Stack의 활용 문제 - BOJ 25556번 포스택
2023. 3. 13. 17:06
DataStructure/List
문제 https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 문제 접근 순열의 "청소"의 정의는 문제에 정의되어있는 일련의 순서를 진행하였을 때 순열의 전체적인 모습이 오름차순으로 정렬될 수 있는가를 묻는다. 스택은 LIFO로 나중에 들어오는 수가 먼저 나가기 때문에 문제의 과정 중 3번을 살펴보면 스택의 내부가 오름차순으로 되어 있어야 한다. 다음의 TC를 보자 10 4 3 6 7 8 9 10 2 1 5 만약 어떤 스택에 4가 먼저 들어온 뒤, 그 스택에 3을 넣는다고 생각해보자. 후입선출의 원리에 의해 스택에서 3이 먼저 나가게 되고 4가 그 이후에 나가게 된다. 하..
우선순위 큐의 활용 문제 풀이
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"가 들어가있다. 푸른색으로 색칠된 노드들은 해당 노드가 문자열의 끝임을 나타내는..
Stack의 활용 - VPS
2023. 3. 6. 20:45
DataStructure/List
들어가며 VPS는 기본 문자열 쌍으로 괄호가 올바르게 배치되어 있는가를 확인하는 문제이다. 이때 올바르게 배치되었다 라는 상태의 정의는 괄호의 ( 과 ) 가 쌍을 이룰 수 있도록 배치되어 있는 상태를 말한다. 예시를 들어 (())라는 괄호 쌍은 올바르게 배치되었다. ( 와 )가 쌍을 잘 이루고 있기 때문이다. 다른 예시로 (())((는 올바르지 않은 배치이다. 뒤의 ((의 쌍이 존재하지 않기 때문이다. 다른 예시로 )(는 올바르지 않은 배치이다. 닫힌 괄호가 먼저 나와있기 때문이다. String 배열로 문자열들이 들어온다. 문자열들은 모두 ( 또는 )로 이루어져 있으며 다른 입력이 들어오는 경우는 존재하지 않는다. 이때 각 문자열들이 VPS로 올바르게 배치되었는지 확인하여 그 결과를 배열로 반환하는 함수..
힙(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에 수행할 시 오름차순으로 이루어진 데이터를 얻을 수 있다. 이렇게 데이터의 입 출력을..