728x90 자료구조5 인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder) 인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder) 이진 트리를 순회하는 세 개의 방법 정의 이진 트리(Binary Tree) 를 순회(Traversal)할 때 위와 같이 세 가지 방법이 존재한다. Inorder (중위 순회) : left Node -> root Node -> right Node preorder (전위 순회) : root Node -> left Node -> right Node postorder (후위 순회) : left Node -> right Node -> root Node 중위 순회 (Inorder Traversal) left Node -> root Node -> right Node 순서로 순회한다. 위 트리에선 (1) -> (3) -> (4) ->.. 2023. 1. 15. 이진 트리 (Binary Tree) 이진 트리 (Binary Tree) 정의 임의의 노드의 자식 노드가, 최대 2개를 넘지 않는 트리 설명 컴퓨터 과학에서 정말 많이 사용되는 자료구조이다. 임의의 노드의 자식 노드가, 최대 2개를 넘지 않는다. 또한 이진 트리에서 부트리(Sub-Tree) 또한 이진 트리이다. Root : Tree의 최상위 노드 Parent / Child : 위 예시에서 임의의 노드 A노드는 B, C 노드의 Parent 이며, B, C 노드는 A 노드의 Child 노드이다. Sibling : 같은 Parent 노드를 가진 두 노드 Leaf Node : Child 노드가 없는 노드 Depth : 임의의 노드에서, Root 노드 까지의 간선의 수 Height : 최대 Depth의 값 Sub Tree : 트리에서, 임의의 노드를.. 2023. 1. 14. 백준 No.5670 [휴대폰 자판] BOJ No.5670 [휴대폰 자판] 문제 5670번: 휴대폰 자판 (acmicpc.net) 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 설명 * 자료 구조 * 트라이 (Trie) 문자열을 저장하는 자료구조 (Trie : 트라이 (Trie) : 문자열 저장 자료구조) 를 이용하는 문제이다. 각 Node 의 옆에 파란 숫자는 그 글자까지 나오기까지 키보드를 누른 횟수이다. 또한 빨간 테두리 Node 는 단어의 끝을 알리는 Node 이다. 키보드를 누르는 경우는 크게 세 가지가 있다. 1. 아직 아무 문자도 안 눌.. 2022. 4. 2. 트라이 (Trie) : 문자열 저장 자료구조 트라이 (Trie) 저장된 문자열 탐색에 용이한 자료구조 정의 트라이(Trie) 는 문자열들의 집합이 있을 때 문자열의 존재 여부를 쉽게 찾아낼 수 있도록 해 주는 자료구조 이다. 직관적인 예시를 통해 설명을 해 보았다. 설명 아래 문자열들을 저장 해 보려고 한다. [저장된 문자열들] key king hi hint day date 위 문자열들은 Trie 자료 구조에서 아래와 같이 저장된다. 만약 'king' 이라는 단어가 저장이 되어 있는지 찾아보고 싶으면 root Node 부터 차례대로 하위 Node로 이동하여 'k', 'i', 'n', 'g' 를 찾아가면 된다. 만약 저 자료구조에는 존재하지 않는 'keep' 이라는 단어를 찾아보려 한다면, root Node ⇒ 'k' Node ⇒ 'e' Node ⇒.. 2022. 4. 2. 세그먼트 트리 (Segment tree) 세그먼트 트리 (Segment tree) 정의 세그먼트 트리 (Segment tree) 란, 1차원 배열의 값들을 포화 이진 트리를 활용하여 Bottom-up 을 통해 효율적으로 저장 및 탐색하는 자료구조 이다. 이 트리의 리프 노드들은 순서대로 배열의 원소들에 해당이 되며, 내부 노드들은 아래 두 자식 노드에 해당이 되는 배열의 원소들을 합한 범위의 원소들에 대한 연산 값을 나타낸다. 트리 구현 트리의 각 노드들은 배열에서 트리에 해당되는 구간의 원소들의 합의 값을 가지고 있다. 설명 세그먼트 트리는 Bottom-up 방식으로 구현이 된다. 이를 위해선, 리프 노드들을 배열의 원소들로 우선적으로 초기화를 시켜준다. 리프노드의 시작 노드는 배열의 개수보다 큰 2의 제곱수 들 중 최소값이다. 즉 위 트리에.. 2021. 8. 3. 이전 1 다음 728x90
