![]()
모든 쌍 최단 경로 문제 (All Pairs Shortest Paths) 각 쌍의 점 사이의 최단 경로를 찾는 문제 다익스트라(Dijkstra)의 최단 경로 알고리즘 이용 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 시간복잡도는 n x O(n^2) = O(n^3) 단, n은 점의 수 2024.03.12 - [Algorithm] - [알고리즘] 다익스트라 (Dijkstra) 최단 경로 알고리즘 플로이드-워셜 (Floyd-Warshall) 알고리즘 Warshall 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안 Floyd 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘을 플로이드-워셜 알고리즘 이라 명칭 플로이드 알고리..
파일 압축 (file compression) 파일의 각 문자가 8 bit 아스키 (ASCII) 코드로 저장되면, 그 파일의 bit 수는 8 x (파일의 문자 수) 주어진 파일의 크기를 줄이는 방법 허프만 압축(Huffman coding) 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당 드물게 나타나는 문자에는 긴 이진 코드를 할당 접두부 특성 (prefix property)이 존재 입력 파일에 대해 각 문자의 출현 빈도수에 기반을 둔 이진트리를 만들어서, 각 문자에 이진 코드를 할당 해당 이진 코드를 허프만 코드라고 지칭 접두부 특성 (prefix property) 각 문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진 코드의 접두부 (prefix)가 되지 않는다는 것 문자 ‘a’에 할당된 ..
작업 스케줄링 (Job Scheduling) 문제 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 시작시간, 종료시간, 작업 길이에 대한 그리디 알고리즘 빠른 시작시간 작업 우선 (Earliest start time first) 배정 빠른 종료시간 작업 우선 (Earliest finish time first) 배정 짧은 작업 우선 (Shortest job first) 배정 긴 작업 우선 (Longest job first) 배정 첫 번째 알고리즘을 제외하고 나머지 3가지는 항상 최적해를 찾지 못함 Pseudo code JobScheduling(t) Input: n개의 작업 t1, t2, ⋯, tn Output: 각 기계에 배정된 작업 순서 1. 시작시간의 오름차순으로 ..
![]()
집합 커버 (Set Cover) 문제 n 개의 원소를 가진 집합 U U의 부분집합들을 원소로 하는 집합 F F의 원소들 중 선택하여 합집합이 U랑 같아지는 원소의 최소 개수 신도시 학교 배치 문제 아래 두 조건을 만족하는 학교 위치 선정 학교는 마을에 위치해야 함 등교 거리는 걸어서 15분 이내이어야 함 학교의 위치 최소 예시 문제 도식화 1. U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 2. F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10} 3. S1 = {1, 2, 3, 8} 4. S2 = {1, 2, 3, 4, 8} 5. S3 = {1, 2, 3, 4} 6. S4 = {2, 3, 4, 5, 7, 8} 7. S5 = {4, 5, 6, 7} 8. S6..
배낭 (Knapsack) 문제 n개의 각각 무게와 가치를 지닌 물건을 최대의 가치를 갖도록 배낭에 넣는 문제 부분 배낭 (Fractional Knapsack) 문제 물건을 나눠서 담는 것을 허용 그리디 사용 가능 0-1 배낭 문제 물건을 통째로 배낭에 넣어야 함 동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결 부분 배낭 문제 그리디 알고리즘 Pseudo code FractionalKnapsack(n, weightAndPriceList, C) Input 물건 n개 각 물건의 무게와 가치 배낭의 용량 C Output 배낭에 담은 물건 리스트 L 배낭에 담은 물건 가치의 합 v 1. 각 물건에 대해 단위 무게 당 가치를 계산 2. 물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬하고, 정..
최단 경로 찾기 (Shortest path problem) 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 다익스트라 (Dijkstra) 알고리즘 주어진 출발점에서 시작 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 Pseudo code ShortestPath(G, s) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 출발점 s로부터 (n - 1)개의 점까지 각각 최단 거리를 저장한 배열 D 1. 배열 D를 ∞로 초기화시킨다. 단, D[s] = 0으로 초기화한다. // 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다. 2. whi..
프림 최소 신장 트리 (Prim MST) 임의의 점 하나를 선택한 후, (n - 1)개의 선분을 하나씩 추가시켜 트리 Pseudo code PrimMST(G) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 최소 신장 트리 T 1. 그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p] = 0으로 놓는다. // 배열 D[v]는 T에 있는 점 u와 v를 연결하는 선분의 최소 가중치를 저장하기 위한 요소 2. for (점 p가 아닌 각 점 v에 대하여) { // 배열 D의 초기화 3. if (선분 (p, v)가 그래프에 있으면) 4. D[v] = 선분 (p, v)의 가중치 5. else 6. D[v] = ∞ 7. } 8. T = {p} // 초기에 트리 T는..
크러스컬 최소 신장 트리 (Kruskal MST) 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 Pseudo code KruskalMST(G) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 최소 신장 트리 T 1. 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자. 2. T = ∅ // 트리 T를 초기화시킨다. 3. while ( T의 선분 수 < n-1 ) { 4. L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다. 5. if (선분 e가 T에 추가되어 사이클을 만들지 않으면) 6. e를 T에 추가시킨다. 7. else // e가 T에 추가되어 사이클이 만들어지는 경우 8. e..
![]()
최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 (b)는 최소 신장 트리 (c)는 가중치의 합이 (b)보다 큼 (d)는 트리가 주어진 그래프의 모든 노드를 포함하지 않음 Idea 사이클이 없도록 모든 점을 연결 그래프의 점의 수가 n인 경우 신장 트리에 (n - 1)개의 선분이 존재 트리에 선분을 하나 추가할 경우, 반드시 사이클이 형성 관련 알고리즘 크러스컬 (Kruskal) 알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 2024.03.10 - [Algorithm] - [알고리즘] 크러스컬 최소 신장 트리 (Kruskal MST) 프림 (Prim) 알..
동전 거스름돈 (Coin Change) 동전 거스름돈의 최소 동전 수를 찾는 문제 단, 동전 액면 500, 100, 50, 10, 1 Idea 남은 액수를 초과하지 않는 조건하에 가장 큰 액면의 동전을 택함 Pseudo code CoinChange(W) Input: 거스름돈 액수 W Output: 거스름돈 액수에 대한 최소 동전 수 1. change = W n500 = n100 = n50 = n10 = n1 = 0 // n500, n100, n50, n10, n1은 각각의 동전 카운트 2. while ( change ≥ 500 ) change = change-500, n500++ // 500원짜리 동전 수를 1 증가 3. while ( change ≥ 100 ) change = change-100, n1..
