[JAVA] 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)
2023. 8. 20. 16:25
JAVA/알고리즘 개념 정리
LIS 란? Longest Increasing Subsequence ex) 수열 A = {10, 20, 10, 30, 20, 50}가 주어지고 가장 긴 증가하는 부분 수열을 구하는 문제 증가하는 부분 수열을 모두 구해보면 아래와 같음 {10}, {20}, {30}, {50} {10, 20}, {10, 30}, {20, 30}, {20, 50}, {30, 50} {10, 20, 30}, {10, 20, 50}, {10, 30, 50}, {20, 30, 50} {10, 20, 30, 50} 이 중 가장 길이가 긴 부분 수열은 {10, 20, 30, 50} 해결 방법 1 - O(n^2) 가장 쉬운 해결 방법은 일반적인 dp를 사용하는 방법 dp[i] = dp[i - 1]과 arr[i]를 포함시켜 만들 수 있는..
[JAVA] Knapsack 알고리즘
2022. 10. 11. 16:51
JAVA/알고리즘 개념 정리
Knapsack 알고리즘 이란? Knapsack은 배낭이란 뜻으로, Knapsack 알고리즘은 배낭 알고리즘 이라고도 불림 Knapsack 알고리즘은 DP의 일종으로 배낭 채우기 문제에서 유래되었음 배낭 채우기 문제란 배낭의 크기 k와 n개의 물건 각각의 무게와 가치가 주어졌을 때, 배낭에 넣은 물건들의 최대 가치의 합을 구하는 문제 ex) 무게가 7까지 담을 수 있는 배낭이 있고, 5개의 물건의 무게와 가치가 아래와 같다고 생각해 보자 물건 1 : 무게 3, 가치 8 물건 2 : 무게 1, 가치 5 물건 3 : 무게 2, 가치 7 물건 4 : 무게 2, 가치 2 물건 5 : 무게 2, 가치 6 이 때, 가방에 넣을 수 있는 최대 가치를 구해보자 만약 1번 물건(3, 8)만 있었다고 가정해보면 DP 테이..
[JAVA] CCW
2022. 6. 17. 19:48
JAVA/알고리즘 개념 정리
CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*Y1 + X3*Y2 + X1*Y3 ) 공식을 따로 외울 필요없이 아래 그림처럼 X1, Y1을 한 번 더 쓴 후, 검은 화살표 곱은 더하고 빨간 화살표 곱은 빼주면 됨 계산된 CCW 값으로는 2가지를 알 수 있음 CCW의 부호에 따라 시계방향, 반시계방향, 일직선의 위치관계에 있는지 파악 가능 CCW 시계 방향 CCW == 0 => 일직선 CCW > 0 => 반시계 방향 CCW의 절대값은 세 점의 벡터의 외적값을 나타냄..
[JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법
2022. 6. 16. 14:20
JAVA/알고리즘 개념 정리
외판원 순회 문제(TSP) 란? 모든 도시들 간에 이동비용이 주어졌을 때, 각 도시들을 한번만 방문하고 처음 시작점으로 돌아오는 최소 비용을 구하는 문제 TSP의 핵심 논리는 반복되는 부분을 제거해서 시간복잡도를 줄이는 것 ex) 0, 1, 2, 3, 4, 5 도시가 있다고 생각해보자 모든 도시가 이어져 있을때 모든 경로를 가보려면, 최소 비용을 구하기 위해 (6-1)! = 120개의 경로를 비교해야 함 시간복잡도가 n! 식으로 나오면 n이 13정도만 되어도 1초가 넘어감 시간을 줄일 수 있는 방법을 생각해보자 0->1->2->3->...->0 과 0->2->1->3->...->0 의 상황을 생각해보면 0에서 출발해 1,2,3 도시를 거쳤고 현재 3번 도시에 있는 상황 이 두 상황에서는 4, 5번 도시를..
[JAVA] 세그먼트 트리 (Segment Tree)
2022. 6. 9. 17:31
JAVA/알고리즘 개념 정리
Segment Tree 란? 데이터 집합이 주어지고, 특정 구간의 합, 최대, 최소 값을 구해야하는 문제가 주어짐 이 때, 구간이 여러개이거나 데이터가 업데이트 될 수 있는 상황에서 더 빠르게 찾아내기 위해 고안된 자료구조 Sement Tree 사용 예제 입력으로 5, 2, 4, 3, 1이 들어왔다고 가정 + 업데이트를 반영한 구간합을 출력해야 되는 상황 트리 초기화 입력으로 들어온 5개의 데이터를 모두 리프 노드에 넣어야 됨 리프노드 : 자식이 없는 노드 이런 식의 트리로 만드는게 목표 배열 사용 (루트 노드가 1번, 1번의 자식들이 순서대로 2, 3번, .... index가 8인 위치에 5를 넣어줌, .....) arr[1~15] = [0, 0, 0, 0, 0, 0, 0, 5, 2, 4, 3, 1, ..
[JAVA] Union-Find
2022. 6. 6. 14:54
JAVA/알고리즘 개념 정리
Union-Find 란? Union : 특정 2개의 노드를 연결해 1개의 집합으로 묶는 작업 Find : 특정 2개의 노드가 같은 집합에 속해 있는지 확인하는 작업 다음과 같이 6개의 노드가 있다고 가정 (1, 2), (2, 3), (4, 6), (3, 6) 을 연결했을 때, 생기는 그룹은 몇개일까? group[1~6] = [1, 2, 3, 4, 5, 6]으로 초기화 이는 각 index가 속한 그룹의 대표값이라 생각하면 됨 1, 2 연결 노드 1과 노드 2의 대표값이 다름 => group[2]에 1을 넣어줌 => group = [1, 1, 3, 4, 5, 6] 2, 3 연결 노드2와 노드 3의 대표값이 다름 => group[3]에 노드2의 대표값 1을 넣어줌 => group = [1, 1, 1, 4, 5..
[JAVA] 플로이드-워셜 알고리즘 (Floyd-Warshall)
2022. 6. 5. 20:11
JAVA/알고리즘 개념 정리
Floyd-Warshall 알고리즘 이란? 모든 노드간에 최단거리를 구하는 알고리즘 다익스트라, 벨만포드는 한 노드에서 모든노드까지의 최단경로 Floyd-Warshall은 모든노드에서 모든노드까지의 최단 경로 벨만포드와 같이 가중치에 음수가 있어도 가능 시간복잡도 : O(V^3) (V:노드의 수) 위 그래프에서 1 -> 5의 최단경로는 1 -> 3 -> 4 -> 5 임 이 때, 중간지점을 4로 지정해 보면 (1 -> 4) + (4 -> 5) = 1 -> 5 가 항상 성립 Floyd-Warshall은 이 논리를 사용 시작점 : s, 끝점 : e, 중간점 : k => dist[s][e] = min(dist[s][e], dist[s][k] + dist[k][e]) k, s, e는 3중 for문을 통해 모든 경..