![]()
본 내용은 위키피디아 “Red-black tree”를 기반으로 관련 논문과 개인적인 이해를 바탕으로 작성하였습니다. 소개 Red-black tree(이하 “RB Tree”)는 일종의 자기 균형 이진 탐색 트리(Self-Balancing BST)입니다. 먼저 이진 탐색 트리란, 자신의 왼쪽 서브 트리에는 현재 노드보다 값이 작은 것, 오른쪽 서브 트리에는 값이 큰 것들만 가질 수 있습니다. 이러한 특성 때문에 이진 탐색 트리의 조회는 O(log n) 시간이 걸리게 되는데 다만 문제는 균형이 무너질 경우 O(N)까지 시간이 증가할 수 있다는 점입니다. 따라서 지금까지도 균형을 맞추기 위해 여러 자료 구조들을 개발하고 있습니다. (이진 탐색 트리 참고 : https://yoongrammer.tistory.co..
![]()
그리디 알고리즘(Greedy Algorithm)은 "탐욕적인"이라는 뜻의 greedy에서 유래된 알고리즘이다. 다른 말로 "욕심쟁이 기법" 이라고도 부르는데 만약 여러 노드를 갖는 그래프에서 A노드 -> B노드까지의 경로를 탐색하려 할 때 모든 경로를 고려하지 않고 단지, 현재의 위치(노드)에서 가장 최적의 경로(예를 들면 에지의 가중치가 작은) 를 도착지까지 매 순간마다 가장 좋은 방법만을 선택하는 방법이다. 다익스트라 알고리즘도 그리디 알고리즘의 한 예시인데 간단히 설명하자면, 한 노드를 시작점으로 출발해 목적지에 연결될 때 까지 현재 연결된 노드로부터 연결된 에지들의 가중치 중 최소만을 선택하는 방법을 말한다. (사이클이 생기지 않는 선에서) 만약 위 그림에서 노드 1->6 까지의 최단 거리를 구하..
![]()
알고리즘이란?? 문제를 해결하기 위한 절차나 방법을 말한다 알고리즘이란 단어의 정의는 대수학의 아버지 알-콰리즈마의 이름에서 유래되었다고 전해지는데, 오늘 날 어떤 문제를 푸는 알고리즘이란 어떤 입력에서 정확한 출력을 유한한 시간에 내는 프로그램을 일컫는다. 여기서 어떤 입력이란? 주어진 입력의 크기와 관계없이 문제를 풀 수 있음을 뜻하는데 문제에 따라서는 음수도 될 수 있고 매우 크거나 작은 수(double 자료형의 범위 밖)가 될 수도 있다. 정확한 출력은 말 그대로 코드를 짠 프로그래머가 원하는 결과값을 나오게함을 의미한다. 유한한 시간은 여러 알고리즘 문제 사이트에서 볼 수 있는 시간 제한 내에 풀 수 있는지를 뜻한다. 예를 들어 내가 짠 코드가 무한루프에 빠지게 되거나 정말 터무니없는 반복을 할..
![]()
보통 우리가 많은 양의 정수, 실수형 배열에 대한 구간 합, 최대치 등을 구할 경우 구간 트리(세그먼트 트리, 펜윅 트리)를 만들어 O(log n) 만에 검색을 할 수 있게 된다. 하지만 문자열을 다룰 때에는 정수, 실수 등 크기가 정적인 변수들을 다루는 것과 좀 다른데 문자열의 경우 문자열 변수를 비교하는 데에 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문이다. (정수처럼 한 번에 비교가 되는 자료형이 아니기 때문입니다.) 따라서 정수형 배열에서 원하는 원소를 찾을 때 O(log n)이 걸렸다면, 같은 알고리즘으로 원하는 문자열을 찾으려면 문자열의 길이 |S|을 곱한 O(|S| log n) 이 걸리게 된다. 이런 문제를 해결하기 위해 문자열을 찾는 문제에서 우리는 더 나은 자료 구조를 찾을 ..
![]()
문제를 풀다가 다른 사람 코드를 봤더니 queue를 쓰던 map을 쓰던 새로운 요소 혹은 객체를 삽입할 때 make_pair, make_tuple을 이용해 객체를 만들고 push 하는 것이 아니라 그냥 emplace 함수를 이용해 간편하게 넣는 걸 보고 간편하다고 생각되어 찾아보니 효율도 대체적으로 좋은 듯하여 따로 찾아 정리를 해본다. (안 좋은 경우도 있다고 합니다.) 1. 정의 c++ reference 에서 emplace를 찾아보니 이러한 설명이 나왔다. 컨테이너에 키가있는 요소가 없는 경우 지정된 인수로 구성된 컨테이너에 새 요소를 삽입한다. emplace를 주의해서 사용하면 불필요한 복사 또는 이동 작업을 피하면서 새로운 요소를 구성할 수 있다. 반복자 및 참조자가 무효화되지 않는다. 여기서 말..
1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데 연속된 부분 문자열을 나타내는 부분 문자열(Substring) 도 있다. (따라서 string 헤더파일의 substr()은 substring을 의미한다) 두 부분 문자열의 차이는 예를 들자면 pringles sangeles 이렇게 두 문자열이 있을 때 가장 긴 Subsequence는 pringles sangeles "ngles" 가 되고 가장 긴 Substring은 pringles sangeles "les" 가 된다. 위에서 알 수 있듯 가장 긴 Substring은 ..
![]()
위상 정렬은 사이클이 없는 단방향 그래프에서 그래프의 간선 u, v 가 있을 때, 정점의 순서를 찾는 알고리즘입니다. 위상 정렬을 구현할 때는 bfs를 사용합니다. 예를 들어 이런식으로 구성된 그래프가 있다고 합시다. 여기서 중요한건 위상 정렬을 사용하기 위해선 반드시 모든 간선이 한 방향을 향하고 있어야 한다는 점입니다. 이 그래프가 주어졌을 때 가장 먼저 해야하는 일은 각 노드의 차수를 계산해야 합니다. 차수를 계산하는 방법은 일반적인 그래프와 살짝다른데, 일반적으로는 트리의 높이가 그 노드의 차수였다면 여기서는 연결되어있는 부모의 수가 그 노드의 차수가 됩니다. 차수가 0인 노드 : 4, 5, 3 차수가 1인 노드 : 2, 7, 8 차수가 2인 노드 : 6, 1 차수를 기록했으면 이제 부모가 존재하..
![]()
유니온 파인드(Union Find)란? 서로소 집합 자료구조(Disjoint-set)이라는 알고리즘으로도 불리며, 서로 다른 부분집합 간의 병합(Union) 과정을 의미한다. 유니온 파인드는 서로 다른 집합을 합치거나, 한 집합이 다른 집합에 속해있는지를 확인하는 연산 두 가지로 이루어져있는데, 전자를 Union 이라하며, 후자를 Find라고 한다. 참고로 유니온 파인드는 집합이지만 트리로 생각하여 푸는 건데, 아래에서 설명하겠다. 1. 초기화 : 유니온 파인드는 우선 처음에 자기 자신을 루트라고 정하고 시작한다. 1 2 3 for (int i = 0; i 현재 부분집합 = {1,2}, {3,4,5} 그렇다면 2개 이상의 부분집합끼리도 붙일 수 있을까? 4)Union(2,5) 어라? 분명 {3,4,5}를..
![]()
이진 탐색트리란? 이진 탐색트리는 다음과 같은 속성이 있는 자료 구조이다. 각 노드에 값이 있고, 각 노드마다 최대 두 개의 자식을 갖는다. 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다. 이진 탐색트리 예시 {8,3,10,1,6,14,4,7,13} 이 노드를 기준으로, 루트 8 의 왼쪽 서브트리는 3부터 그 이하의 노드들로 이루어진 트리이고, 루트 8 의 오른쪽 서브트리는 10부터 그 밑에있는 노드들로 이루어진 트리이다. 이진 탐색 트리는 유일하지 않다. 예를 들어 {1, 2, 3, 4}에 대한 이진 탐색 트리는 이런식으로 두가지 이상으로 표현 가능하다. 만약 어떤 키 값이 자주 접근될 지 모른다면, 균형잡힌 오른쪽 트리가 유리할 것이고, 만약 1 값이 가장 자주 접근된다면..
![]()
기본 아이디어 -> 버블 정렬과 비슷하다. 1등을 뽑아내고 (최대 힙의 루트), 나머지 원소에서 1등을 계속 뽑아내면 정렬이다. 버블 정렬과 다른점 -> 1등을 뽑아낸 뒤, 나머지 원소에서 1등을 뽑을 때 다시 비교할 필요 없이 2등이 자동으로 1등이 된다. (루트 원소를 제거 한 후 -> 힙을 유지하는 방식) 힙이란? 힙의 성질 1. 리프 노드를 제외한 모든 노드는 자식이 반드시 둘이다. 완전 이진트리에서 리프 노드가 어떤 노드 이후부터 모두 생략된 형태이다. 트리를 배열로 표현할 수 있다. (노드의 왼쪽 자식 : node * 2, 오른쪽 자식 : node * 2 + 1) 1 2 3 4 5 최대 힙 (max heap) 정의 : 각 노드들이 (루트 포함) 자식들보다 큰 힙 최대 힙에서 루트 원소 제거 여..
![]()
병합 정렬 정의 : 분할 정복 알고리즘의 하나로 정렬되지 않은 리스트를 잘라 나누어 정렬 한 후 다시 병합하는 정렬기법이다. 작동 방식 1. 분할: 정렬 되지 않은 리스트를 절반으로 나누어 두 부분 리스트로 나눈다. 이를 눈에 보일만큼 작은 크기로 나누어 질 때까지 계속 실행한다 2. 정복: 나누어진 리스트들을 재귀적으로 다시 정렬한다. 3. 결합: 정렬된 리스트들을 하나의 배열에 병합한다. 작동 방식만 보고는 이해가 안되니 바로 그림으로 살펴 보도록 하자. 위 그림은 초기 배열 [3,1,7,2,8,4,6,5]를 밑에서 부터 위로 정렬하는 Down-Top 방식의 병합 정렬이다. 알고리즘의 진행 1. 전체 리스트의 앞의 반, 뒤의 반을 병합 정렬을 통해서 정렬 2. 병합 정렬에 의해서 앞의 반, 뒤의 반 ..
버블 정렬 정의 : 버블 정렬은 말 그대로 거품 정렬이다. 리스트 안의 원소들이 점점 뒤로 밀려들어가기 때문에 이 모습이 마치 거품이 수면위로 올라오는 듯한 모습처럼 보여 지어진 이름이다. 방법 : 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가(내림차순인 경우 작은 수가) 오른쪽으로 가도록 교환한다. 이 때 맨 끝과 그 앞의 원소까지 비교하면, 가장 큰 원소(또는 가장 작은 원소)를 찾은 것이므로, 다시 나머지 n-1개 수에 대하여 다시 반복한다. 예시 9 5 2 4 1 라는 배열이 있다고 가정하자. 오름차순을 만드는 버블 정렬을 순차적으로 표현하면 9 5 2 4 1 -> 5 9 2 4 1 -> 5 2 9 4 1 -> 5 2 4 9 1 -> 5 2 4 1 9 5 2 4 1 9 -> 2 5..
