알고리즘 온라인 저지/알고리즘 | 자료구조 (14) 썸네일형 리스트형 자료구조 구현 : 레드 블랙 트리 (Red Black Tree, RB tree) - 삭제 자료구조 개념 : 레드 블랙 트리 (Red Black Tree, RB tree) 레드 블랙 트리는 일반 이진트리에서 자식들이 한쪽으로 치우치는 것을 막기 위한 균형 기능이 추가된 트리이다. 이를 자가 균형 이진트리(Self-balancing binary tree)라 부른다. 자가 균형 이진트리 dev-game-standalone.tistory.com 이전 포스팅에서 RB 트리의 4가지 조건을 알아보았다. 이 4가지 규칙 중 삽입과 삭제에서 핵심이 되는 규칙은 모든 red는 black 자식을 갖는다. (= red가 red의 부모가 될 수 없다.) 임의의 노드에서 출발하는 모든 경로는 모두 같은 수의 black 노드가 존재한다. 두 가지가 있다. 이 두 가지를 유의하며 RB 트리의 삭제를 살펴보자. 우선 R.. 자료구조 구현 : 레드 블랙 트리 (Red Black Tree, RB tree) - 삽입 자료구조 개념 : 레드 블랙 트리 (Red Black Tree, RB tree) 레드 블랙 트리는 일반 이진트리에서 자식들이 한쪽으로 치우치는 것을 막기 위한 균형 기능이 추가된 트리이다. 이를 자가 균형 이진트리(Self-balancing binary tree)라 부른다. 자가 균형 이진트리 dev-game-standalone.tistory.com 이전 포스팅에서 RB 트리의 4가지 조건을 알아보았다. 이 4가지 규칙 중 삽입과 삭제에서 핵심이 되는 규칙은 모든 red는 black 자식을 갖는다. (= red가 red의 부모가 될 수 없다.) 임의의 노드에서 출발하는 모든 경로는 모두 같은 수의 black 노드가 존재한다. 두 가지가 있다. 이 두 가지를 유의하며 RB 트리의 삽입을 살펴보자. RB 트.. 자료구조 개념 : 레드 블랙 트리 (Red Black Tree, RB tree) 레드 블랙 트리는 일반 이진트리에서 자식들이 한쪽으로 치우치는 것을 막기 위한 균형 기능이 추가된 트리이다. 이를 자가 균형 이진트리(Self-balancing binary tree)라 부른다. 자가 균형 이진트리는 대표적으로 자식의 Depth를 이용하는 AVL 트리와, 노드의 색을 이용하는 Red Black Tree 등이 있다. 이중 노드의 색을 이용한 Red Black Tree (이하 RB 트리)에 대한 설명을 하고자 한다. 트리에 대해 알고 있어야 하며, AVL 트리와 비교하기 좋으므로 이 부분은 더보기를 참고하자. 더보기 자료구조 트리 (tree) 트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가 추가된 자료구조이다. 나무를 뒤집어 놓은 것과 .. 자료구조 개념 : 우선순위 큐 (Priority Queue) + 힙 (Heap) 우선순위 큐는 일반적인 선입 선출형의 큐에 우선순위를 추가한 개념이다. 비유하자면 에버랜드나 롯데월드 등 에서 놀이기구를 타기 위해 줄을 선 것이 일반적인 큐라고 하자. 모든 손님은 먼저 온 순서대로 놀이기구에 탑승할 수 있다. 그런데 언제부터인가 Q패스, 매직 패스의 개념이 생기며 대기열에도 우선순위가 생겼다. 이제 놀이기구 대기열은 아래와 같이 우선순위 큐처럼 동작한다. 1. 일반 손님은 먼저 온 순서대로 놀이기구에 탑승할 수 있다. 2. Q패스, 매직 패스처럼 일반 대기열을 쓰지 않고 빠르게 탑승할 수 있는 대기열이 존재한다. 즉 우선순위 큐를 이해하기 위해서 큐에 대한 이해가 선행되어야 한다. 또한 일반적인 우선순위 큐를 구현하데 가장 효율적이라 평가되는 힙을 설명할 것 이기 때문에 트리에 대해서.. 자료구조 덱(deque, dequeue) 자료구조 덱은 Double Ended QUEue의 축약어로, "deck"으로 발음하게 되어있다. 하지만 데크, 디큐 등의 표기나 발음이 존재할 수 있기 때문에 문맥에 맞는 내용을 선택하자. (사실 '디큐'는 값을 꺼내는 디큐잉이랑 혼동되기 때문에 거의 본 적이 없다.) 덱의 풀네임인 double ended queue에서 알 수 있듯 기본적으로 큐의 동작을 양방향으로 지원하는 자료구조이다. 우선 큐에 대하여 잘 모른다면 더보기의 큐를 선행 학습하고 돌아오자. 더보기 자료구조 큐 (queue) 큐는 선입 선출(First In First Out : FIFO) 형태의 자료구조이다. 큐는 들어온 순서를 이용하는 기능에서 적절하게 사용할 수 있다. 더보기 들어온 순서를 이용하기 위해 큐를 이용한 예시 : 2022... 알고리즘 : 탐욕법 (Greedy) 탐욕법은 문제의 특징을 이용해, 탐색 횟수 자체를 줄여 속도를 향상시키는 일종의 테크닉이다. 탐욕법(이하 그리디)은 휴리스틱 알고리즘으로서, 그 순간의 최적을 취해 나가는 형태로 구성된다. 휴리스틱에 대해 아직 공부하지 않은 채로 위 문장을 보면 이해가 가지 않을 것이다. 하지만 DP와 마찬가지로 그리디 또한 우리가 본능적으로 사용할 수 있는 개념이다. 우리가 본능적으로 시행하고 있는 그리디 문제를 하나 제시해 보겠다. 바구니에 구슬이 15개 있는데, 이 구슬에는 1부터 15까지의 숫자가 적혀있다. 당신은 바구니에서 구슬을 하나씩 뽑아 가져 갈 수 있는데, 구슬들에 적힌 숫자의 합이 30 이 되어야 되도록 구슬을 가져갈 수 있다. 예를 들어 9, 10, 11 구슬을 뽑으면 셋 다 가져갈 수 있지만 13,.. 알고리즘 : 동적 계획법 (Dynamic Programming, DP) 동적 계획법은 메모리를 추가로 사용하여 속도를 향상시키는 일종의 테크닉이다. 동적 계획법(이하 DP)은 코딩 테스트 등의 알고리즘 문제를 풀 때 강한 위력을 보이는데 사실 DP 개념은 단지 알고리즘 문제에 국한되지 않는다. 일상생활에서도 우리는 DP를 하고 있다. 계산 중간결과를 적어두거나, 검색해둔 정보를 다시 찾을 필요 없도록 메모장에 모아두는 행위도 DP의 개념이 일부 들어간 행동이라고 할 수 있다. DP의 대표적 예시는 N번째 피보나치수열의 값을 구하거나, N! (N 팩토리얼)의 값을 구하는 것 등이 있다. 이중 N 팩토리얼을 구하는 문제를 통해 DP의 동작을 보이려고 한다. DP의 아이디어는 "반복해서 연산을 해야하는 부분을 어딘가에 저장해 두고 재사용하자!"이다. 위의 예시에서 5 팩토리얼을 .. 알고리즘 : 이진 탐색 (=이분 탐색, binary search) 이진 탐색은 정렬이 되어있는 N개의 데이터를 대상으로 log(N) 시간 탐색을 할 수 있는 알고리즘이다. 이진 탐색의 대상은 트리(특별히 이진 탐색을 위한 트리를 이진 탐색 트리, binary search tree라고 부른다.)가 될 수도 있고. 배열이 될 수 도 있다. (이경우 배열은 비교하기 위한 기준에 의해 정렬되어있어야 한다.) 심지어는 임의의 정수 영역에 대한 이진 탐색을 수행할 수도 있다. 만약 정렬이 되어있지 않으면 이진 탐색이 불가능하기 때문에, 이진 탐색 트리, 수 영역에 대한 이진 탐색이 아니라면 탐색의 대상을 정렬하는 행위가 선행되어야 한다. (이진 탐색 트리는 삽입 시점에서 정렬을 하면서 삽입을 한다, 수 영역은 개념적으로 정렬이 되어있다.) 포스팅의 예시는 배열을 대상으로 진행하며.. 이전 1 2 다음
