무식하게 풀기

알고리즘 문제를 풀 때 공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽다. 

 

이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 스스로에게 물어보자. 무식하게 풀 수 있을까?

 

흔히 전산학에서 무식하게 푼다 (brute force)라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 가리켜 흔히 완전탐색(exhaustiive search)라고 부른다.

 

완전 탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법이다. 컴퓨터의 최대 장점은 결국 속도가 빠르다는 것이기 때문이다.

특히 현실세계의 문제 중에는 입력의 크기가 작아 컴퓨터가 처리하기에는 별것 아니지만 손으로 직접 풀기에는 경우의 수가 많은 경우가 종종 있는데, 이럴 때 완전 탐색은 충분히 빠르면서도 가장 구현하기 쉬운 대안이 된다.

 

재귀 호출

컴퓨터가 수행하는 많은 작업들은 대개 작은 조각들로 나누어 볼 수 있다. 인터넷에서 물건을 구매하는 작업은 카드회사에 정보를 보내기, 데이터베이스 갱신, 결제 완료 이메일 보내기 등으로 나눌 수 있고, 문자열의 길이를 세는 작업은 첫 한글자를 세기, 다음 한 글자 세기..라는 조각들로 나눌 수 있다.

 

우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있다. 완전히 같은 코드를 반복해 실행해야하는 for문 같은 반복문이 좋은 예이다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀함수(recursive function), 혹은 재귀 호출(recursion)이다. 

 

재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다. 이렇게 들으면 꽤나 쓸데없이 보이지만 재귀 호출은 다양한 알고리즘을 구현하는데 있어 매우 유용하게 사용할 수 있는 도구이다. 

 

자연수 n이 주어졌을 때 1부터 n까지의 합을 반환하는 함수를 재귀로 구현해보자.

 

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

 

n개의 숫자의 합을 구하는 작업을 n개의 조각으로 쪼개, 더할 각 숫자가 하나의 조각이 되도록 하자. 재귀 호출을 이용하기 위해서는 이 조각중 하나를 떼내어 자신이 해결하고, 나머지 조각들을 자기 자신을 호출해 해결해야한다. 이 조각 중에서 n만 따로 빼내기로 하자.  그러면 1부터 n-1까지의 조각이 남는데 이들을 모두 처리한 결과는 다름아닌 1부터 n-1까지의 합니다. 따라서 자기 자신을 호출해 n-1까지의 합을 구한뒤, 여기에 n을 더하면 우리가 원하는 답이된다.

 

recursiveSum의 첫줄에 있는 if문에 주목하자. 이 조건문이 없으면 이 함수가 제대로 동작하지 않을 것은 자명하다. n=1이면 조각이 하나뿐이니, 한개를 빼고 나면 더이상 처리할 작업이 없다.

 

모든 재귀 함수는 이와 같이 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다.

 

이 때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례(base case)라고 합니다.

기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경써야한다. 만약 recursiveSum()에서 n이 1인 경우를 확인하는 것이 아니라 n이 2인지 확인하고, 2라면 3을 반환한다고 가정해보자. 이렇게 구현하더라도 입력이 2이상이면 아무문제 없이 답을 모두 계산할 수 있지만 1이 입력으로 들어오면 문제가 생기게 된다.

 

재귀 호출은 기존에 반복문을 사용해 작성하던 코드를 다르게 짤 수 있는 방법을 제공해준다. 이 함수에서는 기존의 코드에 비해 재귀 호출을 통해 얻을 수 있는 별다른 이득이 없지만, 문제의 특성에 따라 재귀 호출은 코딩을 훨씬 간편하게 해줄 수 있는 강력한 무기가 된다.