문제 이해 단계
예전에 풀었던 문제다.. 근데 못 풀었다.
그때는 3일 걸려서 풀긴 했었는데, 이번에는 풀지도 못했다.
블로그까지 써가면서 풀자고 했는데 못 풀었다.
예전에 했던 풀이는 아래 링크를 걸어두겠다.
문제에 대한 설명 같은 것은 아래 링크를 참고해 주길 바란다.
https://howudong.tistory.com/17
[C++] 백준 5639 - 이진 검색 트리
문제 이해 단계 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있
howudong.tistory.com
문제 접근 단계
두 번째 풀이 방법은 첫 번째 방법보다는
좀 더 논리적인 방법이라고 할 수 있다.
첫 번째 방법은 솔직히 구현 방식에 가깝다.
map 컨테이너를 사용하여 전위순회로 들어온 노드의 관계를 연결한 후,
후위 순회에 연결한 것이다.
하지만 두 번째 방법은
전위 순회의 입력을 그대로 이용하여 후위 순회에 이용한다.
아래와 같이 전위 순회로 나온 출력 순서를
하나의 배열로 담는다고 생각해 보자.
예제 케이스를 그대로 사용하겠다.
해당 순서대로 전위순회가 출력된다.
전위 순회는 루트 → 왼쪽 노드 → 오른쪽 노드로 순회한다.
그렇기 때문에 가장 앞에 있는 노드인 루트 노드 관점에서 보자.
50보다 큰 수가 나올 때까지는 전부 왼쪽 노드이다.
왼쪽보다 큰 수가 나오면 그때부터 오른쪽 노드가 된다.
큰 뭉탱이로 봐서 노드가 이렇게 3개밖에 없다고 가정하자.
그러면 노드 3개를 다 구했으므로,
이 3개의 노드로 후위 순회를 할 수 있다.
연두색 → 하늘색 → 주황색 순으로 하면 후위순회가 된다.
하지만 알고 있듯이 하늘색과 연두색은 서브트리이다.
즉, 트리들의 집합이라는 소리이다.
이 것도 루트, 왼쪽 노드, 오른쪽 노드로 분리를 할 수 있다.
이 안에서도 후위 순회가 가능하다는 소리이다.
이 순서를 어떻게 알아낼까?
사실 알 수 있다.
왜냐하면 위에 전위순회의 출력 순서가 나와있으니까
위에서 했던 것처럼 그대로 하면 된다.
즉 재귀함수로 똑같은 작업을 해주면 된다.
왼쪽 노드로 똑같은 작업을 해줘 보겠다.
회색으로 칠해져 있는 것은
지금 연산에 필요 없는 것이라 제외해 준 것이다.
이런 식으로 이 5개의 배열만 가지고
루트를 지정해 주고 똑같이 나눠주면 된다.
이렇게 계속해서 재귀함수를 반복해 주면 쉽게 구할 수 있다.
이제 문제 구현 단계로 넘어가 보자.
문제 구현 단계
// 후위 순회(시작 인덱스, 끝 인덱스+1(제외되는 것까지(exclusive)))
void post(int start, int end){
if(start >= end) return; // 두 수가 같아지며 종료
int root = node[start]; // root 노드의 번호
int delim = start+1; // 왼쪽 노드와 오른쪽 노드가 갈리는 인덱스
// root 노드보다 큰 노드를 발견하면 종료
while(delim < end){
if(root < node[delim]) break;
delim++;
}
post(start+1,delim); //(루트 노드+1 ~ 왼쪽 노드의 마지막 인덱스)
post(delim,end); // (오른쪽 노드의 시작 인덱스 ~ 끝)
cout << root << "\n";
}재귀함수를 호출하여 전위순회로 주어진 배열을
후위순회로 옮기는 post함수이다.
delim은 왼쪽 노드와 오른쪽 노드가 갈리는 인덱스를 찾아
왼쪽 노드와 오른쪽 노드를 구분하는 역할을 한다.
그리고 while문은 위에서 말했다시피
root노드보다 큰 노드를 찾을 때까지 왼쪽노드로 취급하기 위해 사용한다.
post를 통해 왼쪽 노드의 재귀함수 호출과
오른쪽 노드의 재귀함수 호출을 따로 해준다.
두 호출의 순서가 절대 바뀌면 안 된다.
무조건 왼쪽 노드가 먼저 호출되어야 한다.
왜냐하면 왼쪽 노드 -> 오른쪽 노드 순서이기 때문이다.
여기까지가 전체 설명의 끝이고,
이제 아래에 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
using namespace std;
int node[10001]; // 노드의 최대 개수
// 후위 순회(시작 인덱스, 끝 인덱스+1(제외되는 것까지(exclusive)))
void post(int start, int end){
if(start >= end) return; // 두 수가 같아지며 종료
int root = node[start]; // root 노드의 번호
int delim = start+1; // 왼쪽 노드와 오른쪽 노드가 갈리는 인덱스
// root 노드보다 큰 노드를 발견하면 종료
while(delim < end){
if(root < node[delim]) break;
delim++;
}
post(start+1,delim); //(루트 노드+1 ~ 왼쪽 노드의 마지막 인덱스)
post(delim,end); // (오른쪽 노드의 시작 인덱스 ~ 끝)
cout << root << "\n";
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int num;
int idx = 0;
while(cin >> num) node[idx++] = num;
post(0,idx);
}
시행착오
현타가 너무 심하게 온다. 저번에는 풀었던 문제를 이번에는 못 풀었다.
물론 아주 오래전에 푼 문제라고 쳐도, 그만큼 많은 문제를 풀었다.
그런데 전혀 발전하지 못했다고 생각하니 너무 자괴감이 든다.
나는 도대체 왜 공부를 했던 거지? 그냥 힘들다.
머리가 멍청한 건지, 컨디션이 안 좋은 건지는 모르겠다.
3일 정도 걸려서 푼 게 미련한 건지,
답을 본 게 미련한 건지는 모르겠지만 그냥 못 풀었단 것 자체가 힘들다.