재귀함수 트리구조 가지치기(Pruning)
1. 가지치기란?
가지치기(Pruning)는 재귀(Recursion)나 백트래킹(Backtracking)으로 가능한 모든 경우를 탐색할 때, 정답이 될 가능성이 없는 분기(가지)를 탐색 트리에서 미리 잘라내어 시간과 메모리를 절약하는 기법이다.
재귀 호출은 겉으로는 “함수가 자기 자신을 부르는 것”처럼 보이지만, 실제로는 “선택의 연쇄”로 인해 탐색 트리가 만들어진다.
•
루트(root): 시작 상태
•
노드(node): 현재까지의 선택을 반영한 부분 상태(partial state)
•
자식(child): 다음 선택을 한 번 더 적용한 상태
•
잎(leaf): 목표 깊이/목표 길이에 도달한 완성 해
각 레벨에서 선택지가 B개이고 깊이가 D라면, 탐색 수는 대략 수준으로 증가한다. 따라서 “끝까지 내려가서 실패를 확인하는 방식”만으로는 시간 제한을 넘기기 쉬우며, 불가능하거나 불필요한 가지를 가능한 한 빨리 제거하는 전략이 필요해진다.
2. 가지치기의 핵심 아이디어
가지치기의 핵심은 아래 한 문장으로 요약할 수 있다.
•
“현재 상태에서 앞으로 어떤 선택을 하더라도 정답이 될 수 없다면, 더 내려가지 않는다.”
여기서 중요한 것은 “현재 상태”와 “앞으로 어떤 선택을 하더라도”이다.
•
가지치기는 완성된 해가 아니라, 현재까지 만든 부분해를 기준으로 판단한다. (예: 지금까지 만든 문자열의 접두사, 현재 합, 현재 비용, 현재 배치 상태)
•
가지치기 조건은 반드시 안전해야 한다. 즉, 조건이 참이면 그 아래에는 정답이 존재하지 않음이 논리적으로 보장되어야 한다. 그렇지 않으면 정답을 포함한 가지를 잘라버리는 치명적인 오류가 된다.
3. 가지치기가 성능에 미치는 영향
가지치기는 코드를 “빠르게 만드는” 기법이라기보다, 탐색 자체의 크기를 줄여서 실행 가능성을 바꾸는 기법이다.
•
방문 노드 수 감소
•
재귀 호출 횟수 감소
•
불필요한 상태 저장(배열/문자열 변경) 감소
같은 백트래킹 코드라도 가지치기 조건 하나로 탐색 공간이 수십 배, 수백 배까지 줄어드는 일이 흔하다.
4. 구현 관점에서의 가지치기 유형
가지치기는 코드에서 크게 두 가지 형태로 자주 나타난다.
4.1. 진입 차단 방식(Prevention)
“선택하기 전”에 조건을 검사하여 애초에 그 분기로 들어가지 않게 막는 방식이다.
•
반복문에서 조건을 확인하고 continue로 건너뛴다.
•
장점: 불필요한 재귀 호출 자체가 발생하지 않는다.
•
단점: 조건이 복잡해지면 반복문이 지저분해질 수 있다.
4.2. 조기 종료 방식(Early Return)
함수에 “일단 들어온 뒤” 현재 상태를 검사하여 더 진행할 가치가 없으면 즉시 return 하는 방식이다.
•
장점: 조건을 함수 초입에 모아 관리하기 쉬운 경우가 많다.
•
단점: 호출은 이미 발생했기 때문에, 진입 차단보다 오버헤드가 약간 있다.
둘 중 무엇이 정답인지는 상황에 따라 다르며, 보통 “선택하기 전에 판단 가능한가”가 기준이 된다.
5. 가지치기 조건을 만드는 사고법(대표 패턴)
가지치기 조건은 대개 다음 세 가지 방향에서 만들어진다.
5.1. 제약 조건(Constraint) 기반
문제에서 금지된 조건이 있으면, 그 조건을 만족하는 순간 더 내려가면 안 된다.
•
특정 접두사 금지
•
인접 조건(연속 중복 금지 등)
•
중복 사용 금지(visited)
•
배치/충돌 금지(N-Queen의 행/열/대각선 충돌 등)
5.2. 목표 도달 가능성(Feasibility) 기반
“지금 상태에서 남은 선택을 다 해도 목표를 채울 수 있는가?”를 따져서 불가능하면 자른다.
•
남은 칸 수로 최소 요구 조건을 채울 수 없음
•
남은 값들을 더해도 목표에 도달 불가
•
반대로 현재 값이 이미 목표를 초과했고(모든 값이 양수 등), 앞으로 더 진행하면 더 나빠짐
5.3. 최적화 문제에서의 상한/하한(Bound) 기반
최소 비용/최대 점수와 같은 최적화에서는 “현재까지의 값 + 남은 구간의 최선(또는 최악) 추정치”를 이용한다.
•
더 좋아질 가능성이 없으면 탐색을 중단한다.
•
이 아이디어는 분기 한정법(Branch and Bound)의 핵심이다.
6. 예제 1: 특정 접두사(A로 시작)를 제외한 조합 생성
다양한 A, B, C 세 종류의 카드를 가지고 있다. 이 중 3장을 뽑을 때 모든 조합을 출력하라. 단 A로 시작하는 조합은 제외한다.
6.1. 가지치기 방법 1: 진입 차단 방식(Prevention)
#include <iostream>
char path[5] = "";
void test(int level)
{
if (level == 3)
{
std::cout << path << std::endl;
return;
}
for (size_t i = 0; i < 3; i++)
{
// Level 0에서 'A'를 아예 선택하지 않는다.
if (level == 0 && ('A' + i) == 'A')
continue;
path[level] = 'A' + i;
test(level + 1);
path[level] = 0;
}
}
C++
복사
실행 흐름(개념):
•
Level 0에서 A는 건너뛰고 B, C만 내려간다.
•
따라서 A로 시작하는 모든 가지가 통째로 제거된다.
6.2. 가지치기 방법 2: 조기 종료 방식(Early Return)
#include <iostream>
char path[5] = "";
void test(int level)
{
// 예시 규칙: 연속된 같은 문자가 2개 나오면 즉시 종료
if (level >= 2 && path[level - 2] == path[level - 1])
return;
if (level == 3)
{
std::cout << path << std::endl;
return;
}
for (size_t i = 0; i < 3; i++)
{
path[level] = 'A' + i;
test(level + 1);
path[level] = 0;
}
}
C++
복사
이 방식은 “선택을 반영한 뒤에야 판단 가능한 규칙”에 적합하다.
7. 예제 2: 중복 없이 카드 3장 뽑기(visited)
내장의 카드 중 한 번 뽑았던 카드는 다시 뽑지 않고, 3장만 뽑는 경우를 만든다.
중복 없는 순열/조합을 만들 때 가장 흔하게 쓰는 가지치기는 “이미 사용한 원소는 다시 사용하지 않는다”는 규칙이다. 이를 위해 visited 배열을 이용한다.
#include <iostream>
char path[5] = "";
int visited[5] = {}; // 0: 미사용, 1: 사용중
void test(int level)
{
if (level == 3)
{
std::cout << path << std::endl;
return;
}
for (size_t i = 0; i < 4; i++) // A, B, C, D
{
if (visited[i] == 1)
continue;
visited[i] = 1;
path[level] = 'A' + i;
test(level + 1);
path[level] = 0;
visited[i] = 0;
}
}
C++
복사
핵심 정리:
•
진입 차단: 애초에 선택하지 않고 넘어간다(continue).
•
조기 종료: 들어온 뒤 조건을 확인하고 즉시 종료한다(return).
•
visited: 중복을 제거해 탐색 공간 자체를 줄인다.
8. “강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고,
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,
•
질문할 곳도 없고,
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.
문제는 연습이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
9. 그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
자신의 힘으로 코드를 끝까지 작성하는 경험
10. 지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기
또는 카카오톡 상담방: 얌얌코딩 상담방