재귀

 

Tree의 
높이 = level
가지개수 = branch 

 

재귀 [ path 포함 해서  경로저장 ]  )

 

     * path 배열을 사용해 지나간 경로를 저장 !

path 배열의 
인덱스 값 = 현재 level 
그 인덱스에 저장된 값 = 현재 branch 

    ex) 현재 level 0→1 로 갈 때 branch A를 거쳤다면, 

         path 배열의 0인덱스에 'A' 저장

    ex) 현재 level 1→2 로 갈 때 branch B를 거쳤다면, 

         path 배열의 1인덱스에 'B' 저장 

  * 같은 level의 새로운 branch 로 입장 할 때마다 덮어써서 갱신 됨 ! 

  * level 2에 도달할 때마다 배열값들(저장된 경로) 를 모두 출력 해내므로 갱신되도 상관 x

 

 

// 재귀 연습 
int path[10];	//path 를 둬서 함수진입 경로 표시		// path의 index = level, 값 = branch 
void abc(int level) {
	// level
	if (level == 2) {
		// level 2 에 도달 할 때마다 path 에 있는 것 모두 출력 
		for (int x = 0; x < level; x++) {
			cout << path[x] << " ";
		}
		cout << endl;
		return;
	}
	// branch
	for (int x = 0; x < 3; x++) {
		// branch 에 새로 입장할 때마다 path에 입력하기 
		path[level] = x + 1;		// 앞으로 들어갈 가지 (즉, x가 아닌 x+1) 를 입력  
		abc(level + 1);
	}
}
int main() {
	abc(0);
	return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------

 

예제 ) 4개 종류 카드 (A,B,C,D) 중 세개를 뽑는 경우의 수 (중복 O)

 설계 ) 카드종류 4개 → branch : 4

         뽑는개수 3개 → level : 3

 

 * branch 가 문자열이더라도, 함수인자로 넣지 말고, path 배열로 따로 저장 ! index로 번째 수 표현 ! 

char path[3];
void recur(int level) {
	//level
	if (level == 3) {
		for (int i = 0; i < 3; i++)
			cout << path[i];
		cout << endl;
		return;
	}
	//branch 
	for (int i = 0; i < 4; i++) {	// branch 가 문자여도 어떻게든 반복문으로 돌리기 !!!!!
		path[level] = 'A' + i;		// A,B,C,D 문자열 branch 를 path에 넣음 
		recur(level + 1);		// branch는 재귀에 함수인자로 같이 넣지 말고 
	}


}
int main() {
	recur(0);
	return 0;
}

 

 

예제2) n개의 주사위를 던졌을 때 나올 수 있는 경우의 수 모두 출력

설계) 주사위 개수 n개 →  level : n

        주사위 숫자종류 6개 →  branch : 6

 

//재귀 연습
// level = n  // branch = 6
int path[10];
void recur(int n,int level) {
	//level
	if (level == n) {
		for (int i = 0; i < n; i++)
			cout << path[i];
		cout << endl;
		return;
	}
	//branch
	for (int i = 0; i < 6; i++) {
		path[level] = i+1;
		recur(n, level + 1);
	}
}
int main() {
	int n;
	cin >> n;
	recur(n,0);
	return 0;
}

 

예제3) ooooo    oooox    oooxx ...............................xxxxx 까지 출력 

설계) 자릿수 5개  →  level : 5

        나올 수 있는 종류 ox 2개 →  branch : 2

 

//재귀 연습
// level = 5  // branch = 2 (o,x)
int path[5];
void recur(int level) {
	//level
	if (level == 5) {
		for (int i = 0; i < 5; i++) {
			if (path[i] == 0)
				cout << 'O';
			else
				cout << "X";
		}
		cout << endl;
		return;
	}
	//branch
	for (int i = 0; i < 2; i++) {
		path[level] = i;
		recur(level + 1);
	}
}
int main() {
	recur(0);
	return 0;
}

 

 

-----------------------------------------------------------------------------------------------------------------------------------

 

재귀 [ Used 포함 해서  사용 표시 ]  )  :  순열 (중복 x)

보통 level은 (총)개수, branch는 (카드)종류 나타냄

* path는 level을 index로 사용, 
  used는 branch를 index로 사용
path [level] :      경로 표시 → 개수를 맞춰서 출력하는 작업, 특정 level 에 도달하면 출력
used [branch] :   사용 표시 → 종류 중 어떤 것 사용했는지 표시 

 

 

예제)  A,B,C,D 카드 네장 중복 피하며 뽑기 

// Used 기본 연습 
// A,B,C,D 카드를 중복 없이 뽑기 
char path[10];	
int used[4];		// 중복을 피하기 위함 !!! 
void abc(int level) {
	// level = 3 
	if (level == 3) {
		cout << path << endl;
		return;
	}
	// branch - A,B,C,D 네가지 
	for (int x = 0; x < 4; x++) {
		if (used[x] == 1) continue;	// used가 1 (이미 중복되어있으면) : 다음 턴으로 넘긴다 
		used[x] = 1;
		path[level] = x + 'A';
		abc(level + 1);
		used[x] = 0;		// 해당 가지 빠져나오면, 다시 used 배열 비워주는 이같은 로직 필요 !!
	}
}
int main() {
	abc(0);
	return 0;
}

 

 

-----------------------------------------------------------------------------------------------------------------------------------

특정 경우 피해서 뽑기 !

예제)  A,B,C,D 카드 (중복순열)   - 단, c로 시작하는 경우 제외하고 뽑기 

  방법 1) 진입 후, 다시 back     : 지나온 경로 path의 0index가 c이면 백(return)

  방밥 2) 아예 진입 x              : 현재 level 이 0 이고, branch가 c라면 진입 x(continue)

1)  if (path[0] == 'C') return;
2)  if ((level == 0 && x + 'A' == 'C')) continue;

 * 아래 코드에서 적절히 주석 해제 해서 사용하기 

// A,B,C,D 카드 (중복 순열) but C로 시작하는경우 제외
char path[10];	
void abc(int level) {
	// level = 3 
	if (path[0] == 'C')return;		// 1) 다시 back : C를 통해 들어온 경로면 다시 return 해 back
	if (level == 3) {
		cout << path << endl;
		return;
	}
	// branch - A,B,C,D 네가지 
	for (int x = 0; x < 4; x++) {
		//if ((level == 0 && x + 'A' == 'C')) continue;	// 2) 아예 진입 X : 첫번째로 시작하는게 C이면 진입 x
		path[level] = x + 'A';
		abc(level + 1);
		
	}
}
int main() {
	abc(0);
	return 0;
}

 

예제)  A,B,C,D 카드 (중복순열)   - 단, B인 경우 제외 

 * 위와 비슷하지만, 시작이 B이지 않아도 되므로, 조건 조금 달라짐 !! 

// A,B,C,D 카드 (중복 순열) but 모든 경우에서 'B'는 제외
char path[10];	
void abc(int level) {
	// level = 3 
	if (path[level-1] == 'B' && level>0)return;	// 1) 다시 back : level -1  =  바로 직전 단계가 'B'일 경우 back
	if (level == 3) {
		cout << path << endl;
		return;
	}
	// branch - A,B,C,D 네가지 
	for (int x = 0; x < 4; x++) {
		if (x + 'A' == 'B') continue;	// 2) 아예 진입 X : B 브랜치면 진입 x
		path[level] = x + 'A';
		abc(level + 1);
		
	}
}
int main() {
	abc(0);
	return 0;
}

 

예제)  A,B,C,D 카드 (중복순열)   - 단, 연속해서 같은 카드 뽑지 않음 !! 

 * 위와 비슷하지만, 이전 단계 와 비교 하는 로직 !!! 

// A,B,C,D 카드 (중복 순열) but 모든 경우에서 'B'는 제외
char path[10];	
void abc(int level) {
	// level = 3 
	if (level >=2 && path[level-1]== path[level-2]) return;	// 1) 다시 back : path의 바로 전단계(level-1)와 전전단계(level-2) 가 같을 경우 => 다시 back 
	if (level == 3) {
		cout << path << endl;
		return;
	}
	// branch - A,B,C,D 네가지 
	for (int x = 0; x < 4; x++) {
		// branch 비교 
		//if (path[level - 1] == x + 'A' && level>0) continue;	// 2) 아예 진입 X :  path의 바로 전단계(level-1), 와 지금 진입하려는 branch (x + 'A')가 같으면, PASS
		path[level] = x + 'A';
		abc(level + 1);
		
	}
}
int main() {
	abc(0);
	return 0;
}