재귀함수 트리구조 가지치기(Pruning)
가지치기란?
기본적인 재귀 함수 호출 시 특정 return 조건을 추가하여 진입하지 않을 조합을 줄이고, 인위적으로 막아주는 것이 있다.
나무의 가지를 자르는 것처럼, 불필요한 재귀 호출을 미리 차단하여 효율성을 높이는 기법다양한 ABC 세종류의 카드를 가지고 있다. 이 중 3장을 뽑을 때 모든 조합을 출력하라.
단 A로 시작하는 조합은 제외 시킨다.
시작
/ | \
A B C (Level 1)
/|\ /|\ /|\
X ... ... (Level 2) ← A로 시작하는 가지를 X로 차단
/|\ /|\ /|\
... ... ... (Level 3)
Plain Text
복사
가지치기 방법1: 진입 차단 방식 (Prevention)
애초에 들어가지도 않게 막는 방법•
continue를 사용해서 반복문에서 해당 경우를 건너뛴다
•
장점: 메모리와 시간을 아예 사용하지 않음
•
단점: 조건이 복잡해질 수 있음
#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'(i==0)인 경우 아예 건너뛰기
if (level == 0 && ('A' + i) == 'A')
continue; // 다음 i로 넘어감 (B, C만 시도)
path[level] = 'A' + i; // 현재 레벨에 문자 저장
test(level + 1); // 다음 레벨로 재귀 호출
path[level] = 0; // 백트래킹: 원상복구
}
}
C++
복사
실행 과정 예시:Level 0: A는 continue로 건너뛰고, B와 C만 시도
├─ B 선택 → test(1) 호출
│ ├─ BA, BB, BC 생성
└─ C 선택 → test(1) 호출
├─ CA, CB, CC 생성
Plain Text
복사
가지치기 방법2: 조기 종료 방식 (Early Return)
일단 들어가긴 했는데, 조건 확인 후 바로 나가는 방법•
return을 사용해서 함수를 즉시 종료
•
장점: 복잡한 조건도 함수 내에서 처리 가능
•
단점: 이미 함수에 진입했으므로 약간의 오버헤드 존재
#include <iostream>
char path[5] = "";
void test(int level)
{
// 💡 핵심: 연속된 같은 문자가 2개 나오면 즉시 종료
// level-2와 level-1 위치의 문자가 같으면 패턴 위반
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++
복사
실행 과정 예시:"AA?" 패턴 시도:
├─ Level 0: A 저장
├─ Level 1: A 저장
└─ Level 2: 진입 → level>=2 조건 체크 → path[0]=='A', path[1]=='A'
→ 같으므로 return으로 즉시 종료!
Plain Text
복사
내장의 카드 중 한번 뽑았던 카드는 사다 안뽑고, 세장만 뽑는 경우
중복 없는 조합 만들기 - visited 배열 활용카드가 사용 되었는지 사용 되지 않았는지 중복체크 해주기 위한 배열 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 4장 중에서
{
// 💡 이미 사용중인 카드면 건너뛰기
if (visited[i] == 1)
continue;
// 📌 카드 사용 시작
visited[i] = 1; // 사용 표시
path[level] = 'A' + i; // 경로에 저장
test(level + 1); // 다음 레벨로
// 🔄 백트래킹: 원상복구 (다른 조합을 위해)
path[level] = 0; // 경로에서 제거
visited[i] = 0; // 사용 해제
}
}
C++
복사
visited 배열 동작 원리:초기: visited = [0, 0, 0, 0] (A, B, C, D 모두 사용 가능)
Level 0에서 A 선택:
├─ visited = [1, 0, 0, 0] ← A 사용중 표시
├─ Level 1에서 B 선택: visited = [1, 1, 0, 0]
├─ Level 2에서 C 선택: visited = [1, 1, 1, 0] → "ABC" 완성!
├─ 백트래킹으로 Level 1로 돌아가며: visited = [1, 0, 0, 0]
└─ Level 1에서 C 선택: visited = [1, 0, 1, 0] → "ACB" 시도...
Plain Text
복사
핵심 포인트:•
방법1: 애초에 안 들어가게 차단 (continue)
•
방법2: 들어갔다가 조건 맞으면 나가기 (return)
•
visited: 중복 사용 방지를 위한 상태 관리 배열
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고,
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,
•
질문할 곳도 없고,
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.
문제는 ‘연습’이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기 또는 카카오톡 상담방: 얌얌코딩 상담방