우주의 IT 소행성

들어가기에 앞서

상호 배타적 집합 (Disjoint Set)

- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조직하는 자료 구조

- 공통 원소가 없는 부분 집합들로 나누어진 원소들에 대한 자료구조

- 서로소 집합 자료구조

유니온 파인드

- 그래프 알고리즘, 합집합 찾기의 의미를 가짐

- 상호 배타적 집합 이라고도 한다.

- 여러 노드가 존재할 때 두 개의 노드를 선택하여 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

- 유니온과 파인드 크게 3가지 연산으로 이루어져 있습니다.

> Make-Set : 초기화, x를 유일한 원소로 하는 새 집합을 생성

> Union 연산 :  x가 어떤 집합에 포함되어 있는지 찾는 연산

> Find 연산 : x와 y가 포함되어 있는 집합을 합치는 연산

유니온 파인드 어디에 사용하는 걸까?

- 전체 집합을 구성 원소들이 겹치지 않도록 분할하는 데 자주 사용

- Krusakl MST 알고리즘 에서 새로 추가할 간선이 사이클을 형성하는지 판단

C언어로 구현한 유니온 파인드

int root[MAX_SIZE];
int rank[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
  root[i] = i;
  rank[i] = 0;
}


int find(int x) {
  if (root[x] == x) {
      return x;
  } else {
      return root[x] = find(root[x]);
  }
}


void union(int x, int y){
   x = find(x);
   y = find(y);

   if(x == y)
     return;

   if(rank[x] < rank[y]) {
     root[x] = y;
   } else {
     root[y] = x;

     if(rank[x] == rank[y])
       rank[x]++;
   }
}

참고 및 소스코드 블로그

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

신장 트리, 스패닝 트리 (Spanning Tree)

- N개의 정점으로 이루어진 무방향 그래프에서 N개의 모든 정점과 N - 1개의 간선으로 만들어진 트리

최소 비용 신장 트리 (Minimum Cost Spanning Tree)

- 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

- 여기서 의미하는 가중치란 비용, 거리, 시간 등을 의미한다.

크루스칼 알고리즘 (Kruskal Algorithm)

- 최소 비용 신장 트리를 구할 수 있는 효과적인 알고리즘

- 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법

- 탐욕적인 (Greedy한) 방법임 

크루스칼 알고리즘의 동작 방식 - 1 (가중치가 높은 간선을 제거하는 방식)

1. 그래프의 모든 간선을 가중치에 따라 내림차순으로 정렬

2. 그래프에서 가중치가 가장 높은 간선을 제거 (이 때, 정점을 그래프에서 분리시키는 간선은 제거할 수 없음)

-> 즉 간선을 제거했을 떄 더이상 그래프가 이어지지 않고 끊어지면 안된다는 말

3. 그래프의 간선이 N - 1개 남을 때 까지 2를 반복

크루스칼 알고리즘의 동작 방식 - 2 (가중치가 낮은 간선을 삽입하면서 만드는 방식)

1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬

2. 그래프의 가중치가 제일 낮은 간선을 삽입 (이 때, 사이클을 형성하는 간선은 삽입할 수 없음)

-> 즉, 간선을 놓았을 때 그래프가 사이클을 이루게 되면 안 된다는 말

3. 그래프의 간선이 N - 1개 남을 때 까지 2를 반복

그렇다면, 이 그래프가 사이클을 이루고 있는지는 어떻게 알아?

-> 유니온 파인드(Union-find) 알고리즘을 이용해 확인 할 수 있다.

Kruskal 알고리즘의 시간 복잡도는?

- 간선들을 정렬하는 초기 시간에 좌우

- 간선 e개를 효율적으로 정렬한다면 O(eloe2e)로 해결 가능

참고한 글 (자세한 설명)

https://blog.naver.com/diddnjs02/222000205465

• 정보·통신 생성 시스템에서, 문제의 해답을 구하기 위한 추론 제어 방식의 하나. 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 처음으로 돌아가서 다른 규칙을 선택하여 다시 시도한다.

-표준 국어 대사전에서 발췌-

일반적으로 재귀함수에서 더 이상의 호출이 의미 없을 때, 중간에 재귀함수를 중단시키는 알고리즘을 의미한다.

백준 14889번, 15661번 스타트 링크 문제를 통해 백트래킹에 대해 알아보자.

1 ~ N까지의 번호 중 2개의 팀을 각 N/2명으로 나누어야 한다.

2. 이때 S[I][J] = i번 사람과 j번 사람이 같은 팀일 때 팀에 더해지는 능력치이다.

3. 팀의 능력치 : 팀에 속한 모든 s[i][j]쌍의 합이다.

4. 문제 요구 사항 : 두 팀의 능력치를 구하고 차이의 최소를 구하라

해당 문제를 요구 사항에 맞게 코딩하면

def go(index, first, second):
    if index == n:
        if len(first) != n // 2:
            return -1
        if len(second) != n // 2:
            return -1
        t1 = 0
        t2 = 0
        for i in range(n // 2):
            for j in range(n // 2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1 - t2)
        return diff
    ans = -1

    t1 = go(index + 1, first + [index], second)
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    t2 = go(index + 1, first, second + [index])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans


n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))

이런 코드가 나오게 된다.

index : 사람을 어떤 팀에 넣을지 (스타트 팀, 링크 팀)

first : 1번 팀, second : 2번 팀

index == n 일 경우 함수 종료

first나 second의 팀 수가 n//2를 넘어가게 되면(딱 절반이어야 하는데 넘어갈 때)  -1 반환

하지만 index == n 일때 

first나 second가 n//2가 아님을 검사하게 되면

결국 index는 n 만큼의 재귀를 실행하게 된다. 

만약 first나 second가 (n이 8일 때) 5를 넘었을 때 바로 종료한다면 더 시간을 단축할수 있을 것이다.

이때를 위해 백트래킹 방법이 사용된다.

재귀 중간에, 특정 상황(의미 없는 재귀가 반복된다고 판단)에서 재귀를 종료시키는 구문을 넣어준다.

def go(index, first, second):
    if index == n:
        if len(first) != n // 2:
            return -1
        if len(second) != n // 2:
            return -1
        t1 = 0
        t2 = 0
        for i in range(n // 2):
            for j in range(n // 2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1 - t2)
        return diff
    ans = -1
    if len(first) > n // 2:
        return -1
    if len(second) > n // 2:
        return -1

    t1 = go(index + 1, first + [index], second)
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    t2 = go(index + 1, first, second + [index])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans


n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))

따라서 중간에

if len(first) > n // 2:
    return -1
if len(second) > n // 2:
    return -1

를 넘어줌으로써, 시간을 절약시킬 수 있다.

다이나믹 프로그래밍 (DP)

- 메모리 공간을 더 사용하여 연산속도를 비약적으로 증가시키는 방법

- 동적 계획법이라고도 함

- 탑다운과 보텀업 방식으로 나뉨

다이나믹 프로그래밍의 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션 (캐싱)

- DP구현 방법중 하나, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식이 호출될 때 메모한 결과만을 그대로 가져오는 기법

탑다운 (Top-Down, 하향식)

- 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 큰 문제를 해결 하기 위해 작은 문제를 호출한다고 해서 Top-Down 방식이라 함

- 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

보텀업 (Bottom-Up, 상향식)

- 반복문을 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 작은 문제부터 차근차근 답을 도출한다고 해서 보텀업 방식이라 한다.

- 다이나믹 프로그래밍의 전형적인 형태

- 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP테이블'이라 부른다

다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전 계산 결과를 일시적으로 기록해 놓은 것이므로 다이나믹 프로그래밍과는 별도의 개념이다.