완전 탐색 (exhaustive search)
컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법. '무식하게; 고지식하게 푼다(brute-force)' 라고도 불린다.
최적화 문제 (optimization problem)
문제의 답이 하나가 아닌 여러 개이고, 그중에서 어떤 기준에 따라 가장 좋은 답을 찾아내는 문제들을 통칭한다. 최적화 문제를 해결하는데 동적 계획법, 조합 탐색, 파라메트릭 서치 등 이 사용된다.
분할 정복 (divide and conquer)
주어진 문제를 작은 사례로 나누고 각각의 작은 문제들을 해결하여 정복하는 방법이다. 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다는 점이다.
동적 계획법 (dynamic programming)
분할 정복과 같은 접근 방식을 사용하되 결과값을 저장해두는 cache 메모리를 두어 재활용함으로써 계산 속도를 크게 향상시키는 방법이다. 이와 같은 최적화 기법을 메모이제이션(memoization)이라고 부른다.
반복적 동적 계획법 (iterative dynamic programming)
반복문(bottom-up)을 이용하여 도표를 작성(tabulation)해 나간다. 구해놓은 값을 토대로 하여 중복된 계산 없이 다음 값을 빠르게 계산할 수 있다.
최적 부분 구조 (optimal substructure)
동적 계획법 알고리즘을 적용하기 위해 아주 중요한 조건으로, 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있는 문제를 일컫는 말이다.
파라메트릭 서치 (parametric search)
최적화 문제를 결정 문제로 바꾼 뒤 이분법(이분 탐색)을 이용해 해결하는 방법이다. 결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제들을 말한다.
탐욕적 선택 속성 (greedy choice property)
답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것을 말한다. "최적해 중 우리가 선택한 방법이 반드시 포함된다" 라는 조건이 성립할 때 탐욕적 선택 속성이 성립한다고 한다.
탐욕법 (greedy method)
문제를 여러 개의 조각으로 나누고 각 단계마다 당장의 가장 좋은 답을 선택하는 방법이다. 선택 기준을 찾는 방법은 작은 입력들을 손으로 직접 풀어보는 것이 효율적이다. 탐욕법은 현재 선택이 앞으로의 남은 선택들에 영향을 끼칠지는 고려하지 않기 때문에 많은 경우 최적해를 구할 수 없다. 따라서 탐욕적 선택 속성과 최적 부분 구조를 만족하는 문제에만 제한적으로 사용될 수 있다.
댓글