RAINBOW-LAB

◎ Greedy Algorithm 이란? 탐욕 알고리즘(Greedy Algorithm) 이란, 최적해를 구하는데 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야할 때마다 그 '순간'에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 최적화 방법이다. '순간' 이라고 정의하는 선택은 Local 하게는 최적이지만, 그 선택을 계속 수집하여 Global하게 해답을 만들었다고 해서 그것이 최적이라는 어떠한 보장도 없다. 탐욕 알고리즘에는 대표적으로 '분할 가능 배낭문제' 가 있는데, 다음과 같은 예시를 들어보자. 한 은행의 화폐 단위가 7원/5원/1원 이라고 하자. 한 사람이 14원의 돈을 들고 화폐를 교환하려고 은행에 들렀다. 은행은 Greedy Algorithm을 사용하여 ..

오일러 경로(Eulerian trail) 란 그래프에 존재하는 모든 Edge를 정확히 1번씩만 방문하는 연속된 경로입니다. 이때 시작점과 도착점이 같으면 오일러 회로(Circuit) 가 됩니다. 가장 대표적으로 별 모양 그래프가 있는데 어느 점에서 시작하더라도 모두 출발점으로 되돌아 올 수 있습니다. 즉, 위 그래프는 오일러 회로가 존재합니다. 위 그래프를 다시 보면 모든 정점의 차수가 2(짝수)인데 시작점과 끝점을 제외하고서는 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 마련되어 있어야 하기 때문입니다. 그렇기에 항상 차수가 2의 배수꼴로 붙게 됩니다. 오일러 경로의 존재여부를 판단하는 방법은, 무향 그래프(non-directed graph)일 경우 Degree가 홀수 인 정점(Vertex)가..

어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위 구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이 동적계획법(Dynamic Programming) 이다. Divide-and-conquer 와 비슷해 보이지만 DC는 문제를 큰 부분에서 작은 부분으로 나누는 Top-Down approach인데 반해, DP는 작은 문제부터 큰 문제로 풀어가는 Bottom-Up approach이다. 또한 DC는 나눈 문제들을 완전히 새로운 하나의 독립된 문제로 보지만 DP는 이전 단계의 답에 의존적이다. 그래서 한 번 푼적 있는 문제는 다시 풀지 않도록 테이블에 저장해둔다. 정리하면, 1. 문제를 작은 부분 문제로 나눈다. 2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다. (Mem..

1. P 문제 현실적으로 쓸만한 알고리즘이라면, 그 비용이 견딜만큼 현실적인 알고리즘이라는 것이다. 알고리즘의 Time complexity가 입력 크기 n에 대해 상수 k승을 가진다면 '현실적' 이라고 본다. 예를 들어 $$O(n^2)$$ 혹은 $$O(n^3)$$등이 있다. 입력 크기가 커지면 다항으로 증가하는 비용(Polynomial Complexity)이다. 즉, 현실적인 비용으로 풀 수 있는 문제들, 다항(Polynomial) 알고리즘이 있는 문제들을 'P 클래스 문제' 라고 한다. 2. NP 문제 어려운 문제의 경계에 가까이 있는 문제들의 집합을 'NP클래스 문제' 라고 한다. 운에 기대면 현실적인 비용으로 해결할 수 있는(Non-Deterministic polynomimal) 문제들이다. 운에 ..