아무 말

INTRODUCTION 이번 포스팅에서는 최대 연속 부분합을 다루는 세그먼트 트리에 대해 다루고자 한다. 이 기술은 대한민국에서 특히 더 잘 알려져 있다. 2014년 한국정보올림피아드 중등부 4번 문제 금광을 통해 유명해졌으며 이로 인해 주로 "금광 세그"라는 이름으로 불린다. 해당 세그먼트 트리에 관해서는 Codeforces에서 찾을 수 있는 ITMO Academy: pilot course에서도 다루었다. 강의가 필요하다면 확인하기 바란다. https://codeforces.com/edu/course/2/lesson/4/2 Courses - Codeforces codeforces.com IDEA 우리가 segment tree를 이용할 때를 생각해 보자. tree의 노드가 관리하는 segment를 다른 ..

들어가며.. 이전에 Heavy-Light Decomposition에 대해 다룬 적이 있다. 이는 트리를 몇개의 선형 배열로 바꾸는 것이며, 주로 특정한 두 정점을 잇는 경로에 포함되는 간선의 가중치나 정점에 관한 쿼리를 처리하는 데에 이용된다. 그렇다면, 해당 노드와 그 노드의 모든 자식 노드들에 관한 쿼리는 어떻게 처리할까? Euler tour technique 오일러 투어 테크닉(Euler tour technique)은 Tarjan과 Vishkin이 제안한 방법이다. 이 방법을 오일러 투어 테크닉이라고 부르는 이유는 검색 트리에서 이 테크닉을 통해 정점에 numbering 한 후, 각 간선의 역방향 간선을 만들어(자식 → 부모) numbering 한 순서대로 나열하면, 오일러 회로로 나타내지기 때문이..

들어가며.. 다익스트라 알고리즘(Dijkstra's algorithm)을 이용하면 \(O(|E|+|V| \log(|V|))\)에 단일 출발지 최단 경로를 구할 수 있습니다. 만약, 간선의 가중치가 0 혹인 1 뿐이라면 더 빠르게 작동시킬 수 있을까요? 0 - 1 너비 우선 탐색 0 - 1 너비 우선 탐색은 다익스트라 알고리즘과 완전히 같은 아이디어로 작동합니다.(사실 0 - 1 너비 우선 탐색은 다익스트라 알고리즘을 최적화 한 것입니다.) 그저 가중치가 0 혹은 1 밖에 없는지라 priority queue를 사용하지 않을 수 있다는 것이 차별점이라 할 수 있겠습니다. 다익스트라에서 priority queue는 현재 queue에 들어있는 정점 중 시작 점으로 부터 가장 가까운(=현재 구한 최단 경로가 가장..

Introduction 트리를 분할하는 방법으로는 대표적으로 Centroid Decomposition과 Heavy-Light Decomposition이 있다. Centroid Decomposition의 경우, 주로 트리에서 분할정복을 위해 이용되며, Heavy-Light Decomposition은 우리가 다루기 더 쉬운 형태인 선형 배열의 형태로 트리를 바꾸어 문제를 해결하기 위하여 사용한다. 이번 포스팅에서는 Heavy-Light Decomposition을 다룬다. Heavy-Light Decomposition Heavy-Light Decomposition(HLD)는 트리의 정점을 여러 경로의 집합으로 나누는 방법이다. HLD를 수행하기 위해서 일단 임의의 정점의 트리의 루트로 잡는다. 이후, 루트에서..

서론 그래프에서의 동형사상을 찾는 문제는 NP이다. 다만, 트리에서의 동형사상은 다항시간에 판정할 수 있다. 이번 포스팅에서는 두 rooted 트리에서의 동형사상을 찾는 알고리즘인 AHU Algorithm [Aho, Hopcroft and Ullman]과 unrooted tree의 동형사상을 찾는 방법을 다룰 것이다. 1. 동형인지 여부를 판정할 트리가 rooted tree 일 때 - AHU algorithm AHU algorithm에서는 트리를 몇 개의 튜플로 해싱하여 두 트리가 같은지 비교한다. 이때, depth 별로 tuple을 하나씩 형성해주어야 한다. 이 tuple을 이루는 항은 AHU algorithm에서는 각 depth별 vertex의 degree들이다. 또, tuple은 항상 정렬된 상태로..

들어가기에 앞서.. 단순히 빠른 정렬 방법이 아니라, 특정 상황에서 좋은 정렬법에 대해 설명하고자 한다. BOJ의 '수 정렬하기(시리즈)'의 문제들을 통해 여러 정렬의 방법들을 알아보고자 한다. 본론 2750번: 수 정렬하기는 다루지 않도록 하겠다. 먼저, 10989번: 수 정렬하기 3을 보자. 딱 봐도 Counting Sort의 냄새가 난다. 시간 복잡도는 수의 범위의 크기가 T일 때, O(T+N)이다. Counting Sort는 정렬하고자 하는 수를 배열의 index로 생각하고 배열에서 Count 한 뒤 Count 한 횟수만큼 출력하는 것으로 이루어진다. Counting Sort를 모르는 사람은 많지 않을 것으로 생각한다. 이 Counting Sort의 단점은 수의 범위가 클 때 처리하기 어렵다는 것..

동적 계획법(dynamic programming)은 부분 문제의 해를 결합해 문제를 해결한다. 동적 계획법은 부분 문제가 서로 중복될 때 적용할 수 있다. 동적계획법을 이용하면 모든 부분 문제를 한 번만 풀어 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있다. 동정 계획법 알고리즘을 개발할 때는 다음 4단계를 따른다. 최적해의 구조의 특징을 찾는다. 최적해의 값을 재귀적으로 정의한다. 최적해의 값을 일반적으로 bottom-up 방법으로 계산한다. 계산나된 정보들로부터 최적해를 구성한다. 위의 내용이 Introduction to Alogirhtm 에 수록되어 있는 내용이다. 위 내용을 읽고 생각해보면, 동적 계획법은 각 부분에 대한 값을 계산하고 저장해두며, 필요할..

위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하다. 아래와 같은 알고리즘은 하나의 방향 비순환 그래프를 위상 정렬 한다. 위상 정렬(G) 1 각 정점 v에 대해 종료 시간 v.f를 계산하기 위해 DFS(G)를 호출한다. 2 각 정점이 종료될 때마다 연결 리스트의 맨 앞에 삽입한다. 3 return 정점의 연결 리스트 중요한것은 위상 정렬한 순서대로 일을 수행할 때 일을 수행하지 못하는 일이 나오지 않는다는 것이다. 미리 어떠한 행동 A를 해야 B를 할 수 있다면 A를 하고 B를 해야한다는 것이다. 위 방식으로 위상 정렬을 할 때 시간복잡도는..

간단한 설명 병합 정렬은 존 폰 노이만에 의해 고안된 알고리즘이다. 병합 정렬은 분할정복 기법을 이용하며 다음과 같이 작동한다. 분할: 정렬할 n개 원소의 배열을 n/2개 씩 부분 수열 두 개로 분할한다. 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다. 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다. 계속해서 분할을 하다 보면 원소의 수가 하나가 되고 이는 원소가 하나임으로 이미 정렬된 수열이다. 이 하나의 원소로 이루어진 부분수열로 부터 각 부분수열을 병합해가면서 정렬하는 알고리즘이 바로 병합 정렬이다. 알고리즘의 설계 알고리즘의 설계를 위해 트리를 하나 생각해보자. 이 트리의 각 정점에는 두 개의 자식노드가 있고(물론 한개의 자식만 가질수도 있다.) 맨 아래쪽의..

삽입 정렬은 수를 정렬된 상태로 삽입함으로서 정렬하는 방법이다. A라는 배열이 있을 때 {A[1]}을 초기에 정렬된 배열이라고 하고 이 배열의 처음부터 끝까지를 확인하면서 A[i]보다 큰 수가 나오면 그 자리에 A[i]를 삽입한다. 이때 원래 자리에 있던 수를 비롯한 A[i]보다 큰 수들은 한 칸씩 뒤로 밀리게 된다. 또한 이 정렬된 배열을 따로 만들지는 않으며, A의 앞부분에 나타낸다. INSERTION-SORT(A) for j=2 to A.length key=A[j] i=j-1 while i>0 and A[i]>key A[i+1]=A[i] i=i-1 A[i+1]=key 위는 배열 A에 대한 삽입 정렬의 의사코드이다. A.length는 수의 개수이고 key는 현재 정렬해야하는 수를 의미한다. 삽입정렬에..