복잡도

7 분할 정복 7.1 분할 정복 분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 이 차이점이 아래 그림이다. 그림 (a)는 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고, 그림 (b)는 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여준다. 분할 정복을 ..

06 무식하게 풀기 6.1 도입 흔히 전산학에서 무식하게 푼다(brute-force)는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전탐색(exhaustive search)이라고 부른다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을 정도로 간단한 방법이지만, 완전탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법이다. 컴퓨터의 최대 장점은 속도가 빠르다는 것이기 때문이다. 6.2 재귀 호출과 완전 탐색 재귀 호출 재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다. 예를 들면 ..

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