프로그래밍 잡동사니

다항식 시간에 해결하지 못하는 문제가 근사해도 구하기 힘들다면 해 탐색 알고리즘을 사용한다 1. 백트래킹 기법 (Backtracking) 해를 찾는 도중에 막히면 (= 해가 아니면) 되돌아가서 다시 해를 찾는 기법으로, 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다 * 최적화 문제: 문제의 조건을 만족하는 해의 최대값 or 최솟값 등을 구하는 문제 * 결정 문제: 문제의 조건을 만족하는 해의 존재 여부를 답하는 문제 여행자 문제 (Traveling Salesman Problem, TSP) 백트래킹 알고리즘 최악의 경우 2^n개의 노드를 모두 탐색해야 하는 지수 시간이 걸리며, 이는 모든 경우를 다 검사하여 해를 찾는 완결 탐색 (Exhaustive Search)의 ..

근사 알고리즘 (Approximation Algorithms) NP-완전 문제들은 활용성이 높지만 다항식 시간에 해결할 수 있는 알고리즘이 아직 발견되지 않았고, 존재하지 않을 것으로 추측된다. 일단 해결하기 위해 다음 3가지 중 1가지는 포기해야 한다 다항식 시간에 해를 찾는 것 모든 입력에 대해 해를 찾는 것 최적해를 찾는 것 NP-완전 문제를 해결하기 위해 3번째 요소(최적해)를 포기, 최적해에 아주 근사한 해를 찾아주는 것이 근사 알고리즘이다 최적해가 아닌 근사해를 찾는 대신 다항식 시간의 복잡도를 가진다 근사해가 얼마나 최적해에 근사한지 나타내는 근사 비율(Approximation Ratio)을 알고리즘과 함께 제시해야 한다 근사 비율이 1.0에 가까울수록 정확도가 높은 알고리즘이다 근사 비율을..

P(polynomial) 문제 집합은 다항식 시간 복잡도를 가진 알고리즘으로 해결되는 문제들을 의미하며, O(logn), O(n), O(nlogn), O(n^2), O(n^3) 등 점근적 표기법으로 O(n^k)에 포함되는 시간 복잡도 내에서 해결된다 다항식보다 큰 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합 들이 있는데, 이는 여러 가지 문제 집합으로 다시 분류되며, 이 중 지수 시간 시간복잡도를 가진 알고리즘으로 해결되는 문제들을 NP-완전 문제 집합이라고 한다 * 하나의 NP-완전 문제에 대해서 다항식 시간의 알고리즘을 찾아내면, 모든 다른 NP-완전 문제도 다항식 시간에 해를 구할 수 있다 NP 문제 집합은 이러한 P 문제 집합과 NP-완전 문제 집합을 포함하는 개념으로, 비결정적 다항식 시간..

정렬(Sorting) 알고리즘 내부(Internal) 정렬 입력의 크기가 주기억 장치의 공간보다 작은 경우 (빠름) 버블 정렬, 선택 정렬, 삽입 정렬 합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬 기수 정렬 (입력이 제한된 크기 이내의 숫자로 구성될 때) 외부(External) 정렬: 입력의 크기가 주기억 장치의 공간보다 큰 경우 (느림) 보조 기억 장치에 있는 입력을 나누어 주기억 장치에 읽어 들인 후, 다시 보조 기억 장치에 저장 다방향(p-way) 합병, 다단계(Polyphase) 합병 1. 버블(Bubble) 정렬 이웃하는 숫자를 비교해 작은 수를 앞(위)쪽으로 이동시키는 과정을 반복해 정렬하는 알고리즘 * 작은 수가 앞으로 올라오는 과정이 마치 거품 같아 붙은 이름이다 이중 for문 n(n-1)/..

5. 집합 커버(Set Cover) 문제 집합 커버 문제: n개의 원소를 가진 집합 U가 있고, U의 부분집합들을 원소로 하는 집합 F가 주어질 때, F의 원소들인 집합들 중에서 어떻게 선택하여 합하면 선택하는 집합의 수를 최소화하면서 U와 같게 되는가? 신도시 학교 배치 문제 (응용): 10개의 마을이 있을 때, 등교 거리가 15분 이내가 되도록 학교들의 위치를 선정할 때, 어느 마을에 학교를 신설해야 학교의 수가 최소가 되는가? 그렇다면 집합 커버 문제의 최적해는 어떻게 찾아야 할까? n이 커질 때, 2n-1개를 다 검사하는 것이 비효율적이기 때문에 최적해가 아닌 근사해(approximation solution)를 찾는다 while 루프 수행 최대 n번 / Line 2 O(1) / Line 3 O(n..

그리디(Greedy) 알고리즘 그리디(= 탐욕) 알고리즘: 가능한 해들 중에서 가장 좋은 해를 찾는 최적화(optimization) 문제를 해결하는 알고리즘, 앞뒤 데이터 간 관계를 고려하지 않고 수행 과정에서 최소 or 최대값을 가진 데이터만 근시안적으로 선택 * 한 번 데이터를 선택하면 번복하지 않아서, 알고리즘이 단순하고 제한적인 문제 해결에 적합 1. 동전 거스름돈 문제 남은 액수를 초과하지 않는 조건 하에 가장 큰 액면의 동전을 취하는 방법? (500, 100, 50, 10, 1) 2. 최소 신장 트리(Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클 없이 모든 점을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 (입력: 1개의 연결요소(connected compo..

선택(Selection) 문제 선택 문제: n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제 간단한 방법 최소 숫자를 찾고 제거하는 과정을 k번 반복하고 최소 숫자를 찾는다 ~ 최악의 경우 O(kn) 숫자들을 정렬하고 k번째 숫자를 찾는다 ~ 최악의 경우 O(nlogn) 선택 문제 알고리즘 * 각 그룹의 크기를 알면, k번째 작은 숫자가 어느 그룹에 있는지 알 수 있고, 그 그룹에서 몇 번째 작은 숫자를 찾아야 하는지 알 수 있다! Small group에 k번째 작은 숫자가 속한 경우: k번째 작은 숫자를 해당 그룹에서 찾는다 Large group에 k번째 작은 숫자가 속한 경우: (k – Small group의 숫자 개수 – 1) 번째로 작은 숫자를 해당 그룹에서 찾는다 선택 문제 알고리즘 과정 선..

분할 정복 알고리즘(Divide-and-Conquer) 분할 정복: 아우스터리츠 전투에서 유래된 용어로, 대상을 작게 분할해 각각 정복한다는 의미 분할 정복 알고리즘: 알고리즘 문제를 나눌 수 없을 때까지 쪼개고 각각 풂으로써 전체 답을 구하는 방식 분할된 입력에 대한 문제를 부분문제(subproblem), 부분문제의 해를 부분해라고 한다 부분 문제의 수와 크기에 따라 다음과 같은 분류가 있다 문제가 a개로 분할되고, 부분 문제의 크기가 1/b로 감소하는 알고리즘 a = b = 2인 경우: 합병 정렬, 최근접 점의 쌍 찾기 a = 3, b = 2인 경우: 큰 정수의 곱셈 a = 4, b = 2인 경우: 큰 정수의 곱셈 a = 7, b =2인 경우: 스트라센(Strassen)의 행렬 곱셈 문제가 2개로 분..

알고리즘이란? 알고리즘(Algorithm) = 문제를 해결하기 위한 단계적인 절차 * 해결 방법은 다양하지만 가장 효율적인 방법을 찾는 것에 의의가 있다 알고리즘의 특성 정확성: 주어진 입력에 대해 올바른 해를 주어야 한다 수행성: 각 단계는 컴퓨터에서 수행 가능해야 한다 유한성: 일정한 시간 내에 종료되어야 한다 효율성: 효율적일수록 그 가치가 높아진다 유클리드(Euclid)의 최대공약수 알고리즘 = 최초의 알고리즘 알고리즘의 표현 방법 알고리즘은 프로그래밍 언어나 의사 코드(pseudo code)로 표현할 수 있다 최대값 알고리즘을 표현하는 다양한 방식.. 알고리즘의 분류 문제 해결 방식에 따른 분류 분할 정복(Divide-and-Conquer) 알고리즘 그리디(Greedy) 알고리즘 동적 계획(Dy..

그래프 그래프란 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다 그래프 G는 (V, E)로 표현되며 ‘정점(vertices) or 노드’ / ‘간선(edge) or 링크’ 간의 관계를 의미한다 그래프의 경로: 정점 간 거쳐가는 경로 ex) B -> A -> C -> D 그래프의 길이: 경로 사이의 간선 개수 ex) 3 그래프의 표현 그래프의 탐색 그래프의 탐색은 시작 정점부터 차례대로 모든 정점들을 한 번씩 방문하는 방법으로, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다 신장 트리 신장 트리란 그래프 내의 모든 정점을 포함하는 트리로 사이클을 포함하면 안된다 위상 정렬 위상 정렬이란 방향 그래프에 대해 정점들의 선행 순서를 위반하지 않으면서 모든 정점을 나열하는 것 가중치 그래프 간선..