고양이 두 잔

목차 Divide and Conquer 분할 정복 알고리즘은 큰 문제를 작은 문제로 나누어(분할) 해결(정복)하는 알고리즘이다. 조금 더 구체적으로 적자면 분할(Divide): 복잡한 문제를 더 작고 관리하기 쉬운 부분 문제로 분해하여 정복(Conquer): 이 부분 문제들을 해결한 후 결합(Combine): 이들의 해결 결과를 결합하여 원래 문제의 해답을 찾는다. 예를 들자면 정렬 알고리즘 중 병합정렬과 퀵 정렬이 이에 해당하는데, 각 구현방식은 아래 글에 설명되어 있다. [Java+Python]병합 정렬(Merge Sort) [Java+Python]병합 정렬(Merge Sort) 으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bub..

동적 계획법이란 미리 구해뒀던 답을 이용해 하나의 연산은 한 번만 하도록 하는 프로그래밍 패러다임이다. 지난 글에서 알아본 그리디 알고리즘이 그때그때 최적의 값을 찾아가는 방법이라면, 동적 계획법은 문제를 쪼개 모든 경우의 수를 살펴본 뒤 답을 구한다. 다만 연산 속도의 향상을 위해 이미 계산한 값을 저장해두는데, 이때 사용되는 메모리를 캐시(Cache)라고 한다. 동적 계획법이 적용될 수 있는 조건은 두 가지가 있는데, Overlapping Subproblem - 큰 문제를 중복되는 작은 문제로 나눌 수 있다. Optimal Substructure - 나눠진 작은 문제에서 구한 답을 이용해 전체 문제의 답을 구할 수 있다. 가 그것이다. 가장 쉬운 예로 피보나치수열을 들 수 있는데, 재귀 함수만을 이용..