알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다. 04. 그리디(Greedy) 알고리즘 최적화 문제를 해결하는 알고리즘이다. 입력 데이터 간의 관계를 고려하지 않고, 수행 과정에서 최솟값 또는 최댓값을 가진 데이터를 선택한다. 근시안적 선택으로 부분적인 최적해를 찾고, 이를 모아서 문제 전체의 최적해를 찾는다. 한번 선택하면 번복하지 않아서 알고리즘들이 비교적 단순하다. 4.1 동전 거스름돈 거스름돈의 동전 개수를 가장 적게 받는 방법 남은 액수를 초과하지 않는 조건에서 가장 큰 액면의 동전을 취하는 방법을 사용한다. Pseudo Code int CountCoin(int change) { int n500 = n100 = n50 = n10 = n1 = 0; while (change..

작업 스케줄링(Task Scheduling) 기계에서 수행되는 n개의 작업들을 수행 시간이 중복되지 않도록 가장 적은 수의 기계에 배정하는 문제이다. 각 작업은 시작시간과 종료시간이 정해져있다. 발표 시간이 정해진 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다. 알고리즘 다음과 같은 그리디 알고리즘이 존재한다. 빠른 시작 시간 작업 우선 (Earliest Start Time First) 빠른 종료 시간 작업 우선 (Earliest Finish Time First) 짧은 작업 우선 (Shortest Job First) 긴 작업 우선 (Longest Job First) 여기서는 최적해를 찾기 위해 첫 번째 방법을 선택한다. 빠른 시작 시간 작업 우선 (Earliest Start Time First) ..

집합 커버 문제 (Set Cover Problem) 전체 집합 U와, 그 부분 집합 Si들을 원소로 갖는 집합 F가 있다고 하자. F의 원소인 Si들을 합집합하여 전체 집합 U와 같아지는 집합 Si들의 최소 개수를 찾는 문제이다. F에 있는 집합들의 모든 조합을 하나씩 찾을 경우 만약 F의 원소의 개수가 n개이면 나올 수 있는 경우의 수는 (2n - 1)개이고, n이 증가함에 따라 이 방식으로 최적해를 찾는 것은 실질적으로 불가능하다. 따라서 최적해 대신 최적해에 근접한 근사해(Approximation Solution)을 찾아야 한다. U에 있는 원소를 가장 많이 커버하는 Si를 반복적으로 찾아서 포함시키는 방식을 사용한다. 알고리즘 입력에 전체 집합 U와 그 부분 집합 Si들을 포함한 집합 F가 주어진..

부분 배낭 문제 (Fractional Kanpsack Problem) 배낭 문제 n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대의 가치를 갖도록 넣는 방법에 대한 문제이다. 부분 배낭 문제는 물건을 부분적으로 담는 것이 허용된다. 알고리즘 물건을 부분적으로 담을 수 있으므로, 단위 무게당 가치가 제일 높은 것부터 배낭에 넣는다. 만약 통째로 넣을 수 없다면, 넣을 수 있는 만큼만 부분적으로 넣는다. 입력으로 각 물건의 무게와 가치, 배낭의 용량을 받는다. 출력은 배낭에 담은 물건 리스트와 배낭에 담은 가치의 총합이다. Pseudo Code FractionalKnapsack(Item *arr, int capacity) { 각 물건의 단위 무게당 가치를 계산한다. 단위 무게당 가..

최단 경로 찾기(Shortest Path) 가중치 그래프의 어느 한 출발점에서 도착점까지의 최단 경로를 찾는 문제이다. 대표적으로 다익스트라 최단 경로 알고리즘이 있다. 다익스트라(Dijkstra) 최단 경로 알고리즘 프림의 최소 신장 트리(MST) 알고리즘과 비슷하다. 주어진 출발점에서부터 최단 거리인 점을 하나씩 확정해가며 각 점까지의 최단 거리를 점차 업데이트하는 방식이다. 입력으로 주어지는 그래프에는 각 점과 선분에 대한 정보가 있다고 가정한다. Pseudo Code ShortestPath(Graph g, Node start) { int dist[n]; // 최단 거리를 저장한 배열 dist[start] = 0; start를 제외한 나머지는 inf로 초기화시킨다. while (최단 거리가 확정되지..

최소 신장 트리(Minimum Spanning Tree) 가중치 그래프에서, 사이클 없이 모든 점을 연결시킨 트리들 중에 가중치 합이 최소인 트리를 의미한다. 그래프의 점의 수가 n이면, 신장트리에는 (n - 1)개의 선분이 존재한다. n개 이상의 선분이 존재할 경우 사이클이 생기고, 이는 트리라고 할 수 없다. 대표적인 그리디 알고리즘으로 크러스컬(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 존재한다. 입력으로 받는 그래프 G에는 점의 집합 V와 선분 집합 E에 대한 정보가 포함되어 있다. 점의 개수를 n, 선분의 개수를 m이라고 가정한다. 크러스컬(Kruskal) 알고리즘 최소 가중치를 가진 선분을 하나씩 뽑아서, 트리에 사이클을 형성하지 않는지 검사하고 추가하는 방식이다. Pseudo Co..

알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다. 03. 분할 정복 알고리즘 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다. 분할된 입력의 문제(부분문제, Subproblem)에 대해 동일한 알고리즘을 적용하여 부분해를 얻으며, 이를 취합해서 원래 문제의 해를 얻는다. 더 이상 분할할 수 없을 때까지 계속 부분문제로 분할한다. 문제 : 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분문제의 크기가 n/2이라고 할 때, 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 1이 될까? 총 분할 횟수를 k라고 하면, n/2k = 1이므로 k는 log2n이 된다. 분할 정복 알고리즘의 분류 문제가 a개로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘 ..

선택 문제 (Selection Problem) n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제이다. 간단한 해결 방법 최소인 숫자들 찾아서 제거하는 방법을 k번 반복한다. 최악의 경우 시간 복잡도 : O(kn) 오름차순으로 정렬한 뒤 k번째 숫자를 찾는다. 최악의 경우 시간 복잡도 : O(nlogn) 간단하지만 비효율적이다. 이진 탐색과 퀵 정렬을 섞으면 원하는 숫자를 효율적으로 찾을 수 있다. 데이터 분석에서 중앙값(median)을 찾는 데 활용된다. 아이디어 퀵 정렬에서 처럼 피벗을 정하고 피벗보다 작은건 왼쪽, 피벗보다 큰건 오른쪽에 위치하도록 정렬한다. 작은 그룹의 크기와 큰 그룹의 크기는 피벗의 인덱스를 통해 알 수 있다. 분할 찾고자하는 k번째로 작은 숫자가 피벗인 경우 그대로 반환한다...

알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다. 02. 알고리즘을 배우기 위한 준비 2.1 알고리즘이란 유래 : 페르시아 수학자인 알콰리즈미(al-Khwarizmi)(서기 780~850년) 알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다. 이는 컴퓨터로 해결할 수 있어야 하며 입력과 출력이 존재한다. 알고리즘의 일반적인 특성 정확성 주어진 입력에 대해 올바른 해를 준다. 수행성 컴퓨터에서 수행이 가능해야 한다. (애매모호한 표현이 없어야 한다.) 유한성 현실적인 시간 내로 종료되어야 한다. 효율성 시간적, 공간적인 효율성을 최대한 고려해야 한다. 2.2 최초의 알고리즘 기원전 300년경에 만들어진 유클리드(Euclid)의 최대공약수를 찾는 알고리즘이 최초이다. 유클리드의 ..

알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다. 01. 알고리즘의 첫걸음 알고리즘이라는 용어는 9세기경 페르시아 수학자인 알콰리즈미(al-Khwarizmi)의 이름으로 부터 유래되었다. 문제를 해결하기 위한 단계적인 절차를 의미한다. 1장에서는 다양한 예시를 보여준다. 1.1 최대 숫자 찾기 문제 : 카드 10장 중에서 가장 큰 숫자 찾기 알고리즘 : 순차 탐색(Sequential Search) == 선형 탐색(Linear Search) 카드를 한 장씩 차례대로 읽어가며 찾는 방식 1.2 임의의 숫자 찾기 문제1 : 45, 20, 60, 35, 10, 55, 90, 85, 75, 25가 적힌 카드 중에 85가 적힌 카드 찾기 알고리즘 : 순차 탐색 최대 숫자 찾기처럼 85를 기..