반복문을 통해 완전탐색을 구현하지 못하는 대표적인 예로 순열, 조합이 있습니다.
단계별 예시를 통해 천천히 반복문의 한계를 극복해봅시다.
순열 혹은 조합을 코드로 구현하는 상황을 떠올려봅시다.
조합은 서로 다른 N개 중 K개를 순서에 상관없이 선택하는 것을 뜻합니다.
순열은 조합의 정의에서 순서를 고려해서 경우의 수를 뽑아냅니다.
만약 알파벳 A, B, C, D, E 5개 중 2개를 중복해서 순서에 상관 있게 뽑는다고 하면,
AA, AB, AC, AD, AE, BA, BB, BC, BD, BE, CA, CB, CC, CD, CE, DA, BC, BC, DD, DE, EA, EB, EC, ED, EE 로 총 25가지 경우가 존재합니다.
찾아낸 경우들을 문장으로 풀어쓴다면 다음과 같겠죠.
첫 번째 자리에 A ~ E 중 하나의 알파벳을 고르고,
두 번째 자리에 A ~ E 중 하나의 알파벳을 고른다.
이를 코드로 구현할 때, 반복문을 이용한다면 머리 아프지 않게 작성할 수 있습니다.
각 자리에 5가지 알파벳을 바꿔가면서 대입한 것으로 볼 수 있기때문에
하나의 자리당 반복문이 하나 있으면 코드 작성이 끝납니다.
for(char first='A'; first<='E'; first++){
for(char second='A'; second<='E'; second++){
printf("%c%c ", first, second);
}
}만약 알파벳 A, B, C, D, E 5개 중 2개를 중복없이, 순서에 상관없이 뽑는다고 하면,
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE 로 총 10가지 경우가 있습니다.
찾아낸 경우들을 문장으로 풀어쓴다면 다음과 같겠죠.
첫 번째 자리에 A ~ E 중 하나의 알파벳을 고르고,
두 번째 자리에 A ~ E 중 첫 번째 자리에서 선택하지 않은 하나의 알파벳을 고른다.
앞서 살펴본 예제에서 중복을 제외하는 로직을 코드에 추가해야합니다.
10가지 경우를 펼쳐놓은 것을 보면 두 번째 알파벳은 첫 번째 알파벳의 다음 알파벳부터 시작하는 규칙을 알 수 있습니다.
for(char first='A'; first<='E'; first++){
for(char second=first+1; second<='E'; second++){
printf("%c%c ", first, second);
}
}여기까지는 몸풀기 예제였고, 본격적으로 다음 예제를 살펴봅시다.
만약 알파벳 A, B, C, D, E 5개 중 K개를 중복없이 순서에 상관없이 뽑는다고 하면,
5Ck 총 5! / {k! x (5-k)!}가지 경우가 있습니다.
앞의 두 예제를 살펴봤을때, 자리 하나당 for문 하나를 사용하면 코드를 작성할 수 있었습니다.
해당 논리를 바탕으로 생각해본다면 현재 k개의 for문이 중첩된 코드가 필요합니다.
for(char first='A'; first<='E'; first++){
for(char second=first+1; second<='E'; second++){
...
for(char kth=(k-1)th; kth<='E'; kth++){
printf("%c%c...%c ", first, second, ..., kth);
}
...
}
}
# 문법적으로 틀린 코드입니다.만약 K가 1부터 5까지로 정해져있다면, 각각의 숫자에 맞게 for문을 중첩시키는 코드를 조건문을 통해 끔찍하게 구현할 수 있겠죠.
if(K==1){
for(char first='A'; first<='E'; first++){
printf("%c ", first);
}
}
else if(K==2){
for(char first='A'; first<='E'; first++){
for(char second=first+1; second<='E'; second++){
printf("%c%c...%c ", first, second, ..., kth);
}
}
}
else if(K==3){
...만약 K가 엄청나게 크다면? 범위가 엄청나게 넓다면? 모든 조건에 대한 for 중첩을 적을 수 없게되겠죠?
위와 같은 지저분한 코드를 정리하기 위해 재귀함수를 이용합니다.
K개의 중첩된 for문을 작성해야되는 상황에서 다시 침착하게 생각해봅니다.
K개의 중첩 또한 1개의 중첩에서부터 K개의 중첩까지 1씩 증가하는 모습을 보일 것 입니다.
중첩을 반복시킬 무언가가 필요한 상황인데, 이때 재귀함수를 사용하는 겁니다.
재귀함수 또한 반복문으로 생각할 수 있습니다.
# 재귀함수
func recursion(int i){
if(i==k) return;
else{
for(...){
recursion(i+1);
}
}
}
recursion(0);
# 반복문
for(int i=0;i<k;i++){
...
}재귀함수의 매개변수 초기값이 반복문의 초기값이라 볼 수 있고,
재귀함수의 기저조건이 반복문에서의 탈출 조건이고,
재귀함수의 재귀호출이 반복문의 증감식이 됩니다.
한 줄 이상의 코드를 반복시킬때에는 반복문을 사용하고,
한 겹 이상의 for문을 중첩시킬때에는 재귀함수를 사용합니다.
마지막 예제를 재귀함수를 통해 구현한 코드를 작성해보겠습니다.
func recursion(int i){
if(i==k){
for(int idx=0;idx<k;idx++){
printf("%c", data[idx]);
}printf(" ");
return;
}
else{
char prev='A';
if(i!=0) prev=data[i-1];
for(char alphabet=prev+1;alphabet<='E';alphabet++){
data[i]=alphabet;
recursion(i+1);
}
}
}
recursion(0);
# 문자열 저장을 위해 추가된 변수 data[]재귀함수 얘기가 나온김에 아주 쬐끔만 더 얘기 해보겠습니다.
재귀함수는 두 가지 의미로 작성 될 수 있습니다.
- 반복문, 중첩의 의미
- 구할 값
반복문, 중첩의 의미로 작성될 경우 순열, 조합, 그래프 등에 탐색의 목적으로 사용됩니다.
구할 값에 대한 의미로 작성될 경우는 주로 Divide and Conquer, Dynamic Programming에서 사용이 되죠.
따라서, 재귀함수는 추후 Dynamic Programming 에서 다시 한 번 언급이 될 예정입니다.
마무리
저번 시간에 이어 완전 탐색 구현 방법의 또 다른 방법인 재귀함수에 대해서 알아봤습니다.
완전 탐색 문제에서 for문을 통해 구현을 할 수 없는 경우인 K-for 상황에 대해 살펴봤습니다.
또한, 이를 구현하기 위해 "재귀함수를 어떻게 생각할 것인가?"에 대해 간략하게 알아봤습니다.
한 줄 이상의 코드를 반복시킬때에는 반복문을 사용하고,
한 겹 이상의 for문을 중첩시킬때에는 재귀함수를 사용합니다.
아직 효율성에 대한 얘기는 본격적으로 시작하지 않았지만,
짚고 넘어가야할 부분이 있어서 살짝만 언급하고 지나가겠습니다.
재귀함수를 이용한 탐색에 연관된 알고리즘 종류로는 Backtracking이 존재합니다.
완전 탐색에서 시간 효율을 벌기 위해 Promising, Pruning 이라는 기법을 사용합니다.
최종 탐색 단계까지 가지 않아도 탐색 과정에서 "이 길은 썩었다"라고 판단하고 되돌아가는 기법이죠.
길이 썩었다는 점을 초기에 알면 알수록 기존의 완전 탐색보다 시간 효율이 엄청나게 좋아지겠죠?
백트래킹 단어 정의에서 시작하는 이해
그림 예제를 통해 이해하는 백트래킹
Difference between backtracking and branch-and-bound
다음 시간 예고
지금까지 시간, 공간 제약이 없는 상태로 가정하고, 완전히 문제를 이해하는데에 집중했습니다.
현실의 문제는 제한 시간, 메모리 제한 등 제한이 많이 존재하죠.
무식한 방법을 거친 효율적 방법에 대해 하나씩 알아보도록 하겠습니다.
