Stack의 활용 - VPS
2023. 3. 6. 20:45
DataStructure/List
들어가며 VPS는 기본 문자열 쌍으로 괄호가 올바르게 배치되어 있는가를 확인하는 문제이다. 이때 올바르게 배치되었다 라는 상태의 정의는 괄호의 ( 과 ) 가 쌍을 이룰 수 있도록 배치되어 있는 상태를 말한다. 예시를 들어 (())라는 괄호 쌍은 올바르게 배치되었다. ( 와 )가 쌍을 잘 이루고 있기 때문이다. 다른 예시로 (())((는 올바르지 않은 배치이다. 뒤의 ((의 쌍이 존재하지 않기 때문이다. 다른 예시로 )(는 올바르지 않은 배치이다. 닫힌 괄호가 먼저 나와있기 때문이다. String 배열로 문자열들이 들어온다. 문자열들은 모두 ( 또는 )로 이루어져 있으며 다른 입력이 들어오는 경우는 존재하지 않는다. 이때 각 문자열들이 VPS로 올바르게 배치되었는지 확인하여 그 결과를 배열로 반환하는 함수..
Java 미니 과제 리뷰 - (2)
2023. 3. 2. 21:23
Java
5번 사용자 입력을 받아 해당 년 월의 달력을 출력하는 문제 Java에서 날자 관련 기능을 가진 클래스인 LocalDate클래스를 사용해 구현하였다. 먼저 년 월을 입력으로 받고 해당 년과 월의 1일에 대한 정보를 LocalDate를 통해 가져온다. 이후 1일이 무슨 요일인지를 받은 뒤 해당 요일보다 앞에 있는 요일들은 아무것도 출력하지 않고 공백으로 출력한다. 이후 1일부터 시작하여 점점 증가하며 일수를 출력시킨다. import java.util.Scanner; import java.time.LocalDate; public class JavaStudy05 { public static void main(String[] args){ System.out.println("[달력 출력 프로그램]"); Syste..
Java 미니 과제 리뷰 - (1)
2023. 3. 2. 20:43
Java
1번 문제 이중 for looping을 사용하여 구구단을 출력해야 하는 문제 출력 형식이 1 * 1 = 1 2 * 1 = 2 3 * 1 = 3 ... 형식으로 되어있어 내부 루프를 도는 인자가 먼저 출력되도록 설정하기만 하면 지극히 기본적인 구구단 출력 문제이다. public class JavaStudy01 { public static void main(String[] args){ for (int i = 1; i < 10; i++){ for (int j = 1; j < 10; j++){ System.out.print(String.format("%02d", j) + " x " + String.format("%02d", i) + " = " + String.format("%02d", i * j) + "\t")..
힙(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의 방식을 따른다. 임의의 위치에 존재하는 원소의 삭제 연산은 해당 원소에 딸려있는 모든 원소들을 삭제해야 한다. 조건해석과 구현 방법 이전에 수행했던 조건과 동일하므로 해석 역시 동일하다. 눈여겨보아야 할 점은 임의의 위치에 존재하는 원소의 삭제 연산이다. 해당 원소에 딸려있는 모든 원소를 삭제해야한다는 것은 해당 원소를 루트로 ..