알고리즘 문제 풀이 공부 _ 2

Union & Find

찾고자 하는 대상을 검색해서, 그 대상을 그룹으로 묶는 알고리즘이다.

정확한 정의는 아니지만 내가 이해한 바로는 C++의 포인터에 가깝다. 특정 데이터의 값을 포인터처럼 다른 데이터를 가르키게 한다. 그럼 특정 데이터와 가르키는 데이터는 같은 그룹이라는 뜻을 내포하는 것으로 이해하고, 로직을 작성하면 된다.

 

Union & Find는 다음 문제와 같다.

친구들이 서로 아는 사이인지 물어본다. 친구의 친구도 아는 사이로 한다. 

1,2

2,3

3,4

1,5

6,7

7,8

8,9

 

이때 풀이는 다음과 같다.

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a]=b;
}

unf 라는 배열을 미리 만들어 두고, Find로 하여금 데이터 가르키는 값을 가져오는 방식이다.

1,2 를 비교하게 되었을때 변경되는 unf의 값.

2,3 를 비교하게 되었을때 변경되는 unf의 값이다.

 

 

 

문제

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

그림은 아래와 같다.

 

이 문제는 도로의 값을 오름차순으로 나열한 뒤에 Union & Find 알고리즘으로 적용시키면 된다.

로직도 똑같이 unf 로 묶으면 된다. 그렇게 해서 unf로 묶이지 않은 대상이라면 도로의 값을 추가하고 unf 로 묶으면 되는 방식이다.

 

위 문제는  priority_queue 로도 풀수 있다.

어찌되었든 오름차순으로 정렬하기 때문에 우선순위 큐에 넣고, 노드 하나를 기준으로 연결해 나아가는 방식이다.

 

 

다익스트라 알고리즘

길찾기 알고리즘이다. 그런데 조건이 있는데, 모든 노드가 양수여야 한다. 다익스트라 알고리즘 방식은 큐에 시작 노드를 넣고, 가장 작은 비용의 노드로 이동하며 최소경로 값들을 기록하며 모든 최소 경로를 기록한 뒤에 결론을 내는 알고리즘이다.

 

 

 

 

 

다이나믹 - TopDown : DFS , 메모이제이션

동적 계획법 ( Dynamic Programming ) 이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방식을 말한다. 

그중 TopDown 방식은 가장 위에서 부터 작은 조각들로 조각조각 내어 푸는것을 볼 수 있다.

 

LIS : 최장 증가 부분 수열 (Longest Increasing Subsequence)

주어진 수열에서 원소들의 순서를 유지하면서 가장 길게 증가하는 부분 수열을 찾는 알고리즘이다.

- 1차원 DP 배열 dp[i]을 만든다. 여기서 i는 i번째 원소를 끝으로 하는 배열의 길이이다.

 

점화식 :

• dp[i] = max(dp[i], dp[j] + 1) (단, j < i이고 arr[j] < arr[i])
• 즉, i번째 원소 이전에 있는 모든 원소 j에 대해, arr[j] < arr[i]이면, dp[i]는 dp[j] + 1을 취한다.
• 이를 통해 i번째 원소를 끝으로 하는 LIS의 최대 길이를 구할 수 있다.

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

 

LCS : 최장 공통 부분 수열(Longest Common Subsequence)

두 배열에서 가장 긴 공통 부분 수열을 찾는 알고리즘이다.

- 2차원 DP 배열 dp[i][j]를 만든다. 여기서 dp[i][j]는 배열 A[0...i-1]과 배열 B[0...j-1]의 최장 공통 부분 수열의 길이를 뜻한다.

 

점화식 :

• 두 배열의 원소가 같은 경우 (A[i-1] == B[j-1]):

 

• • dp[i][j] = dp[i-1][j-1] + 1: 즉, 현재 원소가 같다면 이전까지의 최장 공통 부분 수열의 길이에 1을 더한다.
• 두 배열의 원소가 다를 경우 (A[i-1] != B[j-1]):
  • dp[i][j] = max(dp[i-1][j], dp[i][j-1]): 두 배열에서 하나씩 원소를 제외한 두 경우 중 더 긴 공통 부분 수열의 길이를 선택한다.

 

 

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

 

 

냅색 알고리즘

냅색은 배낭이란 뜻인데, 배낭에 가장 효율적으로 담을 수 있는 문제가 유명해져서 이름붙여진 알고리즘이다.

가방에 담을 수 있는 무게는 제한이 있고, 그렇기 때문에 가장 효율적으로 담아야 한다.

	vector<int> dy(m+1, 0);
	for(int i=0; i<n; i++){
		cin>>w>>v;
		for(int j=w; j<=m; j++){
			dy[j]=max(dy[j], dy[j-w]+v);
		}
	}

 

 

 

플로이드 워셜 알고리즘

다익스트라 알고리즘과 다른점은, 본 알고리즘은 어느 노선이든 각 위치로 가는 최적의 값을 알아야 한다는 로직이다.

그렇기 때문에 모든 경우를 다 하다보면 비용이 비싸지기 때문에 새로운 방식으로 계산하게 된다.

	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(dis[i][j]>dis[i][k]+dis[k][j]){
					dis[i][j]=dis[i][k]+dis[k][j];
				}
			}
		}
	}