bracket problem 재귀 예시
2020. 11. 22. 03:45ㆍ카테고리 없음
이 문제는 재귀함수 문제입니다.
입력한 n에 대해, n 쌍의 bracket pairs를 생성하는 문제입니다.
bracket problem에 대해서 얘기하기 전에,
어떤 전체적인 problem 즉, 문제상황에 대해서 생각 해 봅시다.
모든 전반적인 problem을 포괄 할 수는 없으니, 이런 bracket problem에 대해서 생각해봅시다.
1. 주어진 bracket string이 올바른 bracket string인지 "검사".
2. 주어진 bracket string을 올바른 bracket string으로 "변환" (transform)
3. 올바른 bracket string을 생성.
과거를 되짚자면,
1.은 주어진 bracket string을 stack에 넣어서 검사.
2.는 재귀적으로 Doubly Linked List를 이용해서 주어진 bracket string을 DLL에 집어넣고,
새로운 DLL을 생성해서 변환.
3.은 사실 뭘 사용하든 상관이 없는데, 재귀적인 방법이 가장 좋다고 생각되는 이유는 Path problem이 생각났기 때문입니다.
<Path Problem>
이 Path Problem을 보면 알다시피, 처음 시작할 때, 두가지 경우로 나뉘는 점입니다.
return NumPaths(row+1,col,n) + NumPaths(row,col+1,n);
우리의 이 3번 Problem도 같은 시작점을 지닙니다.
시작을 {로 시작하던지, 혹은 }로 시작하던지가 나뉘는 분기점이니, 이도 재귀적으로 유사할 수 있습니다.
<용어>
Base Case = 재귀의 종료 지점
General Case = 재귀의 반복 지점
Smaller Casing = 재귀의 General Case가 올바르게 Case들을 소거하며 Base Case로 다가가고 있는가.
그렇다면 Base Case는 무엇일까?
코드에도 남겨놓았지만, 정상종료와 비정상종료 지점이 존재한다.
정상종료는, index가 size에 도달 했을 때, balance 즉, { 와 } 의 balance가 같으면 정상 종료입니다.
비정상종료는, index가 size에 도달 했으나, balance가 0이 아닙니다.
또는,
이것은 효율성을 따지기 위함인데,
생각을 해보면, 4자리가 있을 때, {{{ 라고 벌써 이미 생성했다면,
이미 실패한 bracket string이므로, 이 조건은 버려야 합니다.
#include <iostream>
#include <vector>
using namespace std;
class bracketProblem{
private:
int size;
vector<char> temp;
//Using STL as we dont know how many complete cases are present.
vector<vector<char>> result;
public:
explicit bracketProblem(int n):size(n*2){
temp.resize(n*2);
}
void print(){
out('{',1,1);
out('}',1,-1);
for(const vector<char> &vec1 : result){
for(char ch: vec1){
cout << ch;
}
cout << endl;
}
//User could unlock this comment to see how many cases are present.
//cout << result.size() << endl;
}
void out(char bracket,int index, int balance){
temp[index-1] = bracket;
if(index == size){ //base case
if(balance == 0){ // complete terminate
//i.e.) if n = 2, {{}} case
result.push_back(temp);
}else{ // balance != 0 // incomplete terminate
//i.e.) if n = 2 , {{{} case
return;
}
}else if(size - index < abs(balance)){ //incomplete terminate
// in this condition, none of trials are leading to complete terminate.
// i.e.) if n = 2 , {{{ case.
return;
}else{
out('{',index+1,balance+1);
out('}',index+1,balance-1);
}
}
};
int main() {
cout << "Console in one integer : ";
int n;
cin >> n;
cout << endl;
bracketProblem case1(n);
case1.print();
return 0;
}