[조진과제][AP프로그래밍][4월]과제-2
안녕하세요. 다시 돌아온 Ms. KevinGogans 입니다. 기후변화의 나라, 대한민국답게 4월 1일이 되자마자 날씨가 부쩍 더워졌는데요, 역시 더울땐 코드업이죠.
.
.
.
.
오늘의 주제는 CodeUp - 3201 트리의 중위 순회 문제입니다.
바로 갑시다.
I. 문제 선정 동기
지난 시간에 3202번 문제를 풀었는데요, 저는 이와 매우 관련있는 문제인 3021번 문제를 풀어봄으로써 트리 및 트리의 순회에 대한 이해도를 더욱 높여보고자 CodeUp 3201 '트리의 중위 순회' 문제를 선정하게 되었습니다. 이 문제의 풀이 방법은 3202번 '트리의 전위 순회' 문제와 그 방법이 비슷하지만 그러면서도 서로 다른 풀이 방법을 보입니다.
Ⅱ. 문제 풀이 전략
먼저 사용자로부터 문자열을 입력받는 부분, 내가 문제를 풀기 위하여 임의의 트리를 구축하는 부분, 구축한 트리의 노드를 각각 출력하는 부분으로 나눠 문제를 풀고자 하였습니다.
1. 노드 구축
Node 클래스를 정의하여 노드를 설정할 수 있게 해주었습니다. 기본적으로 완전 이진 트리 상태에서 문제를 해결하고, 자식 노드는 왼쪽 노드와 오른쪽 노드로 나뉘므로 각각 left와 right로 놓고 기본 상태를 None으로 설정하였습니다.
2. 문자열 입력받기
사용자로부터 임의의 문자열(abcd …)를 입력받는 코드를 작성하였습니다. 입력받은 코드는 곧바로 완전 이진 트리(Complete Binary Tree) 함수의 매개변수 중 하나로 쓰입니다.
(complete_binary_tree 함수에 대한 설명은 뒤에 나와있음)
3. 완전 이진 트리 구축
complete_binary_tree() 함수는 이번 문제를 푸는 데에 핵심이 되는 부분으로, 사용자가 입력한 문자열을 바탕으로 완전 이진 트리를 구축하는 역할을 합니다.
complete_ibnary_tree() 함수는 arr과 i라는 매개변수를 필요로 하는데 arr은 이름 그대로 배열로써 사용자가 입력한 문자열을 뜻합니다.
cf) 저번 문제를 풀 때에는 위 함수에 매개변수로 사용자가 입력한 문자열을 전달해줄 때 list()를 통해 str class에서 list class로 그 자료형을 변환해주었지만, 그럴 필요가 없다고 판단되어 이번엔 이 과정을 거치지 않고 문자열을 그대로 매개변수로 줌.
i는 몇 번 노드를 탐색할 지에 대한 값으로써 특정 규칙에 따라 i 값을 새롭게 주면서 트리를 탐색해 나가도록 하였습니다.
이때, 노드의 왼쪽(left)과 오른쪽(right)에게 서로 다른 i 값을 줌으로써 서로 다르게 잘 탐색해나가도록 하였습니다.
이 함수는 재귀적으로 반복되어 최종적으로 모든 노드를 구축한 후 종료됩니다.
cf) 루트 노드가 A이고 그 자식 노드가 각각 B, C, 그 자식 노드는 D, E, … 인 완전 이진 트리를 생각해보자. 이를 1차원 배열에서 생각하면 노드 i의 부모 노드는 i2, 노드 i의 왼쪽 자신 노드는 i*2, 노드 i의 오른쪽 자식 노드는 i*2+1임을 알 수 있음.
위 사진은 이와 관련하여 위 내용을 이해하는 데에 도움을 줄 수 있다고 판단하여 넣은 한 이진 트리의 구조를 나타낸 그림임.
4. 중위 순회 결과 출력
이는 이번 문제을 푸는 데에 필요한 또다른 핵심 코드로, 중위 순회를 하는 코드입니다. 함수 이름은 중위 순회(inorder traversal)에서 따와 inorder라고 하였습니다.
이 함수는 매개변수로 node와 result를 갖습니다. 이는 각각 특정 노드를 방문하여 결과 리스트(result)에 추가하는 데에 쓰입니다. 따라서, 중위 순회의 결과는 result에 순차적으로 저장되는 것입니다.
이 함수는 재귀적으로 반복되어 모든 노드를 탐색한 후 종료됩니다.
Ⅲ. 문제에 적용한 자료구조 및 개념 설명
1. 자료 구조
자료구조(Data Structure)는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말합니다. 각각의 자료구조에는 장단점이 있으므로 어떤 자료구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있습니다. 그러므로 다양한 자료구조의 장단점을 살펴보며 애플리케이션을 만들 때 어떤 자료구조를 사용하는 것이 최선일지 판단해야 합니다.
프로그래밍이란 결국 알고리즘을 작성하고, 그에 맞는 자료구조를 선택하는 것이므로 자료구조를 충분히 이해하지 못한다면 결코 좋은 개발자가 될 수 없습니다. 그래서 파스칼을 개발한 스위스의 컴퓨터 과학자 니클라우스 비르트는 ‘알고리즘 + 자료구조 = 프로그램’이라는 유명한 말을 남기기도 했습니다.
위 내용은 한빛미디어에서 한 말을 가져와본 것인데요, 저는 자료구조를 보다 더 쉽게설명하자면, 책과 책장으로 설명할 수 있겠습니다.
제가 어릴때 다니던 영어학원에는 참 책이 많았는데요, 만약 여러분이 영어 선생님이라면 책을 어떻게 정리하실 건가요?
ㄱ. 난이도별로
ㄴ. 카테고리별로(장르)
ㄷ. 두께별로
ㄹ. 사전식으로(ABC 배열)
위 말고도 많은 배열 기준이 있을 수 있겠지만, 저희 영어학원에서는 아이들이 각자 수준에 맞는 책을 읽을 수 있도록 ㄱ. 난이도별로 정렬했습니다. 단순한 비유지만, 자료구조는 이와 같아요. 문제 상황에 따라 항목들을 여러 방법으로 정리할 수 있으며, 그 기준은 그때그때 개발자(선생님)이 정하는 것이죠.
아이들이 수준별로 책을 골라읽을 수 있도록 하려는데 그걸 카테고리별로 나누면 이상하잖아요?
2. 기본 용어 설명
노드(Node): 트리를 이루고 있는 기본 요소. 주로 특정 값을 가짐.
트리(Tree): 트리란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조간선(Edge): 노드와 노드 간의 연결선
루트 노드(Root Node): 트리 구조에서 부모 노드가 없는 최상위 노드
말단 노드(Terminal Node): 트리 구조에서 자식 노드가 없는 최하위 노드 (=리프 노드)
자식 노드(Child Node): 부모 노드의 하위 노드
형제 노드(Sibling Node): 같은 부모를 가지는 노드
깊이(Depth): 루트에서 어떤 노드의 간선까지의 수
높이(Height): 어떤 노드에서 말단 노드까지 가장 긴 경로의 간선의 수
레벨(Level): 루트에서 어떤 노드까지의 간선의 수
디그리(Degree): 노드의 자식 수
패스(Path): 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
패스 길이(Path Length): 해당 경로에 있는 총노드의 수
사이즈(Size): 자신을 포함한 자손의 노드 수
너비(Width): 레벨에 있는 노드 수
폭(Breadth): 리프 노드의 수
거리(Distance): 두 노드 사이의 최단 경로에 있는 간선의 수
계수(차수, Order): 부모 노드가 가질 수 있는 최대 자식의 수
3. 이진 트리
이진 트리(Binary Tree)란 모든 노드들이 2개 이하(0, 1, 2개)의 자식들을 가진 트리를 말합니다.
이 중에서도 여러 개의 트리로 그 종류가 구분되는데, 이 문제에선 완전 이진 트리에 대해서만 다루므로 이 문제를 풀기 위해 완전 이진 트리(Complete Binary Tree) 구조를 사용했다.
4. 완전 이진 트리
완전 이진 트리란 이진 트리 중에서도 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 노드를 의미한다. 즉, 마지막 레벨은 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
5. 트리 순회
트리는 선형 자료구조가 아니기에, 트리를 단순히 선형 자료 구조와 같은 방법으로 접근할 수는 없다. 따라서 트리에서는 순회(Traversal)를 통해 모든 노드들을 접근할 수 있다. 트리를 순회하는 방법은 노드를 방문하는 순서에 따라 전위(Preorder), 중위(Inorder), 후위(Postorder)로 나눌 수 있다.
6. 중위 순회
전위 순회(Preorder Traversal)는 왼쪽 노드를 먼저 방문한 후 부모 노드를 방문한 후 오른쪽 자신 노드를 탐색하는 방식의 순회 방법을 말한다. 더 이상 방문할 부모 노드가 없으면 종료된다.
Ⅳ. 시행착오
오히려 전에 풀었던 문제(트리의 전위 순회)를 많이 참고하면서 거의 똑같은 코드로 풀려고 하다보니, 잘 풀리지 않았었지만 처음부터 코드를 차근차근 다시 써가다보니 ( 기존 코드를 참고하면서 ) 결국 문제를 잘 해결할 수 있었습니다.
Ⅴ. 소스 코드
전체 소스 코드는 다음과 같습니다.
class Node:
def __init__(self, item):
self.item = item
self.left = None
self.right = None
def complete_binary_tree(arr, i):
if i < len(arr):
node = Node(arr[i])
node.left = complete_binary_tree(arr, 2 * i + 1)
node.right = complete_binary_tree(arr, 2 * i + 2)
return node
return None
def inorder(node, result=[]):
if node:
inorder(node.left, result)
result.append(node.item)
inorder(node.right, result)
return result
input_string = input()
root = None
root = complete_binary_tree(input_string, 0)
print(inorder(root), end='')Ⅵ. 느낀점
처음 트리 순회 문제를 풀 때는 재귀함수를 쓰는 것이 머리가 많이 아파왔지만, 이번에는 트리에 대해 더 깊은 이해도를 가진 상태로 문제를 풀어서 그런건지 전보다는 수월하게 문제를 풀 수 있어 좋았습니다. 트리에 대해 더 높은 이해도를 가지게 되었음을 알 수 있는 기회가 된 것 같아 뿌듯함을 느낄 수 있었습니다.