오뚝이개발자

트리를 순회하는 방법은 preorder, inorder, postorder로 크게 3가지가 있다. 여기서 소개하려고 하는 내용은 이러한 순회를 "어떻게" 구현하는지에 관한 것이다. 가장 보편적인 것은 물론 재귀를 이용하는 것이나, 반복문을 통해서도 얼마든지 구현 가능하다. 참고로 트리노드의 정의는 아래와 같다고 하자. # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right 편의상 inorder를 구현하는 것으로 한다. 재귀(Recursive)를 통한 구현 class Solution: # ..

Stack이란? LIFO(Last In First Out) order를 따르는 자료구조 예) 쌓여있는 책더미 Stack 구현의 두 가지 방법(item container로 어떤 것을 선택할지) Linked list로 구현(head에만 삽입하고 head만 지워 이를 stack의 top처럼 활용) Dynamic array로 구현(head를 포인터가 아닌 index 값으로 사용) Queue란? FIFO(First In First Out) order를 따르는 자료구조 예) 줄서기(waiting line) Queue 구현의 두 가지 방법 Linked list로 구현 Dynamic array로 구현 이 때, false-overflow 문제 발생 : 실제로는 빈 공간이 있는데 다 찬 것처럼 보이는 현상 그래서 나온 해..