1. 개요 [그림 1] 동적 계획법 ( Dyanmic Programming ) 완전검색을 좀 더 효율적으로 하는 방법Recursive + Memoization 기법을 활용 (1) 메모이제이션 (Memoization) : 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기법으로 동적계획법의 핵심이 되는 기술이다. (2) 동적계획법의 적용 요건1. 최적 부분문제 구조 (Optimal Substructure) : 최적화 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다.동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이용해서 구하기 때문에 만약 큰 문제..
1. 개요 [그림 1] 깊이 우선 탐색 (Depth First Search) 깊이 우선 탐색 알고리즘은 그래프 구조에서 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더 이상 갈 곳이 없게되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법이다. 따라서, 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용 하거나 재귀호출을 통해서 구현한다. 2. 깊이 우선 탐색 예제 1 - 두 색으로 칠하기 (Binary Coloring) 평면위의 지도에서 서로 인접한 다른 영역을 구분하기 위해서 다른 색으로 칠하고자 한다. 어떤 연결..
1. 개요 [그림 1] 탐욕법 ( Greedy ) 과정 탐욕법 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법이다. 일반적으로 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy접근이 된다. 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들어 놓고 보면 그것이 최적이라는 보장은 없다.일단 한번 선택한 것을 번복하지 않는다는 특성 때문에 대부분의 탐욕 알고리즘은 단순하며, 또한 제한적인 문제들에 적용된다. 최적화 문제 (optimization)란 가능한 해들 중에서 가장 좋은 (최대 또는 최소)해를 찾는 ..