- 1. Problem
- 2. My Approach
- 3. Implementation
- 4. Textbook Approach
- 5. Implementation
- 6. Analysis
- 7. Feedback
1. Problem
2. My Approach
- 입력된 input은 주어진 그림과 같이 quadtree로 나타낼 수 있다.
- 주어진 연산을 처리하는 것은 다음과 같다.
- 부모노드(‘x’)의 자식 노드들의 순서를 바꿔준다. (s1, s2, s3, s4) –> (s3, s4, s1, s2)
- 위의 연산을 하위 노드부터 Bottom-up 접근으로 진행한다.
- input으로 받아들여진 문자열 중 x가 등장하면 이전 4개의 원소는 x에 귀속된다.
- 따라서 input의 순서를 뒤집으면 x가 등장하면 이후 4개의 원소가 x에 귀속된다.
3. Implementation
- string 타입의 stack을 생성한다.
- input의 뒷부분부터 각 원소를 stack에 넣어준다.
- x가 등장하면 stack 상단의 원소들(위에서 순서대로 s1,s2,s3,s4)을 꺼내 x의 값에 순서대로 붙여주어 귀속시킨다(x+=s3+s4+s1+s1).
- 수정된 값을 stack에 넣어준다.
- 다음 index부터 다시 반복.
for(long i=input.size()-1;i>=0;i--){
if(input.at(i) != 'x'){
output.push(input.substr(i,1));
}
else{
string q1 = output.top(); output.pop();
string q2 = output.top(); output.pop();
string q3 = output.top(); output.pop();
string q4 = output.top(); output.pop();
string x = "x" + q3 + q4 + q1 + q2;
output.push(x);
}
}
4. Textbook Approach
- 본래 이 문제는 같은 연산을 반복적으로 진행하면서 상향식 또는 하향식으로 분할하여 접근 한다는 점에서 재귀적으로 생각해 볼 수 있다.
- input의 앞에서 부터 순차적으로 접근하면서 순서를 바꾸는 함수 reverse()를 호출한다.
- reverse( ) :
- reverse( ) 는 현재 위치의 값이 b나 w일 때 해당 값을 반환한다.
- reverse( ) 는 현재 위치의 값이 x면 4번의 reverse() 호출로 순차적으로 다음 4개의 원소를 구한다.
- 귀속시키려는 4개의 원소중에 x가 또 등장하면 2번 연산이 다시 재귀적으로 동작한다.
5. Implementation
string reverse(string::iterator& it){
char ch = *it;
it++;
if(ch == 'b')
return "b";
if(ch == 'w')
return "w";
string s1 = reverse(it);
string s2 = reverse(it);
string s3 = reverse(it);
string s4 = reverse(it);
return "x"+s3+s4+s1+s2;
}
- input의 iterator를 parameter로 받아 사용한다는 점에 주목하자. 단순히 int index를 사용하여 접근해도 되지만 다양한 접근 방법을 알고 있으면 그만큼 다양한 구현 방법도 생각할 수 있을 것으로 여겨진다. 호출되는 재귀함수간의 인과관계가 좀 더 복잡한 경우에 유용할 것으로 생각된다.
6. Analysis
- 채점결과 책의 코드(4ms)가 본인의 코드(12ms)보다 더 빠른 것으로 나타났다.
- 그러나 본인의 코드는 단순 for문으로 시간복잡도는 O(n)이 되고, 책의 코드 역시 중복을 처리하지 않기 때문에 재귀함수가 n번 호출되므로 똑같이 O(n)의 시간복잡도를 보인다. (stack에서 사용하는 연산으로 인해 실제 소요시간에서 약간의 차이가 발생한 것으로 보인다.)
- 본 문제나 모든 경우의 수를 구하는 경우, 재귀함수는 중복을 처리하지 않으면 시간소모를 효과적으로 줄일 수 없다.(이 부분에 대해선 후에 동적계획법을 사용하는 문제에서 자세히 다뤄보기로 한다)
7. Feedback
- 본 문제는 다른 방식으로도 해결할 수 있었으나, 후에 재귀적 방법으로만 해결할 수 있는 문제를 위해서 재귀적 구조로 접근하는 방식을 익혀둘 필요성을 느꼈다.
- 본 문제 외에 재귀함수를 사용하는 몇 개의 문제를 풀어본 결과, 재귀함수의 구현은 분할 정복과 관련하여 몇가지 유형으로 나누어 접근할 수 있음을 느꼈다.
- 기저 사례(base case)는 주어진 범위의 끝 ‘무렵’에 도달했을 경우(start 또는 end)
- input의 처음과 나머지로 나누어 접근 또는 가운데를 기준으로 나누어 접근
- 다양한 문제를 풀어보면서 재귀함수 구현에 익숙해지자.