공간복잡도

8 동적 계획법 8.1 도입 동적 계획법(dynamic programming)이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍(programming)이라는 단어와는 아무런 관련이 없다. 중복되는 부분 문제 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 ..

02 알고리즘 분석 (04 ~ 05) 04 알고리즘 시간 복잡도 분석 4.1 도입 두 알고리즘의 속도를 비교하는 가장 직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는 것이다. 하지만 프로그램의 실행 시간은 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합하다. 가장 큰 이유는 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어는 물론이고 운영체제, 컴파일러까지 수 많은 요소에 의해 바뀔 수 있기 때문이다. 두 번째 이유는 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못하기 때문이다. 알고리즘의 수행 시간을 지배하는 것은 반복문이다. 입력의 크기가 작을 때는 반복외의 다른 부분들이 갖는 비중이 클 수가 있지만, 입력의 크기..