코딩테스트에서는 각 문제 당 메모리와 시간이 제한되어 있다. 비교적 적은 입력이나 짧은 알고리즘에서는 이러한 제한이 큰 장애가 되지는 않는다. 그러나 입력이 많은 문제 (예를 들어 10억개의 입력 등) 거나 재귀적인 알고리즘에서는 메모리 혹은 시간 제한에 걸리게 된다. 따라서 우리는 최대한 연산 속도와 메모리 공간을 효율적으로 활용하는 알고리즘을 구현해야 한다. 몇몇 문제에서는 메모리 공간을 조금 더 사용할 수록 비약적으로 연산속도를 줄일 수 있는 경우가 존재한다. 이는 뒤에서 설명할 다이나믹 프로그래밍 기법을 사용하는 경우이다. 다이나믹 프로그래밍이란 동적 계획법이라고도 표현하며 2가지 방식이 존재한다. 이는 아래와 같다. 탑다운 방식 바텀업 방식 먼저 다이나믹 프로그래밍의 기본적인 아이디어는 다음과 ..
