1. 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 정점이 n개인 그래프에서 n-1개의 간선을 선택하는 방식 초기 상태는 n개의 정점들이 하나의 트리가 된다. 하나의 정점을 포함하는 n개의 상호 배타 집합이 존재 간선을 선택하면 간선의 두 정점이 속한 트리가 연결되고 하나의 집합으로 합쳐진다. 사이클이 생기면 안된다. 두 정점이 같은 집합의 원소인지 검사해야한다. 동작과정 최초, 모든 간선을 가중치에 따라 오름차순 정렬 최소 가중치 간선부터 선택하면서 트리 증가 사이클이 존재하면 다음 가중치 낮은 간선 선택 n-1개의 간선이 선택될 때 까지 (2) 반복 소스코드 # G : 그래프 def mst_kruskal(G): mst = [] # 선택된 간선 집합, 공집합으로 ..

1. 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 임의의 정점을 하나 선택해서 시작 선택한 정점들과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 (2) 반복 두 종류의 상호 배타 집합(disjoint set)이 필요 트리 정점 : 최소 신장 트리에 선택된 정점들 비트리 정점 : 선택되지 않은 정점들 소스코드 # G : 그래프 # s : 시작 정점 def mst_prim(G, s): key = [INF] * N # 가중치를 무한대로 초기화 pi = [None] * N # 트리에서 연결될 부모 정점 초기화 visited = [False] * N # 방문 여부 초기화 key[s] = 0 # 시작 정점의 가중치를 0으로 ..

1. 그래프 최소 비용 문제 : 최소 신장 트리 문제 vs 최단 경로 문제 최소 신장 트리 문제 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제 최단 경로 문제 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제 2. 신장 트리(Spanning Tree) 정점인 n개인 undirected graph에서 n개의 정점과 n-1개의 간선으로 구성된 트리 즉, 모든 vertex set을 포함해야한다. 신장 트리의 수는 정점의 개수와 간선의 수의 비례한다. 3. 최소 신장 트리(Minimum Spanning Tree) 가중치 그래프의 신장 트리 중 간선들의 가중치의 합이 최소인 신장 트리 프림 알고리즘과 크루스칼 알고리즘이 존재한다.

1. 서로소 또는 상호배타 집합(Disjoint set) 교집합이 없는 집합 집합에 속한 특정 원소로 각 집합을 구분 대표자(representative) 상호배타 집합 표현 연결 리스트, 트리 2. 상호배타 집합 연산 Make-Set(x) : 원소 x만 속한 집합을 생성 Find-Set9x) : 원소 x가 속한 집합을 알아내는 연산, 해당 집합의 대표자를 반환 Union(x, y) : 원소 x가 속한 집합과 원소 y가 속한 집합을 합치는 연산, 대표자는 본인이 설정 3. 연결 리스트 표현 같은 집합의 원소들을 하나의 연결 리스트로 관리 연결리스트의 첫번째 원소가 집합의 대표원소 각 원소는 대표원소를 가리키는 링크를 갖는다. 4. 트리 표현 집합(disjoint set)을 하나의 트리로 표현 자식 노드가 ..

1. 그래프 탐색 그래프의 모든 정점을 빠짐없이 탐색 2. 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 시작 정점에서 한 방향을 선택해서 다음 정점으로 이동 선택된 정점에서 (1)을 반복 수행하면서 계속 깊이 탐색 이미 방문한 정점은 재방문 안한다. 더 이상 갈곳이 없으면 부모노드로 되돌아가 다시 깊이 탐색 스택을 사용한다 DFS 재귀 호출 # G : 그래프 # v : 시작 정점 # visited : 정점의 방문 여부, False로 초기화 # G[v] : 그래프 G에서 v의 인접리스트 def dfs(G, v): visited[v] = True # v를 방문 표시 visi..

1. 친구관계 A와 B는 친구를 (A - B)로 표현 2. 그래프 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 G = (V, E) |V| : 정점 수, |E| : 간선 수 |V| = n개의 정점은 최대 C(n, 2) = n*(n-1)/2 개의 간선이 가능 3. Directed Graph vs Undirected Graph Undirected Graph 서로 대칭적이지 않은 관계 기업간의 공급관계, 작업의 선후 관계 등을 표현 4. 가중치 그래프(Weighted Graph) 간선에 비용이 추가된 그래프 5. 용어 인접(adjacency) : 두 정점 사이에 간선이 존재할 경우 인접하다고 한다. 완전 그래프 : 모든 정점이 인접한 그래프 부분 그래프 :..

1. 동전 거스름돈 총금액 800, 동전 종류 : 10, 50, 100, 400, 500 그리디 : 500, 100, 100, 100 -> 최적해가 아니다 소스코드 # coin[] : 동전의 금액을 젖아 # choice[] : 선택한 동전 집합 # best : 거스름돈에 대한 최소 동전 개수 def coinChange(choice, N, money): global best if best N best = N else: for i in range(len(coin): if money - coin[i] >= 0: choice[N] = coin[i] coinChange(choice, N+1, money-coin[i])

1. 순열 예시) 원소 개수 n = 4 -> 집합 = {A, B, C, D}, 4!인 24가지의 경우가 존재 따라서 상태 공간 트리에서의 단말노드의 수는 24개이다. 24개의 후보해가 존재한다는 것이고 이것은 단말노드의 수와 같다. 노드 방문 시마다 원소를 가리키는 인덱스 값을 저장 같은 원소 수를 갖는 부분집합과 순열의 상태 공간 트리의 높이는 같다. 순열의 경우 높이가 다른 노드는 선택지 수가 동일하지 않다. 선택할 때마다 다음 선택의 선택지 수가 하나씩 줄어든다. 소스코드 # order[] : 순열의 순서를 저장하는 리스트 def permutation(order, k, n): if k == n: # 다 선택하면 print_order_array(order, n): # 출력 else: check = [..

1. Power set 집합의 모든 부분집합 (공집합, 자기자신 포함) 집합의 원소개수가 n => 부분집합의 개수는 2^n 1 또는 0 값을 가지는 비트열 리스트로 부분집합 표현 소스코드 # a[0, ... , n-1] : 집합에 대한 비트표현 저장, 크기는 원소의 수 # k : 선택한 횟수(현재 노드의 높이) # n : 모든 선택 수(트리의 높이) def subset(a, k, n): if k == n: # 모든 선택이 끝난 상태 (단말노드 도착) process_solution(a, n) # else: a[k] = 0 # k번째 원소 포함 안하는 경우 subset(a, k+1, n) a[k] = 1 # k원소 포함하는 경우 subset(a, k+1, n) 백트래킹 구현은 상태공간트리와 동일한 함수호출트..

1. n-Queens 문제 n x n 체스판에서 n개의 퀸들을 서로 위협하지 않도록 배치하는 문제 2. 백트래킹 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는 기법 최적화(optimize)문제와 결정(decision)문제를 해결할 수 있다. 최적화 문제 미로 찾기, Subset sum 등 결정 문제 n-Queen, Map coloring 등 루트까지 되돌아갔는데 더이상 선택지가 없다면 답이 없는 것이다. 백트래킹의 핵심은 상태 공간 트리를 탐색하는 것! 해를 찾기 위한 선택의 과정을 트리로 표현 트리의 내부 노드는 해로 가는 중간 상태 트리의 단말 노드는 하나의 후보해에 대한 최종 상태 상태 공간 트리를 깊이 우선 탐색(DFS)하는 방법이 백..