본문 바로가기

Archived(CSE Programming)

 (169)
레드블랙 트리(Red Black Tree) (변형이진탐색트리) 레드 블랙 트리는 효율적인 탐색을 위해 BST의 height를 낮추는방식으로 고안된 트리이다.다음의 3 가지 조건을 만족해야 한다. 루트 노드와 외부 노드는 Black 노드이다Red 노드가 연속해서 올 수 없다루트로부터 외부 노드로 까지의 가는 경로에서 count 되는 Black 노드의 수는 같다 (최대 경로는 최소 경로의 두배 이하이다) 그리고 이러한 조건을 만족시키기 위해 삽입 시에는 Red 노드로 삽입을 고정시키는 것이 유리하다(블랙 노드로 삽입시 조건 3을 위배시키기 쉬워서 이런 경우에는 복잡한 처리를 수행해야 하기 때문) Red 노드로 삽입 후에는 조건 2만 체크를 하면 된다. 조건 2를 만족시키기 위해 4가지 Case가 있는데 다음과 같다.(right에 삽입되었을 경우를 합치면 총 8가지 ca..
AVL Tree(변형 이진탐색트리) AVL Tree 이진탐색트리(BST, Binary Search Tree)의 효율성은 최대한의 높이(height)를 낮추는 것에 있다. 탐색, 삽입, 삭제와 같은 연산 시의 시간복잡도는 O(h)일 만큼 height에 달려있기에 height를 낮추는 것이 이진탐색트리의 효율성을 높이는 방법이 될 수 있다. 그래서 이진탐색트리(이하 BST)의 효율성을 최대로 살리기 위해 height를 낮추는 방법 중 가장 대표적인 방법으로 AVL 트리를 들 수 있다. 초기에 제안되었던 방식으로 G.M. Adelson-Velskii와 E.M. Landis가 자신들의 이름을 따서 AVL Tree로 명하였다. 핵심은 높이를 낮추는 것으로 Balanced Factor(bf, 또는 높이)를 비교하여 좌측 서브트리와 우측 서브트리의 높..
이진탐색트리(Binary Search Tree, BST) 이진탐색트리(BST) 이진탐색트리는 트리의 대표적인 형태로 말 그대로 이진트리 중에서도 탐색에 특화된 트리이다. 탐색에 특화된 이유는 트리 내부 부모노드의 값은 왼쪽 자식노드의 값보다 크고 오른쪽 자식노드의 값보다 작다는 특성을 지니고 있기 때문이다. 그래서 실제 값이 들어있는 이진탐색트리를 살펴보면 아래와 같다. 이 트리를 전위순회방식으로 탐색하면 "1 3 4 6 7 8 10 13 14" 로 값을 오름차순으로 출력할 수 있다. 즉 아까의 특성 때문에 값을 찾기 쉽기 때문에 이진탐색트리라고 한다. 이진탐색트리는 Node와 NodePointer를 통해서 구현할 수 있는데, 아까의 특성을 지키기 위해 아래의 로직으로 구현할 수 있다. 삽입은 삽입하고자 하는 값이 부모노드보다 작으면 왼쪽 자식노드로, 크면 오..
우선순위 큐(Priority Queue) / 힙(Heap) 우선순위 큐(Priority Queue) 우선순위 큐는 말 그대로 Queue 중에서도 특별한 Queue이다. 우선순위를 가지는 큐로써, 가장 우선순위가 높은 자료가 가장 먼저 출력되는 구조를 지닌다. 아래처럼, 완전히 정렬된 형태는 아니지만 출력은 언제나 우선순위가 가장 높은 자료형이 반환된다. 따라서, 출력될 때 우선순위가 가장 높은 자료가 나올 수 있도록 삽입, 삭제가 이루어져야 한다. 삽입과 삭제의 연산에서 많은 연산들이 소모되어서 비효율적으로 보일 수 있지만 언제나 우선순위가 높은 자료형을 O(1)로 꺼낼 수 있기에 이러한 자료형이 필요시 될 때도 있다. 구현 방법에는 다양한 방법이 있지만 Heap을 통해서 우선순위 큐를 구현하는 것이 가장 이상적이다. 아래의 두가지를 만족하는 자료형을 Heap이..
스택(Stack)과 큐(Queue), 순환 큐(Circular Queue) 스택(Stack) 스택(Stack)은 LIFO(Last In First Out)을 표현하는 대표적인 선형 자료구조 이다. 나중에 입력한 값이 먼저 출력되는 구조이다. 그래서 일반적인 스택은 top이라는 하나의 공간을 통해 입출력이 일어난다. 배열을 통해서 많이 표현하는데 아래와 같이 표현할 수 있다. 위와 같이 top이라는 하나의 공간을 통해 값을 입력, 출력한다. 삽입은 top이 가르키는 공간의 다음 공간으로 이동하여 삽입한다. 삭제는 top이 가르키는 공간의 자료를 꺼낸뒤 top은 이전 공간으로 이동한다. top이 -1일 경우 STACK은 비어있는 상태이다. top이 배열의 마지막 공간을 가르키고 있을 경우 STACK은 가득찬 상태이다. 스택(Stack) 구현 #include #define MAX_S..
프로그래머스 - 이중우선순위 큐(Java, LV3) https://programmers.co.kr/learn/courses/30/lessons/42628?language=java 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이 우선순위큐(heap)을 오름차순, 내림차순(Collections.reverseOrder()) 기준으로 하나씩 만든다 삽입의 경우 두 heap에 각각 넣어준다 최대값 삭제의 경우 내림차순 우선순위큐에서 최대값을 찾아서 두 heap에 remove 한다 최소값 삭제의 경우 오름차순 우선순위큐에서 최솟값을 찾아서 두 heap에 remove 한다 결과값을 출력하는데 heap이 empty가 아닐 경우에만 값을 넣어 출력한다 import java.util.*; class Solution { public int[] solu..
프로그래머스 - 디스크 컨트롤러(Java, LV3) / Heap https://programmers.co.kr/learn/courses/30/lessons/42627?language=java 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 Job 들에 대해서 시간이 빠른순으로 정렬(같을 경우 짧은 시간 순) Job 들을 작업시간이 짧은 순으로 우선순위 큐에 보관한다 현재 시간(t) 기준으로 작업수행이 가능한 Job들을 우선순위 큐에 넣고 반복문을 통해서 하나씩 꺼내서 수행한다 수행한 뒤 다시 현재 시간을 경과된 작업시간만큼 더해주고 다시 작업수행이 가능한 Job..
프로그래머스 - 카카오프렌즈 컬러링북(Java, 2017카카오) https://programmers.co.kr/learn/courses/30/lessons/1829?language=java 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이 전체 그래프에서 탐색할 영역 중 영역 0(배경색)을 제외한다 그래프 중 방문하지 않은 곳을 찾아서 그곳을 시작점으로 같은 색으로만 DFS 탐색을 한다. DFS 탐색을 하면서 영역의 수를 count하고, count한 영역이 최대영역 크기보다 크면 갱신한다. DFS 가 끝나면 전체 그래프 중에서 다시 탐색하지 않은 곳을 찾아서 DFS 탐색..

티스토리툴바