본문 바로가기

알고리즘

 (82)
레드 블랙 트리(red black tree) 레드 블랙 트리란 AVL와 비슷하게 자가 균형 이진 탐색 트리지만 다른 점이 있다. AVL에선 삽입, 삭제가 발생할 때마다 균형을 조정해야 하는 문제가 있다. 아무리 $\log(N)$의 시간 복잡도를 보장한다 해도 수천만의 쓰기 작업이 발생하면 $N\log(N) $ 시간 복잡도로 문제가 복잡해진다. 이런 문제를 해결하기 위해 레드 블랙 트리에선 삽입, 삭제 작업에서 발생하는 균형 조정을 느슨하게 대처한다. 하지만 이로 인해 탐색에선 AVL보다 균일한 시간 복잡도를 제공하진 않는다. 레드 블랙 트리의 성질 루트 노드는 언제나 블랙 노드다. Nil Node 우리가 생각하는 말단 노드의 하위 노드에 암묵적으로 Nil Node가 생긴다고 보면 된다. Nil Node는 실제 데이터가 아니기 때문에 트리의 높이 계..
이진 힙(binary heap) 이진 힙이란? 완전 이진트리(Complete Binary Tree)의 한 형태로 힙 정렬, 또는 우선순위 큐에 사용된다. 이진 힙은 다음 2가지 특성을 가지고 있다. 완전 이진 트리와 동일하게 모든 레벨이 완전히 채워져 있다. 마지막 레벨은 왼쪽부터 순서대로 채워진다. 모든 부모 노드는 자식 노드보다 큰 값을 가진다. 이 경우, 최대 힙(Max Heap) 이라고 한다. 반대로 부모 노드가 자식 노드보다 작은 값을 가지면 최소 힙(Min Heap)이라고 한다. 이 글에선 최소 힙을 기준으로 설명한다. 힙 선언 class Heap { private int[] heapArray; private int tail = 0; private int capacity; public Heap(int capacity) { t..
AVL 트리 (Adelson-Velsky and Landis Tree) 이진 탐색 트리의 문제점 상위 노드를 기준으로 작으면 왼쪽, 크면 오른쪽으로 보내기 때문에 들어오는 순서에 따라 한 방향으로 치우칠 수 있다. 우리는 이것을 치우친 이진 트리(Skewed Binary Tree)라고 부른다. AVL 트리란? 모든 리프 노드들의 레벨 차이는 1 이하 트리의 높이는 logN 삽입, 삭제, 탐색 연산에서 최악의 경우에도 O(logN)의 시간 복잡도를 보장한다. Balance Factor 각 노드는 아래 공식으로 balance factor 수치를 계산해 트리의 균형 유무를 판단한다. balance factor = 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이 balance factor > 1: 왼쪽 서브 트리에서 불균형 발생 balance factor < -1: 오른쪽 서브 트..
이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리란 이진 트리에서 데이터의 크기를 판단해 탐색하는 트리 부모 노드를 기준으로 작은 값은 왼쪽 서브 트리로, 큰 값은 오른쪽 서브 트리로 배치된다. 따라서 맨 왼쪽 리프 노드는 트리의 최솟값이고, 맨 오른쪽 리프 노드는 트리의 최댓값이다. 이를 이용해 값을 찾을 때 대소 비교를 통해 탐색 방향을 정한다. 매 탐색마다 경우의 수가 절반씩 줄어들기 때문에 삽입, 삭제, 탐색에서 logN의 시간 복잡도를 가진다. 이진 탐색 트리의 문제 오름차순 또는 내림차순 된 리스트를 순차적으로 저장하는 경우 트리의 방향이 한쪽으로 치우치는 편향 이진 트리가 된다. 이경우, logN의 시간 복잡도가 아닌 O(N)의 시간 복잡도가 발생한다. 노드 정의 private static class Node { int da..
트리, 이진트리 트리란? 노드들이 연결된 비선형 자료구조. 루트 노드라 불리는 최상위 노드에서 시작해 여러 하위 노드로 확장되는 계측정 구조. 한 노드가 여러 노드와 연결돼 있다. 트리는 사이클이 존재하지 않는다. 즉, 탐색을 수행할 때 시작 노드와 종료 노드가 동일한 경로가 없다. 트리의 용어 노드(Node): 트리의 기본 단위 루트 노드(Root Node): 트리의 최상위 노드. 트리는 하나의 루트 노드를 가진다. 부모 노드(Parent Node): 자식 노드를 가지는 노드 자식 노드(Childe Node): 특정 노드의 하위 계층에 있는 노드 리프 노드(Leaf Node): 자식 노드를 가지지 않는 노드 즉, 최말단 노드 형제 노드(Sibling Node): 같은 부모 노드를 둔 노드들 레벨(Level): 지정된 ..
백준[1113] 수영장 만들기 (Python3) 물을 채울 수 있는 조건은 다음과 같다. 현재 높이를 A라 할 때 높이 A와 이어지는 영역은 테두리에 닿으면 안 된다. (물이 땅으로 흐름) 상하좌우의 높이가 A보다 작으면 안 된다. (작은 쪽 높이가 테두리로 이어짐) 한번 채워진 영역은 다시 한번 더 채워질 수 있기에 (예제 2번 기준) 높이가 낮은 곳부터 탐색을 해야 한다고 생각했다. 코드의 흐름은 다음과 같다. 찾을 높이를 1 ~ 9까지 정하고 이 높이를 wall이라 한다. (main 함수) wall 값과 동일한 값을 가진 가진 좌표들을 구한다. (findWall 함수) 만약 테두리와 이어지면 무효 상하좌우로 탐색한 높이의 최솟값이 wall보다 낮으면 무효 wall 보다 큰 값이 없다면, 해당 영역에 물을 채울 수 없으니 무효 영역을 구하면 상하좌..
프로그래머스 - 인사고과 값을 여러 쌍을 준 뒤, 특정한 인덱스가 몇 번째로 위치하는지에 대한 문제를 프로그래머스에서 몇 번 본듯한 기억이 있었다. 지금 정리해두면 나중에 유용하다 생각해 글을 쓰게 됐다. 완전 탐색 1. 태도, 동료 점수 모두 자신보다 큰 사원이 있을 경우 해당 사원을 제외한다. 2. 각 사원들의 점수 총합을 구한 뒤, 점수를 기준으로 내림차순 정렬을 해 원호가 몇 번째로 큰지 본다. 만약, 원호가 제외됐을 경우 -1을 반환한다. 시간복잡도 계산 1번의 경우 모든 사원을 봐야 하기 때문에 N^2의 시간 복잡도 발생 2번의 경우 정렬에 Nlog(N), 원호의 위치를 찾는 과정에서 N의 시간 복잡도 발생 총 시간 복잡도는 N^2 + Nlog(N) + N으로, N = 100,000이기에 시간 초과가 발생한다. 틀린 ..
백준[1981] 배열에서 이동 (Python3) 완전 탐색 배열을 모두 순회하는데 O(100 * 100) 이 필요하다. 최대 - 최소의 경우, 차이가 1이라 할 때, 차이가 1이 되는 최대, 최소의 쌍은 (1, 2), (2, 3), (3, 4), ... (199, 200) 식이다. 차이가 최대 200까지 발생하니, 쌍을 구하는 것에 대한 시간 복잡도는 (199 + 198 + 197 + ... + 0) = 약 20,000 정도 된다. 총 시간 복잡도는 O(100^2) * O(199 + 198 + ... + 0) = 2억으로 시간 초과가 발생한다. 완전 탐색 최적화 배열을 일부만 탐색할 수는 없으니, 쌍을 구하는 과정에서 최적화를 수행해야 한다. 하지만, 어떤 최대, 최소의 차이 A를 구하기 위해선, 이를 만족하는 모든 경우를 확인해야만 한다. 따라서, ..

티스토리툴바