오뚝이개발자

문제 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 나의 풀이 preorder와 postorder로 트리를 순회하는 것은 쉽다.(모르면 검색을 해보면 금방 나올 것이다.) 이 문제의 핵심은 주어진 정보로 트리를 얼마나 잘 구현하는가이다. nodeinfo를 y좌표에 대해 내림차순, x좌표에 대해 오름차순으로 정렬한다. 정렬된 nodeinfo를 순회하며 각 노드의 자리를 찾아 삽입한다. 문제에서 주어진 조건 중 ..

트리를 순회하는 방법은 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: # ..

Tree란? Connected, Acyclis, Undirected graph Tree는 Graph에 포함된다. Rooted tree란? 하나의 node가 root로 지정된 tree Tree에서 depth란? root 노드로부터 해당 노드까지의 edge 수 트리의 depth : lowest leaf의 depth(이것을 트리의 height라고도 한다.) Tree에서 level이란? depth와 비슷하지만 기준이 edge가 아닌 node 아래 그림에서 B, D는 각각 레벨이 2, 3인 노드이다. Binary tree란? 모든 node가 최대 2개의 child를 갖는 트리 Binary search tree(BST)란? x라는 key value를 갖는 노드의 left subtree에는 x보다 작은 값이, rig..