우선순위 큐의 활용 문제 풀이
2023. 3. 10. 15:42
DataStructure/Tree
제공되는 문제들은 제로베이스 백엔드 스쿨 11기의 비선형 자료구조 문제들입니다. 우선순위 큐의 활용 우선순위 큐(Priority Queue) 자료구조는 힙을 사용한 자료구조이다. 힙의 특성상 최대, 최소값만 찾고 나머지는 연산할 필요가 없는 문제들에서 사용될 수 있다. 이는 매 턴마다 최대 최소값을 찾기 위해 정렬을 수행해야하는 상황에서 특히 강력함을 발휘할 수 있다. 힙 정렬을 사용하여 O(NlogN) 으로 정렬을 수행한다 하더라도 턴의 수가 M인 경우에 전체 시간 복잡도는 O(M x NlogN)으로 M >= N인 상황에서 O(N^2logN)의 수행시간이 걸리며 이는 그렇게 좋은 시간 복잡도는 아니다. 이를 우선순위 큐를 통해 최대 - 최소값만을 찾을 경우에 데이터의 삽입 - 삭제만 일어나기 때문에 전..
트라이(Trie)의 정의와 구현
2023. 3. 7. 20:37
DataStructure/Tree
트라이의 정의 트라이는 문자열을 저장하고 빠르게 탐색하기 위해 사용하는 자료구조의 일종으로 트리 구조를 가진다. 일반적으로 어떠한 문자열에서 특정 문자열을 찾기 위해서 이중 루프를 사용하나 해당 방법은 O(N^2)에 가까운 수행시간이 걸리게 된다. 트라이에서는 트라이 자료구조를 생성하는데 걸리는 시간 O(MN)이 수행된다(M : 문자열의 개수, N : 문자열의 길이) 하지만 생성하고 나면 길이 N의 문자열을 탐색하는데 O(N)이 수행되며 트라이 자료구조를 위한 메모리와 탐색에 걸리는 시간을 trade-off 하였다고 할 수 있다. 위 사진의 트라이에는 각각 "apple", "april", "ace", "bear", "best"가 들어가있다. 푸른색으로 색칠된 노드들은 해당 노드가 문자열의 끝임을 나타내는..
힙(Heap), 우선순위 큐(Priority Queue)의 원리와 구현
2023. 2. 28. 22:07
DataStructure/Tree
들어가며 힙(Heap)은 최대, 최소값이 항상 루트로 존재하는 트리이다. 힙 트리는 다음과 같은 특징을 가진다. 힙 트리의 루트는 최대값(최대 힙일때), 최소값(최소 힙일때) 중 하나의 값을 가진다. 힙 구조에서 부모 노드는 자식 노드보다 작거나(최소 힙일때) 커(최대 힙일떄)야 한다. 힙 트리는 완전 이진 트리이다. 트리에 데이터가 들어가거나 삭제될 때 최대 최소값만 가장 위로 올라가는 구조이며 그 이외에는 정렬되어있지 않다. 이를 반정렬 상태라고 한다. 중복된 값이 들어갈 수 있다. 루트가 항상 최소가 되게 하는 힙을 최소 힙(min heap)이라고 하며 루트가 항상 최대가 되게 하는 힙을 최대 힙(max heap)이라고 한다. 힙의 구현 이번에 구현할 힙은 최소 힙으로 구현하며 다음과 같은 연산을 ..
AVL 트리의 원리와 구현 (3)
2023. 2. 27. 19:26
DataStructure/Tree
들어가며 이전에는 AVL트리의 벨런스를 맞추는데 사용되는 연산 전반과 트리에 노드를 삽입하는 연산까지 구현하였다. 이번에는 AVL 트리에서 노드를 삭제하는 연산과 그 결과로 인해 벨런스가 맞지 않을 경우 어떻게 동작하는지에 대해서 구현해보겠다. 직전까지 구현한 코드는 아래와 같다. import java.util.*; class Node{ int data; int height; Node left; Node right; Node(int data){ this.data = data; this.left = null; this.right = null; this.height = 0; } } class AVL_Tree { Node root; AVL_Tree(){ this.root = null; } private int..
AVL트리의 원리와 구현 (2)
2023. 2. 27. 17:34
DataStructure/Tree
들어가며 이전 글에서 AVL트리가 어떻게 균형을 자동으로 수복하기 위해 수행하는 4가지 연산(LL, RR, LR, RL연산)에 대해 알아보았다. 이번에는 AVL 트리를 구현하면서 이전 글에서 본 4가지 연산이 어떻게 코드로 구현되는지에 대하여 알아본다. 또한 저번 이진 탐색 트리를 구현할 때 반복문을 통한 구현을 수행했는데 이번에는 재귀로도 구현하는 방법을 같이 알아본다. AVL 트리의 구조 AVL 트리는 자체적으로 균형을 유지하는것 이외에는 이진 탐색 트리와 동일하다. 따라서 사용자는 AVL 트리를 이진 탐색 트리를 사용하는 것 처럼 사용할 수 있으며 자체적으로 어떻게 균형이 유지되는가는 알지 못해도 상관없다. 따라서 자체적으로 균형을 맞추는 모든 연산과 균형의 상태, 높이의 연산따위의 정보는 모두 p..
AVL트리의 원리와 구현 (1)
2023. 2. 27. 16:12
DataStructure/Tree
들어가며 이전에 구현한 이진 트리는 일반적인 경우 어떠한 값을 찾는데 걸리는 시간이 O(logN)이다. 하지만 최악의 경우에 O(N)이 된다. 이때 최악의 경우는 이진 탐색 트리가 하나의 방향으로만 이어져 있는 경우로 다음과 같은 사진으로 확인할 수 있다. 이 경우 1을 찾기 위해서는 좌측으로만 편향된 모든 노드를 거쳐 들어가야하기 때문에 O(N)이 걸리게 된다. 이러한 구조는 좋지 않다. 이러한 구조를 미연에 방지하여 트리가 자동으로 균형을 잡아주는 트리를 AVL(Adelson - Velsky - Landis)트리 라고 한다. 이때 균형이 깨졌다는 것은 어떻게 판단할 것인가를 생각해볼 수 있다. 균형의 판단은 다음과 같이 이루어진다. 어떤 노드의 높이는 그 노드의 좌측 서브트리의 높이와 우측 서브트리의..
이진 탐색 트리의 원리와 구현 - (2)
2023. 2. 26. 16:01
DataStructure/Tree
들어가며 이전에는 이진 탐색 트리의 삽입에 대해 구현하였다. 이번에는 삭제에 대해 구현할 것이다. 이진 탐색 트리에서 원소의 삭제는 해당 노드를 삭제하면서 트리의 전체적인 구조가 이진 탐색 트리의 기준에 맞게 노드들이 다시 재배열 되도록 하는 것이 중요하다. 삭제 연산은 3가지의 케이스가 존재하며 다음과 같다. 삭제할 노드가 자식을 가지고 있지 않은 경우 삭제할 노드가 자식을 하나 가지고 있는 경우 삭제할 노드가 자식을 둘 가지고 있는 경우 3가지 케이스 모두 그림을 통해 자세히 알아보도록 하자. 우리가 테스트로 사용할 트리의 구조는 아래와 같다고 가정하자 선행 조건 원소를 삭제하기 위해서는 당연하게도 우선 해당 원소의 위치를 찾아야 한다. 만약 해당 위치가 null이 된다면 해당 트리에 삭제할 원소가 ..
이진 탐색 트리의 원리와 구현 - (1)
2023. 2. 26. 14:58
DataStructure/Tree
들어가며 이진 탐색 트리(Binary Search Tree, BST)는 중복된 데이터를 허용하지 않으며, 데이터가 트리에 삽입될 때 특정한 조건을 따라 저장되는 이진 트리를 말한다. 기존의 이진 트리에서 데이터를 탐색할 때 해당 데이터가 트리의 어느 부분에 존재하는지 알 수 없으므로 모든 노드를 탐색해야하는 문제가 있다. 이진 탐색 트리는 해당 문제를 해결하기 위해 고안된 자료구조로, 데이터가 삽입될 때 해당 원소와 현재 노드가 가지고 있는 원소를 비교하여 크다면 우측, 작다면 좌측으로 내려가며 저장되는 구조로 되어있다. 이는 데이터를 삽입, 삭제할 때 마다 자동적으로 정렬이 수행되는 구조이며 실제로 중위 순회를 BST에 수행할 시 오름차순으로 이루어진 데이터를 얻을 수 있다. 이렇게 데이터의 입 출력을..
이진 트리의 구현 - (2)
2023. 2. 24. 16:57
DataStructure/Tree
들어가며 이번엔 연결 리스트를 통해 이진 트리의 구현을 수행한다. 우리가 구현할 연산은 다음과 같다. 원소의 삽입 원소의 삭제 임의의 위치에 존재하는 원소의 삭제 트리의 레벨, 전위, 중위, 후위 순회 임의의 노드의 부모 노드를 반환 트리에 존재하는 모든 노드의 개수 반환 이때 제한 조건 이전에 제시한 조건과 동일하다. 원소의 삽입과 삭제는 complete binary tree의 방식을 따른다. 임의의 위치에 존재하는 원소의 삭제 연산은 해당 원소에 딸려있는 모든 원소들을 삭제해야 한다. 조건해석과 구현 방법 이전에 수행했던 조건과 동일하므로 해석 역시 동일하다. 눈여겨보아야 할 점은 임의의 위치에 존재하는 원소의 삭제 연산이다. 해당 원소에 딸려있는 모든 원소를 삭제해야한다는 것은 해당 원소를 루트로 ..
이진 트리의 구현 - (1)
2023. 2. 24. 15:42
DataStructure/Tree
들어가며 이진 트리는 이전에 말했듯 배열과 연결 리스트로 구현이 가능하다. 이번에는 배열로 이진 트리를 구현하는 것을 해보도록 하겠다. 우리가 구현해야할 기능들은 다음과 같다. 트리에 원소를 추가 트리에 원소를 삭제 트리의 전위, 중위, 후위, 레벨 순회 구현 이때 따라붙는 제한 조건(구체적 조건)은 다음과 같다. 원소를 추가할 때는 complete binary tree의 방식을 따른다. 즉 좌에서 우로 원소를 추가해야한다. 원소를 제거할 때에는 우에서 좌로 원소를 삭제한다. 조건해석과 유의사항 원소를 추가할 때 complete binary tree의 방식을 따르므로 이 트리는 complete binary tree가 된다. 즉 리프 노드간의 높이 차이가 최대 1까지 존재하며, 우측 자식이 존재한다면 반드..