의식이 흐르는대로 해보는 프로그래밍

목차 접근 `n`개의 정점을 가는 이진 트리의 정점에서 1 ~ n까지 중복 없이 번호가 매겨져 있다. 이런 이진 트리에서 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제다. 정말 많이 틀리고, 시간이 들었다. 여러 개선점에 대해서 생각해보는 시간이었다. 먼저 기본적인 접근에 대해서 생각해보자. 중위순회는 이진트리를 Left - Mid - Right 순으로 탐색을 진행한다. 후위순회는 이진트리를 Left - Right - Mid 순으로 탐색을 진행한다. 그럼 맨 처음 주어진 각각의 순회의 결과에서 후위순회의 마지막 결과값이 처음 트리의 Mid의 값이라는 것을 알 수 있다. 그럼 아래와 같으 과정을 거치면, 트리를 재귀적으로 분해해나갈 수 있다. 위에서 구한 Mid..

접근 세상에나 중간에서 만나기라는 알고리즘이 있다는 것이 신기하다. 부분수열의 합은 고등학생 때 부분집합의 갯수를 구하는 공식을 떠올려보면 이해하기 쉽다. 고등학생 때 전체 집합의 원소의 갯수가 $ N $ 개라면, 부분집합의 갯수는 $ 2^N $이 되었다. 그런 이유는 공집합에 원소마다 [넣기 / 안넣기] 2가지의 선택권밖에 없었기에, $ 2 * 2 * ... * 2 = 2^N $으로 도출될 수 있는 것이다. 여기선 최악의 경우를 생각해보면, $ O(2^{40}) $의 시간복잡도가 나오게 된다. 중간에서 만나기는 이분 탐색과 분할 정복의 형태와 비슷하다. 이분 탐색은 매 탐색마다 $ N / 2 $ 를 수행해서 시간 복잡도가 log 단위로 나오는 반면, 중간에서 만나기는 처음 한번 $ N / 2 $ 수행하..