무식하게 풀기
1. 도입
프로그래밍 대회에서 대부분의 사람들이 가장 많이 하는 실수가 '어렵게 문제 풀기'라고 한다.
이것을 방지하기 위한 첫번째 마음가짐은 '무식하게 풀기'이다.
무식하게 풀기는 컴퓨터의 퍼포먼스를 이용하여 모든 가능성을 열고 보는것이다. 가장 좋은 예시가 '완전 탐색'일 것이다.
2. 재귀 호출과 완전 탐색
재귀 호출
컴퓨터가 수행하는 많은 작업들은 대개 작은 조각들로 나누어 볼 수 있습니다.
그런데 우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있다. 완전히 같은
코드를 반복하는 반복문이 좋은 예이다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀함수 혹은 재귀 호출이다.
재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는
함수를 가리킨다. 이 개념의 연습을 위해 반복문을 재귀로 작성해보자.
#include<cstdio>
//반복문을 수행하는 함수
int sum(int n)
{
int ret = 0;
for (int i = 1; i <= n; i++)
{
ret += i;
}
return ret;
}
//반복문을 재귀함수로 변환 했을 때
int recursiveSum(int n)
{
if (n == 1) return 1;
return recursiveSum(n - 1) + n;
}
int main()
{
printf("%d\n", sum(10));
printf("%d\n", recursiveSum(10));
return 0;
}
위의 코드를 실행해보면 같은 결과가 나오는 것을 확인할 수 있다.
위의 코드를 봤을 때 재귀 함수에서 탈출조건에 유의하자. 탈출조건은 더 이상 처리할 작업이 없을 시 필요한 모듈이다. 모든 재귀 함수는 이와 같이
'더 이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀호출의 '기저 사례'라고 한다.
3. 완전 탐색 레시피
어떤 문제를 완전 탐색으로 해결하기 위해 필요한 과정은 대략 다음과 같다. 이 과정이 모든 문제에 항상 적용되는 것은 아니지만,
어떤 식으로 문제에 처음 접근해야 할지에 대한 대략적인 지침은 될 것이다.
- 완전 탐색은 모든 답을 검사하므로 걸리는 시간은 가능한 답의 수에 비례한다. -> 시간 초과가 예상되면 DP로 가자.
- 답의 후보를 만드는 과정을 여러개의 선택으로 나눈다.
- 하나의 조각을 답의 일부로 만들고 나머지 답을 재귀를 통해 구한다.
- 조각이 더 이상 남지 않거나 하나만 남았을 경우 기저 사례로 빠져나간다.
4. 최적화 문제
지금까지 다뤘던 문제와는 달리 문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은'답을 찾아 내는
문제들을 통칭해 최적화 문제라고 부른다. 예를 들면, n개의 원소 중에서 r개를 순서 없이 골라내는 방법의 수를 계산하는 것은 최적화 문제가 아니다.
우리가 원하는 답은 딱 하나밖에 없고, 더 좋은 답이나 덜 좋은 답이 없기 때문이다. 반면에 n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제,
아니면 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화하는 문제 등은 최적화 문제가 된다.
최적화 문제는 우리의 생활과 아주 밀접하게 관련되어 있다. 인공지능(젠장 알파고), 생명공학, 자동차 디자인에 이르기까지 컴퓨터가 하는
많은 작업들이 최적화 문제로 표현된다. 최적화 문제를 해결하는 방법은 여러 가지가 있으며, 그 중 가장 기초적인 것이 완전 탐색이다.
완전 탐색은 최적화 문제를 풀기위한 가장 직관적인 방법이다. 가능한 답을 전부 구하고 그 중에서 가장 좋은 답을 고르면 되기 때문이다.