무식하게 풀기

완전 탐색(exhaustive search), 혹은 브루트 포스(brute-force)라고 불린다. 컴퓨터의 빠른 속도를 이용하여 모든 경우의 수를 확인하는 방법이다. PS에서는 경우의 수가 크지 않을 때 주로 사용한다. 간단한 예를 들면, 열 명의 학생을 한 줄로 세우려고 하는데, 서로 사이가 안 좋은 학생들끼리는 떨어트려서 세우려고 한다. 이때는 약 360만(10!)의 경우의 수가 나오는데, 컴퓨터에게는 1초도 걸리지 않는 양이니 모든 경우의 수를 확인해보는 것이 빠르게 문제를 해결할 수 있다. (종만북에 따르면 일반적으로 컴퓨터는 1초에 1억번의 계산을 할 수 있다.)

재귀호출

재귀 함수란 자신을 정의할 때 자신을 재참조하는 함수이다. [^1] 간단히 1 to n의 sum을 재귀 함수를 이용해 구해보자.

int sum(int n){
	if(n==1) return 1;
	return n + sum(n-1);
}

n이 1이 될 때까지 계속 자신을 호출하며 답을 구한다. 재귀 함수에서 가장 중요한 것은 재귀호출을 멈출 return 문이 있어야 한다. 그렇지 않다면 무한 호출하며 결국 stack overflow를 일으킬 것이다. 종만북에 따르면, 이런 return문을 재귀 호출의 기저 사례(base case)라고 한다.또한, 모든 입력이 항상 기저 사례의 답을 이용해야 한다.^[1]

해당하는 문제

예제: 보글게임

[1] : 종만북