언어를 배우는 초기에 풀어볼 법한 아주 기초적인 문제라 포스팅하지 않으려 했지만 생각보다 정답 비율이 엄청 낮아서 작성하기로 했다.
단순하게 최솟값과 최댓값을 구하는 건 상당히 쉽다.
최솟값과 최댓값을 뜻하는 변수 두 개를 선언하고 전체 Data를 돌면서 각각 최솟값보다 작은 수가 나오면 갱신, 최댓값보다 큰 수가 나오면 갱신하면 끝이다.
이때 처음 변수 선언 시 팁이 될 수 있는 것은 최솟값 변수엔 가능한 최댓값보다 큰 값을, 최댓값 변수엔 가능한 최솟값보다 작은 값으로 초기화하는 것이다.
그래야 단 한 번이라도 갱신할 수 있으며 파이썬스럽게 선언하는 방법은 float('inf'), float('-inf') 이렇게 양의 무한대, 음의 무한대로 선언하는 것이다.
이걸 그대로 출력해도 inf, -inf로 나오기 때문에 편하게 무한대라 생각하면 된다.
문제를 푸는 코드는 먼저 C를 이용하여 앞서 설명한 방식대로 답을 구하는 방법과 파이썬의 함수를 이용하여 단 3줄로 구현하는 방법을 소개하겠다.
먼저 C 코드이다.
#include <stdio.h>
int main() {
int a,b,min=1000000,max=-1000000;
scanf("%d", &a);
for (int i = 0; i < a; i++) {
scanf("%d", &b);
if (min > b) {
min = b;
}
if (max < b) {
max = b;
}
}
printf("%d %d", min, max);
return 0;
}
원소는 -1000000 이상, 1000000 이하로 제한되어 있으므로 3번째 줄에서 딱 맞게 초기화했다.
그리고 5번째 반복문에서 원소를 하나씩 입력받으며 입력받은 값이 최솟값 변수보다 작다면 갱신, 최댓값 변수보다 크다면 갱신하고 결괏값을 출력하면 된다.
DP란 정해진 방식이 있는 게 아니라 큰 문제를 해결하기 위해 문제를 세분화시키고 각각 작은 문제를 해결하여 나온 값들을 이용하는 방식을 총체적으로 지칭하는 알고리즘이다.
따라서 이미 연산한 값을 이용함으로써 불필요한 연산을 줄일 수 있다.
이것의 대표적인 예시가 피보나치 수열이다.
매번 필요한 값을 연산하도록 구현할 수 있지만 DP를 활용하게 되면 획기적으로 연산 횟수가 줄어들기 때문에 더 많은 수열을 구할 수 있다.
다시 문제로 돌아와서 문제는 A란 수열에서 원소가 증가하는 부분 수열을 찾는 것이며 각 원소는 연속하지 않아도 된다.
해당 문제는 최장 증가 수열(Least Increasing Subsequence) 알고리즘으로 알려져 있으며 DP를 활용하는 기법이기도 하다.
문제의 조건은 다음과 같다.
수열 A의 크기는 1000 이하다.
각 원소도 1000 이하의 자연수이다.
수열 A의 크기는 1000 이하이므로 O(n^2)의 시간 복잡도도 충분히 연산이 가능하다.
바로 전체 코드를 통해 어떻게 DP를 활용했는지 확인해 보자.
n=int(input())
sequence=list(map(int,input().split()))
res=[0 for i in range(n)]
res[0]=1
for i in range(1,n):
cnt=0
for j in range(0,i):
if sequence[j]<sequence[i] and cnt<res[j]:
cnt=res[j]
res[i]=cnt+1
print(max(res))
3번째 줄 res란 리스트가 DP를 활용하는 리스트이기 때문에 핵심 포인트이다.
sequence는 원래의 수열 A를 뜻하고 res는 각 원소가 부분 수열의 몇 번째에 해당하는지를 나타낸다.
따라서 n만큼 수열의 길이를 입력받으므로 res를 n의 길이만큼 초기화시키고 res의 0번째 인덱스를 1로 한 이유는 0번째 인덱스의 원소가 부분 수열의 첫 번째 원소가 된다는 의미이다.
5번째 줄부터 중첩 for문을 사용하는데 버블 정렬과 원리는 비슷하다.
첫 번째 for문에서는 1번째 원소부터 n-1번째 원소까지 반복하는데 매번 카운트를 0으로 초기화하고 두 번째 for문에서는 i번째 원소보다 작으면서 카운트보다 res의 원소가 더 크다면 카운트를 갱신한다.
즉 해당 원소보다 작은 원소들이 최대한 몇 개 포함될 수 있는지 계산하는 방식이다.
두 번째 for문이 끝나면 res의 i번째를 카운트+1로 갱신한다.
예를 들어 카운트가 2라면 i번째 인덱스는 3이 되고 i번째 원소보다 작은 원소가 두 개, i번째 원소는 부분 수열의 3번째 원소가 될 수 있다는 의미이다.
이렇게 리스트에 몇 번째 원소가 될 수 있는지 카운트함으로써 부분 수열을 일일이 구하지 않아도 최장 길이를 구할 수 있다.
투 포인터 알고리즘이란 두 개의 지점을 이동시키면서 연속된 숫자의 합(구간 합)을 구하는 알고리즘이다.
비슷한 알고리즘으로 슬라이딩 윈도우(Sliding Window)가 있는데 이 둘의 차이점은 구간의 길이다.
슬라이딩 윈도우는 구간의 길이가 정해져 있고, 투 포인터는 상황에 따라 변한다.
또한 투 포인터는 음수가 존재할 경우 구간의 길이가 증가했을 때 구간 합이 증가할지 감소할지 보장할 수 없으므로양의 정수만 존재할 때 사용 가능하다는 특징이 있다.
그림을 통해 이해하면 쉬울 것이다.
다음과 같이 자연수로 이루어진 리스트가 있을 때 합이 5인 구간의 최소 길이를 찾는 예시를 보자.
이때 두 가지 변수를 Left, Right로 선언하고 처음부터 Right 변수를 오른쪽으로 움직이며 구간 합에 원소를 합하고 Left 변수를 오른쪽으로 움직이며 구간합에 원소를 빼는 방식이다.
먼저 Right 변수가 첫 번째 원소를 가리킬 때다.
Sum에 해당하는 원소를 더하고 5와 비교했을 때 더 작으므로 구간을 늘려야 한다.
따라서 Right 변수를 옮겨야 한다.
Right 변수를 옮기고 나서 구간합이 5가 되므로 이 구간의 길이를 갱신시키면 된다.
최소 길이를 구해야 하므로 Left 변수를 옮기면 된다.
Left 변수를 옮기고 나서 Sum이 5보다 작으므로 Right 변수를 옮긴다.
Right 변수를 옮긴 뒤 Sum이 5보다 크므로 Left 변수를 옮겨 구간 합을 더 작게 만든다.
Left 변수를 옮기고 Sum이 5보다 더 크지만 동일한 원소(구간의 길이가 1)를 가리키므로 Right 변수를 옮긴다.
Right 변수를 옮긴 뒤 Sum이 5보다 크므로 Left 변수를 옮긴다.
Left 변수를 옮긴 뒤 해당 원소를 빼주니 Sum이 5이다.
해당 구간의 길이는 1이므로 구간 길이를 갱신해주고 Right 변수를 옮긴다.
Right 변수를 옮기니 리스트를 벗어나므로 탐색을 종료한다.
인덱싱을 어떻게 구현하는지는 본인의 자유이며 인덱싱 과정이 헷갈릴 수 있기에 여러 가지 방법 중에 가장 자신한테 적합한 방식을 적용하는 편이 좋을 것 같다.
다음은 문제를 푼 전체 코드이다.
n,s=map(int,input().split())
left=-1
right=0
min_len=100001
num_array=list(map(int,input().split()))
temp_sum=num_array[0]
while right<n:
if temp_sum>=s:
if min_len>right-left:
min_len=right-left
left+=1
temp_sum-=num_array[left]
else:
right+=1
if right<n:
temp_sum+=num_array[right]
if min_len==100001:
print(0)
else:
print(min_len)
문제에서 수열의 길이 N은 100000 미만이므로 100000 이상의 숫자 중 아무거나 구간의 최소 길이로 정하고 그걸 갱신하면 최소 길이를 구할 수 있다.
만약 처음에 정한 숫자가 그대로 있다면 합이 s보다 큰 구간이 없단 뜻이며 4번째 줄에선 선언하고, 17번째 줄에선 판단하도록 구현했다.
7번째 줄의 while문에서는 right 변수가 수열의 길이를 넘어가면 안 되므로 길이(n) 미만일 때까지만 반복을 한다.
또한 while문 내부에서는 구간합이 S이상이면 길이를 갱신하고 Left를 이동시켜 원소를 구간합에서 빼고 구간합이 S미만이면 Right를 이동시켜 원소를 구간합에 더하도록 구현했다.
결과 화면
인덱싱 과정이 다소 헷갈릴 수 있는 알고리즘이라서 소수의 원소를 집어넣고 접근하는 과정을 하나씩 출력하다 보면 실수를 줄일 수 있을 것이다.
이진 트리와 순회에 대해 구현한 경험이 있다면 아주 쉽게 풀 수 있는 문제지만 경험이 없다면 아마 상당히 막막하게 느껴질 수 있는 문제라고 생각한다.
다행히 파이썬은 딕셔너리란 자료구조를 지원하므로 딕셔너리를 이용해서 아주 쉽게 구현해보겠다.
def preorder(trees,root):
print(root,end="")
if trees[root][0]!=".":
preorder(trees,trees[root][0])
if trees[root][1]!=".":
preorder(trees,trees[root][1])
def inorder(trees,root):
if trees[root][0]!=".":
inorder(trees,trees[root][0])
print(root,end="")
if trees[root][1]!=".":
inorder(trees,trees[root][1])
def postorder(trees,root):
if trees[root][0]!=".":
postorder(trees,trees[root][0])
if trees[root][1]!=".":
postorder(trees,trees[root][1])
print(root,end="")
n=int(input())
trees={}
root="A"
for i in range(n):
temp=input().split()
trees[temp[0]]=[temp[1],temp[2]]
preorder(trees,root)
print()
inorder(trees,root)
print()
postorder(trees,root)
문제를 간략하게 다시 설명하자면 0은 비어있는 땅, 1은 배추가 있는 땅이고 각 케이스마다 배추가 이어져있는 구역을 세서 출력하면 된다.
그래프를 탐색하는 방법은 스택을 쓰는지, 큐를 쓰는지에 따라 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)으로 나뉘는데 둘 다 시간 복잡도는 비슷하므로 편한 방식으로 구현하면 된다.
필자는 최단 거리를 찾을 때 BFS가 유리하므로 보통 BFS로 구현한다.
바로 전체 코드를 확인해 보자.
testcase=int(input())
dir=[[-1,0],[0,1],[1,0],[0,-1]]
for i in range(testcase):
queue=[]
res=0
M,N,K=map(int,input().split())
graph=[[0 for j in range(M)]for k in range(N)]
for j in range(K):
tempm,tempn=map(int,input().split())
graph[tempn][tempm]=1
for j in range(N):
for k in range(M):
if graph[j][k]==1:
res+=1
queue.append([j,k])
graph[j][k]=0
while len(queue)>0:
tempn,tempm=queue.pop(0)
for a in range(len(dir)):
dx=tempn+dir[a][0]
dy=tempm+dir[a][1]
if 0<=dx<N and 0<=dy<M and graph[dx][dy]==1:
graph[dx][dy]=0
queue.append([dx,dy])
print(res)
1번째 줄은 테스트 케이스만큼 반복하기 위한 변수이고 2번째 줄은 각 노드에서 탐색 방향(위, 오른쪽, 아래, 왼쪽)을 묶어놓은 리스트이다.
이렇게 방향을 리스트로 묶으면 4가지 방향을 탐색할 때 반복문으로 해결할 수 있다는 장점이 있기에 꼭 잊지 말길 바란다.
대부분은 4가지 방향이지만 가끔 대각선도 고려하는 8가지 방향 문제도 있는데 단순하게 방향을 고려해서 8개의 리스트를 넣으면 된다.
4번째 줄의 queue는 큐를 사용함으로써 BFS 방식을 쓰기 위해 선언한 리스트이다.
가끔 리스트를 큐 방식으로 쓸 때 시간 초과가 나는 경우가 있는데 이는 pop() 함수에서 마지막 원소부터 탐색하기 때문에 첫 번째 원소를 제거하기 위해서는 O(n)의 시간 복잡도가 걸리기 때문이다.
그럴 경우엔 deque 모듈을 사용하면 O(1)로 첫 번째 원소에 삽입하고 삭제할 수 있다.
8번째 줄은 배추의 위치를 갱신하는 반복문이고 11번째 줄부터는 그래프를 전체 탐색하면서 배추 구역을 카운트하는 반복문이다.
13번째 줄은 배추가 있을 경우 카운트를 하고 인접한 배추 구역을 0으로 바꾸는 작업이다.
보통 원본 그래프를 변경하지 않기 위해 visited로 그래프와 똑같은 크기의 리스트를 선언하고 방문한 노드인지 아닌지 체크하여 중복된 방문을 방지하는데 해당 문제에서는 단지 배추 구역만 세면 되므로 원본 리스트를 변경해도 상관없어서 아예 0으로 바꿨다.
또한 20, 21번째 줄에서 탐색할 노드의 위치를 계산하여 따로 변수에 저장하는 이유는 미리 값을 저장해놔야 그래프 크기 안인지 배추가 있는 노드인지 체크할 때 불필요한 연산 횟수를 줄일 수 있기 때문에 값을 저장하는 것을 추천한다.
결과 화면
탐색 방향을 고려할 필요도 없고 단지 구역만 세면 되기 때문에 그래프 문제 중에서도 꽤 쉬운 편에 속한다고 생각한다.
그림의 가로길이는 짝수이며 접었을 때 물감이 겹치는 부분도 없다고 하니 그냥 구간을 절반으로 나눠 물감이 있으면 반대편에도 추가하는 방식으로 풀면 되는 브론즈다운 문제였다.
상당히 쉬우니 바로 전체 코드로 넘어가겠다.
n,m=map(int,input().split())
graph=[]
for i in range(n):
temp=list(input())
for j in range(m//2):
if temp[j]!='.':
temp[m-j-1]=temp[j]
elif temp[m-j-1]!='.':
temp[j]=temp[m-j-1]
graph.append(temp)
for i in range(len(graph)):
for j in range(len(graph[i])):
print(graph[i][j],end="")
print()
각 줄을 입력받으면서 바로 물감을 갱신한 뒤 그래프에 추가하여 출력하는 방식으로 구현했다.
5번째 줄이 물감을 갱신하는 반복문이며 구간을 절반으로 나눠 6번째 줄은 첫 문자부터 절반 부분까지, 8번째 줄은 뒷 문자부터 절반 부분까지 물감이 있으면 반대편에 추가하고 완료되면 그래프에 추가했다.
그리고 완전 탐색을 통해 그래프 출력만 하면 되는 쉬운 문제였다.
만약에 인덱싱 부분이 헷갈린다면 작은 숫자를 몇 개 대입해보면 쉽게 해결할 수 있을 것이다.
이진 탐색 트리(Binary Search Tree)란 왼쪽 서브 트리는 자신보다 작은 수들만 존재하고 오른쪽 서브 트리는 자신보다 큰 수들만 존재하는 이진트리를 뜻한다.
단순한 이진트리는 원하는 값의 존재 여부를 확인하려면 트리 전체를 탐색해야 한다.
따라서 자료구조로써의 효율이 떨어진다.
그래서 나온 것이 이진 탐색 트리이며 왼쪽은 작은 수, 오른쪽은 큰 수를 유지함으로써 탐색하는데 O(logn)의 효율적인 시간 복잡도를 가질 수 있다.
또한 모든 원소들은 서로 다른 값을 가진다는 조건이 붙어있다.
삽입과 삭제 과정을 그림을 통해 보면 이해가 쉬울 것이다.
이진 탐색 트리의 삽입 연산
먼저 트리는 항상 루트부터 시작한다.
기존의 트리에서 4를 추가하기 위해 루트 원소를 살펴보니 6으로 4가 더 작기 때문에 왼쪽 자식 노드로 내려간다.
다시 비교해보니 추가하려는 원소가 더 크기 때문에 오른쪽으로 내려가야 되는데 더 이상 자식 노드가 없으므로 오른쪽 자식 노드로 추가한다.
그다음 8을 추가하기 위해 다시 루트 노드부터 탐색을 시작한다.
6보다 크니 오른쪽 자식 노드로 내려가고 9보다 작으니 왼쪽 자식 노드, 7보다 크니 오른쪽 자식 노드로 내려가는데 이때 오른쪽 자식 노드가 없으므로 오른쪽에 노드를 추가하면 된다.
루트에서 시작해서 매번 범위를 절반씩 줄여 나가므로 삽입 시 O(logn)의 시간 복잡도가 걸린다.
삽입 연산이 크기 비교만을 통해 탐색 후 추가하는 거라 상당히 단순하기 때문에 삽입에 비해서 삭제 연산은 다소 복잡하게 느껴질 수 있다.
하지만 케이스를 나눠 순서를 따라가면 이해할 수 있을 것이다.
케이스는 크게 2가지로 삭제할 노드가 단말 노드인 경우, 자식 노드가 존재하는 경우로 나눠서 생각하면 된다.
단말 노드일 때 삭제 연산
삭제 노드를 찾기 위한 탐색은 삽입 연산과 동일하다.
먼저 가장 간단한 경우인 삭제할 노드가 단말 노드인 경우는 그냥 해당 노드와 부모 노드의 관계를 끊어주고 삭제하면 된다.
자식 노드가 존재할 경우 삭제 연산
두 번째는 자식 노드가 존재할 경우이다.
통상 이진 탐색 트리의 삭제는 단말 노드인 경우, 자식 노드가 한 개인 경우, 자식 노드가 두 개인 경우 이렇게 나누는데 자식 노드가 하나나 둘이어도 원리는 같은 방식이니 굳이 구분 짓진 않겠다.
기억해야 할 중요한 점은 삭제할 노드와 가장 차이가 적게 차이나는 노드로 교체한다는 것이다.
이것과 이진 탐색 트리의 특성을 기억한다면 방식을 까먹을 일은 없다.
즉, 삭제할 노드의 왼쪽 자식(왼쪽 서브 트리)으로 내려갔다면 가장 차이가 적게 나는 값을 찾기 위해 최대한 오른쪽 자식 노드(오른쪽 서브 트리)로 이동해야 값을 찾을 수 있을 것이고, 반대로 오른쪽 자식 노드로 내려갔다면 가장 차이가 적게 나는 값을 찾기 위해 최대한 왼쪽 자식 노드로 이동해야 값을 찾을 수 있을 것이다.
가장 차이가 적게 나는 노드를 찾았다면 원래 삭제할 노드와 값을 교환하고 단말 노드의 삭제를 하면 된다.
그림을 보면 삭제할 9를 찾기 위해 루트 노드의 오른쪽 자식으로 이동하여 삭제할 노드를 찾았고, 왼쪽 자식이 있으므로 왼쪽으로 이동 후 오른쪽 자식 노드가 존재하지 않을 때까지 오른쪽 자식 노드로 이동하였다.
결국 8을 찾았고 이를 9와 교체한 뒤 삭제하면 된다.
전체적으로 보면 알겠지만 삽입과 삭제 과정에서도 꾸준히 이진 탐색 트리의 특성을 유지하는 것을 알 수 있다.
구현
이진 트리를 구현하는 3가지 방법을 소개하겠다.
리스트(배열)로 구현
딕셔너리로 구현
구조체로 구현
보통 리스트로 구현하는 방법은 낭비되는 공간이 많으므로(공간 복잡도가 비효율적이므로) 구조체로 구현하는 방법을 많이 쓴다.
또한 파이썬은 키, 값을 갖는 딕셔너리로도 구현이 가능하기 때문에 상황에 맞게 자신이 편한 방식대로 구현하면 된다. (필자는 딕셔너리가 가장 편하고 쉬우며 효율적이기에 자주 쓴다.)
코딩 테스트를 기준으로 보통 이진 탐색 트리가 나온다면 삽입이나 순회가 나온다.
삭제를 실제로 구현하기엔 다소 복잡하기 때문이다.
따라서 이진 탐색 트리를 다양하게 구현해보고 노드 삽입까지 해보겠다.
def list_insert(curr,num):
if binary_tree[curr]=='*':
binary_tree[curr]=num
elif num<binary_tree[curr]:
list_insert(2*curr,num)
else:
list_insert(2*curr+1,num)
print("리스트로 구현한 이진 탐색 트리\n")
binary_tree=['*' for i in range(16)]
root=1
list_insert(root,6)
list_insert(root,3)
print(binary_tree)
list_insert(root,1)
list_insert(root,9)
print(binary_tree)
list_insert(root,7)
list_insert(root,4)
list_insert(root,8)
print(binary_tree)
리스트로 구현할 때는 연산의 편의성 때문에 인덱스 1을 루트 노드로 가정한다.
인덱스 1을 루트로 하기 때문에 인덱스*2는 왼쪽 자식 노드, 인덱스*2+1은 오른쪽 자식 노드로 생각할 수 있다.
트리의 형태는 본문의 노드 삽입 결과와 똑같기 때문에 결과 화면과 그림을 비교해보면서 인덱스를 추적하면 이해가 될 것이다.
리스트 결과 화면
def dic_insert(curr,num):
global root
if len(binary_tree)==0:
root=num
binary_tree[root]=['*','*']
else:
if num<curr:
if binary_tree[curr][0]=='*':
binary_tree[curr][0]=num
binary_tree[num]=['*','*']
else:
dic_insert(binary_tree[curr][0],num)
else:
if binary_tree[curr][1]=='*':
binary_tree[curr][1]=num
binary_tree[num]=['*','*']
else:
dic_insert(binary_tree[curr][1],num)
print("딕셔너리로 구현한 이진 탐색 트리\n")
binary_tree={}
root=None
dic_insert(root,6)
dic_insert(root,3)
print(binary_tree)
dic_insert(root,1)
dic_insert(root,9)
print(binary_tree)
dic_insert(root,7)
dic_insert(root,4)
dic_insert(root,8)
print(binary_tree)
딕셔너리는 키를 노드의 원소, 값을 길이가 2인 리스트로 선언하여 왼쪽 자식과 오른쪽 자식으로 구분 짓는다.
따라서 딕셔너리의 길이가 0일 땐 루트의 원소로 갱신하고 새로운 노드를 삽입할 땐 부모 노드에서 자식 노드를 갱신하고 초기화된 노드를 추가하는 것을 잊지 말아야 한다.
딕셔너리 결과 화면
class Node:
def __init__(self,num):
self.data=num
self.left=self.right=None
class Binary_tree:
def __init__(self):
self.root=None
def Node_insert(self,num):
if self.root==None:
self.root=Node(num)
else:
self.curr=self.root
while True:
if num<self.curr.data:
if self.curr.left==None:
self.curr.left=Node(num)
break
else:
self.curr=self.curr.left
else:
if self.curr.right==None:
self.curr.right=Node(num)
break
else:
self.curr=self.curr.right
print("구조체로 구현한 이진 탐색 트리\n")
Binary=Binary_tree()
Binary.Node_insert(6)
Binary.Node_insert(3)
Binary.Node_insert(1)
Binary.Node_insert(9)
Binary.Node_insert(7)
Binary.Node_insert(4)
Binary.Node_insert(8)
구조체로 구현하는 방식은 노드에 대한 구조체를 선언하고 해당 노드들을 이진 트리의 구조체로 묶는 형식이다.
파이썬의 특성상 Class의 인스턴스를 생성한 뒤 첫 번째 인자로 넘기기 때문에 self로 받는다.
이런 부분까지 다루게 되면 상당히 복잡하고 어려워지므로 이진 탐색 트리는 여기까지 하도록 하겠다.
처음 생각한 풀이법은 노드의 수는 10,000개 이하고 전위 순회의 결과가 입력으로 주어지니 전위 순회 순서대로 트리에 삽입하여 완성된 트리를 후위 순회하여 출력하는 방식을 생각했었다.
하지만 생각치 못하게 시간 초과와 메모리 초과가 떠서 틀렸었다.
불합격 이미지
다음은 불합격한 코드이다.
import sys
sys.setrecursionlimit(10**6)
binary_tree={} #이진 트리를 위한 딕셔너리 선언
while True:
try:
num=int(input())
if len(binary_tree)==0: #빈 트리일 때
root=num #루트로 설정
binary_tree[root]=['*','*']
else:
curr=root
while True:
#왼쪽 서브 트리일 때
if num<curr:
#왼쪽 노드가 없을 때
if binary_tree[curr][0]=='*':
binary_tree[curr][0]=num
binary_tree[num]=['*','*']
break
#왼쪽 자식 노드로 이동
else:
curr=binary_tree[curr][0]
#오른쪽 서브 트리일 때
else:
#오른쪽 노드가 없을 때
if binary_tree[curr][1]=='*':
binary_tree[curr][1]=num
binary_tree[num]=['*','*']
break
#오른쪽 자식 노드로 이동
else:
curr=binary_tree[curr][1]
except:
break
def postorder(curr):
#왼쪽 자식 노드로 이동
if binary_tree[curr][0]!='*':
postorder(binary_tree[curr][0])
#오른쪽 자식 노드로 이동
if binary_tree[curr][1]!='*':
postorder(binary_tree[curr][1])
#현재 노드 출력
print(curr)
postorder(root)
2번째 줄은 파이썬에서 기본 재귀 깊이 제한이 1000이기 때문에 1000000으로 세팅하는 코드이다.
이 때문에 런타임 에러(Recursion Error)가 뜬 것이다.
또한 입력받는 부분에서 어디까지 받는다는 제한이 없으므로 try except 구문을 사용하여 예외가 발생하기 전까지 입력을 받고 트리에 추가하는 방식으로 하였다.
예외가 발생하면 그대로 트리를 후위 순회하여 출력했는데 불합격한 것을 보니 다른 방식을 생각해야 했다.
고민하던 중에 전위 순회는 현재 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 탐색하고 후위 순회는 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 현재 노드 순으로 탐색하기 때문에 현재 노드를 출력하는 타이밍을 조절해야겠다는 생각이 들었고 현재 노드보다 작은 숫자는 왼쪽 서브 트리, 큰 숫자는 오른쪽 서브 트리로 구분 지을 수 있겠다는 생각이 들었다.
따라서 리스트를 기준으로 첫 번째 원소는 현재 노드라 마지막에 출력하고 현재 노드보다 작은 원소들의 리스트는 왼쪽 서브 트리로 여겨 재귀 호출, 큰 원소들의 리스트는 오른쪽 서브 트리로 여겨 재귀 호출하면 차례대로 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 현재 노드 순으로 출력될 것이라 생각했고 역시 통과했다.
다음은 통과한 전체 코드이다.
import sys
sys.setrecursionlimit(10**6)
#입력받을 원소 리스트
num_list=[]
while True:
try:
num=int(input())
num_list.append(num)
except:
break
def postorder(left,right):
#순서 역전시 종료
if left>right:
return
else:
mid=right+1 #분할 기준
for i in range(left+1,right+1):
#해당 원소가 현재 노드보다 크다면 그 전까지는 왼쪽 서브 트리,
#해당 원소 이후는 오른쪽 서브 트리이다.
if num_list[left]<num_list[i]:
mid=i
break
postorder(left+1,mid-1)
postorder(mid,right)
print(num_list[left])
postorder(0,len(num_list)-1)
트리 생성이 아닌 단순히 리스트에 원소를 입력 받으므로 입력 받는 부분은 전보다 더 간단해졌다.
시작은 전체 리스트의 길이부터 시작하고 가장 첫 번째 원소는 현재 노드, 그 이후부터 반복문을 돌면서 현재 노드보다 큰 원소가 있다면 그 전까지는 왼쪽 서브 트리, 큰 원소부터 이후는 오른쪽 서브 트리로 구분지어 재귀호출한다.
만약 큰 원소가 없을 경우를 대비해 mid=right+1을 함으로써 없으면 현재 노드를 제외한 나머지를 왼쪽 서브 트리로 보내고 두 번째 호출하는 재귀 함수는 순서가 역전되어 종료되도록 구현하였다.
결과 화면
인덱스를 접근하고 관리하는 방법에서 다소 헷갈리는 부분이 있고 알고리즘 외적으로도 재귀 깊이를 변경한다든지 입력받는데 처리해줘야 하는 부분이 있는 문제였다.
또한 해당 코드를 PyPy3로 제출하면 메모리 초과가 뜬다.
PyPy3가 Python3보다 연산이 빠르기에 안전하게 하기 위해 PyPy3로 먼저 제출했었는데 자료를 찾아보니 PyPy3는 최대 재귀 깊이는 제한이 없으나 10만 단위 이상으로 들어가면 Stack Overflow가 발생하여 재귀에 약하다는 정보를 얻을 수 있었다.
따라서 시간 초과가 뜬다면 PyPy3로, 재귀를 사용하여 메모리 초과가 뜬다면 Python3으로 제출해야한다는 지식을 알게 되었다.
