알고리즘 온라인 저지 (48) 썸네일형 리스트형 자료구조 구현 : 레드 블랙 트리 (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)가 존재하지 않으며, 노드 간의 부모 자식 관계가 추가된 자료구조이다. 나무를 뒤집어 놓은 것과 .. BOJ 14890번 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 백준 14890 경사로 문제는 오래간만에 풀어보는 구현 문제였다. 사실 깡구현에 가깝기 때문에 한 경로가 경사로 건설을 통해 이동 가능한지 판별하는 아이디어 부분만 설명하고자 한다. 특별한 알고리즘을 요구한다는 느낌이 없었기 때문에 이러한 느낌으로 직접 구현했다. 만약 더 좋은 아이디어가 있다면 가르침을 바랍니다. code: GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지 알고리즘 온라인 저지. Contribute to YoungWoo93.. BOJ 13334번 철로 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 백준 13334번 철도 문제는 우선순위 큐를 이용한다면 의외로 간단하게 풀 수 있는 문제다. 우선순위 큐에 대하여 잘 모른다면 아래의 더보기 포스팅을 참고하자. 더보기 자료구조 개념 : 우선순위 큐 (Priority Queue) + 힙 (Heap) 우선순위 큐는 일반적인 선입 선출형의 큐에 우선순위를 추가한 개념이다. 비유하자면 에버랜드나 롯데월드 등 에서 놀이기구를 타기 위해 줄을 선 것이 일반적인 큐라고 하자.. BOJ 1937번 욕심쟁이 판다 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 백준 1937번 욕심쟁이 판다 문제는 정답을 구하기 위한 DFS와 속도를 늘리기 위한 DP를 조합하여 풀 수 있다. 깊이 우선 탐색(DFS)과 동적 계획법(DP)에 대해 잘 모른다면 아래의 더보기 포스팅을 참고하자. 더보기 알고리즘 : 깊이 우선 탐색(DFS) 우선 그래프, 트리, 스택 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는 것이 좋다. 더보기 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 그래.. BOJ 1114번 통나무 자르기 1114번: 통나무 자르기 첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출 www.acmicpc.net 백준 1114번 통나무 자르기 문제는 이분 탐색에 미숙하던 과거의 나에게 충격을 줬던 문제다. 과거 이분 탐색을 사용할 때 에는 정해진 크기의 배열 (또는 벡터 등)이 있을 때, 저장된 데이터에 대하여만 이분 탐색을 수행했었다. 하지만 이런 유형의 문제를 풀고 난 뒤, 하나의 고정관념이 사라졌다. 저장되있지 않은 대상에게도 이분 탐색을 적용할 수 있다는 깨달음을 얻은 것이다. 우선 문제 자체는 이분 탐색을 이용하면 간단한 문제이므로 이분탐색 알고리즘 자체에.. 자료구조 개념 : 우선순위 큐 (Priority Queue) + 힙 (Heap) 우선순위 큐는 일반적인 선입 선출형의 큐에 우선순위를 추가한 개념이다. 비유하자면 에버랜드나 롯데월드 등 에서 놀이기구를 타기 위해 줄을 선 것이 일반적인 큐라고 하자. 모든 손님은 먼저 온 순서대로 놀이기구에 탑승할 수 있다. 그런데 언제부터인가 Q패스, 매직 패스의 개념이 생기며 대기열에도 우선순위가 생겼다. 이제 놀이기구 대기열은 아래와 같이 우선순위 큐처럼 동작한다. 1. 일반 손님은 먼저 온 순서대로 놀이기구에 탑승할 수 있다. 2. Q패스, 매직 패스처럼 일반 대기열을 쓰지 않고 빠르게 탑승할 수 있는 대기열이 존재한다. 즉 우선순위 큐를 이해하기 위해서 큐에 대한 이해가 선행되어야 한다. 또한 일반적인 우선순위 큐를 구현하데 가장 효율적이라 평가되는 힙을 설명할 것 이기 때문에 트리에 대해서.. 이전 1 2 3 4 ··· 6 다음
