Study with book/Algorithms

[백준]이진탐색트리


백준저지

[이진탐색트리]https://www.acmicpc.net/problem/2957



필자에 너무 어려웠던 문제이다. 이 문제를 풀기위해 3주를 고민했다.

어렵게 풀었던 만큼 이진탐색트리의 삽입, 삭제, 탐색은 확실하게 이해도가 많이 올라간 것 같아 기분이 좋다.

추가적으로 Map이란 STL사용법도 확실히 많이 익숙해진 듯하다.

 

[풀이]

기본적으로 이진탐색트리의 삽입의 성질과 위 문제의 의도를 정확하게 이해해야 풀 수 있는 문제이다.

root의 값보다 크면 오른쪽, root의 값보다 작으면 왼쪽

아마 처음 접근은 위 문제에서 수도코드로 짜여있는 예시대로 구현을 했을 것이다.

필자도 저 예시대로 재귀로 구현해도 해보고 반복으로 구현도 해보고 배열을 30만개 만들어서도 해보고...

결론은 이진탐색트리를 구현하는 방식으로 코딩을 했는데 전부 시간초과가 발생했다.

그 이유는 최악의 경우를 생각해보았을 때 30만개가 1부터 30만까지 차례대로 들어온다고 하면 O(N2)의 시간이 나온다. 1초안에 해결할 수 없는 시간이다.

1, 2, 3, 4의 숫자가 차례대로 들어온다고 생각하면,

1일 때 0번 비교

2일 때 1번 비교(1과 비교 후 1의 오른쪽에 삽입)

3일 때 2번 비교(1과 비교, 2와 비교 후 2의 오른쪽에 삽입)

4일 때 3번 비교(1과 비교, 2와 비교, 3과 비교 후 3의 오른쪽에 삽입)

, 1부터 30만까지 차례로 입력이 들어왔을 때 비교 횟수는

0+1+2+3+ + 299,999 = O(N2)이다.

이렇다는 것은 절대 일반적인 이진탐색트리의 방식으로 위 문제를 시간 내에 풀 수 없다는 것을 뜻한다.

즉 생각을 전환해야할 필요가 생긴다는 것인데, 문제는 C의 값만을 출력하길 원하고 있다.

C의 값은 이진트리에 삽입이 될 때 누적된 높이의 값을 뜻한다.

필자는 이진트리를 만드는 일련의 과정을 탈피하고 이진트리가 갖고 있는 성질문제가 원하는 결과 값(바로 C의 값)초점을 맞추어서 문제를 접근하기 시작했다.

 

그 결과 하나의 규칙을 발견할 수 있었는데 바로 어떠한 값 X“X보다 작은 값들 중 가장 큰 값의 오른쪽에 삽입이 되는 것“X보다 큰 값들 중 가장 작은 값의 왼쪽에 삽입되는 것이란 성질이 있다는 것을 발견했다.

사실 위 문제를 풀기위해 입력된 X가 어떤 트리의 오른쪽 서브트리인지 왼쪽 서브트리인지 알 필요조차 없다. 그냥 입력된 값과 높이를 저장하는 자료구조를 사용하고, 입력한 값 X보다 작은 값들 중 가장 큰 값의 높이입력한 값 X보다 큰 값들 중 가장 작은 값의 높이를 구해서 비교한 뒤 더 큰 높이에 1을 추가해서 자료구조에 삽입하면 끝이다.

 

왜 위와 같은 원리가 적용이 되는 것일까?

바로 이진트리의 성질 중에 있다. 트리에 35가 삽입되어 있다고 하자. 이 상태에서 4가 입력이 되었다고 하자. 4는 어디에 삽입이 될까? 그렇다. 3의 오른쪽 혹은 5의 왼쪽에 삽입이 된다. 그럼 여기서 더 나가보자.

만약 3이 먼저 삽입되고 5가 삽입되었다고 하자. 그럼 4는 어디에 삽입이 될까? 맞다. 5의 왼쪽에 삽입된다.

그럼 반대로 5가 먼저 삽입되고 3이 삽입되었다고 하자. 그럼 4는 어디에 삽입될까? 그렇다. 3의 오른쪽에 삽입이 된다.

슬슬 눈치를 챘을 것이라고 믿어 의심치 않는다.

바로 43의 오른쪽에 삽입 되는가 혹은 5의 왼쪽에 삽입되는 가를 결정하는 것은 누가 먼저 삽입되었는가에 달려있고 또 다른 말로 하게 되면 어느 것의 높이가 더 높은가라고 말할 수 있다.

다른 숫자로도 연습장에 그려보길 바란다. 필자가 생각한 원리가 그대로 적용될 것이라 생각한다.

즉 위 내용을 일반화해보면 아래와 같다.

입력된 X의 값보다 작은 것들 중 가장 큰 것의 높이입력된 X의 값보다 큰 것들 중 가장 작은 것의 높이를 비교한 후 높이가 큰 것에 +1을 한 것이 입력된 X의 높이가 된다.

 

자 푸는 방식은 알았다. 그렇다면 구현을 해보자.

사실 구현하는 것도 만만치 않다. “입력된 X보다 작은 값들 중 가장 큰 것입력된 X보다 큰 값들 중 가장 작은 것을 구하는 것이 솔직히 간단한 작업은 아니라고 생각한다.(적어도 필자 입장에서는...)

그래서 필자는 균형 잡힌 이진트리와 스레드 이진트리를 이용해서 문제를 풀어볼까 생각했는데

C++STL에 분명 입력하면 정렬된 상태로 저장되고,

입력된 값의 바로 앞의 값과 바로 뒤의 반복자를 return해주는 STL이 있을 것이라 생각했고 구글링에 들어갔다.

바로 map이라는 것이 필자가 찾는 STL이었다!

 

[구현]

map STL의 설명을 보면 자세히 알 수 있겠지만 간략하게 필자가 이용한 함수를 설명하겠다.

lower_bound(key)란 함수는 매개변수 key요소를 가지고 있다면 해당 위치의 반복자를 반환한다.

key요소의 이전 반복자를 반환하는 것이 없어서 (--m.lower_bound(in))식으로 이전 반복자를 반환하게 하였다.

upper_bound(key)란 함수는 매개변수 key요소를 가지고 있다면 해당 위치의 다음 위치 반복자를 반환한다.

lower_bound()upper_bound()map의 범위에 벗어나는 곳을 접근할 때 Runtime Error가 발생했다.

예를 들어 (1,2) (2,3)map에 삽입할 때 upper_bound(2)를 하면 다음 위치 반복자가 없으므로 Runtime Error가 발생했다.

line14: 그래서 필자는 백준 문제에서 범위가 1<=N<=30만이므로 map(0,-1)(3000001, -1)을 먼저 삽입한 뒤 Runtime Error의 발생을 막았다.

line22: lower_boundupper_bound를 통해 높이를 구한 뒤 max값+1을 하고

line24: mapArr에 삽입을 하였다.

추가적으로 위 문제를 접하면서 cin & coutscanf & printf의 입출력 시간 차이가 있다는 것을 깨달았다.

아래 코드에서 입출력을 cin & cout으로 바꾸면 시간초과가 나는 현상이 발생했다.

#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

int main(void) {
	int num;
	long long int C = 0;
	map<int, long long int> mapArr;
	map<int, long long int>::iterator lower_bound;
	map<int, long long int>::iterator upper_bound;

	mapArr.insert(pair<int, long long int>(0, -1));
	mapArr.insert(pair<int, long long int>(300001, -1));
	scanf("%d", &num);

	for (int i = 0; i < num; i++) {
		int in; scanf("%d", &in); long long int dep = 0;
		lower_bound = (--mapArr.lower_bound(in));
		upper_bound = (mapArr.upper_bound(in));
		dep = max(lower_bound->second, upper_bound->second) + 1;
		
		mapArr.insert(pair<int, long long int>(in, dep));
		C += dep;
		printf("%lld\n", C);
	}

	return 0;
}


'Study with book > Algorithms' 카테고리의 다른 글

[백준]피보나치 함수  (3) 2017.03.11
[백준]K번째 수  (0) 2017.01.13
[백준]트리  (2) 2017.01.02
[백준]힙 정렬  (0) 2016.12.30
[백준]2xn 타일링2  (0) 2016.12.23