![]()
세그먼트 트리(Segment Tree)는 구간에 대한 정보를 빠르게 구해낼 수 있으며 완전 이진트리 형식의 구조를 가지는 자료구조입니다.구간의 최솟값을 구하는 세그먼트 트리는 먼저 구하고자 하는 배열을 완전 이진트리의 최하단에 위치시킨 후, 모든 부모 노드가 자식 노드들 중 작은 값을 가지게 하며 트리를 완성시킵니다.이를 통해 트리의 어떤 노드 X는 X의 하위 노드 중 최솟값을 가지게 됨은 자명합니다.예를 들어 아래 배열을 사용한 세그먼트 트리의 구현에서 Tree[1]은 모든 원소의 최솟값이 오게 되고, Tree[2]는 하위 노드인 8~11번지의 최솟값이 들어있게 됩니다.이들 중 원하는 범위 [L, R]에 필요한 노드를 골라서 구성할 것입니다.위에서 완성된 세그먼트 트리에서 배열 D에 대한 범위 [L, ..
![]()
최소 신장트리란최소 신장 트리(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프의 모든 노드를 포함하면서 사이클이 없고 가중치의 합이 최소가 되는 트리입니다. 연결그래프가 주어질 때, MST를 구하는 알고리즘은 대표적으로 크루스칼, 프림 2가지가 있습니다.두 알고리즘은 비슷한 시간 복잡도를 가지지만 나름의 장, 단점이 있으므로 모두 알아봅시다. 1. 프림 알고리즘프림 알고리즘은 일단 시작점을 아무 정점을 선택하고, 이는 MST를 구성하는 첫 원소가 됩니다.그리고 현재까지 구성된 MST의 원소(시작점)에 연결된 간선 중 가장 가중치가 작은 값을 가지는 간선을 골라 이어준 후 MST의 원소로 추가합니다.그리고 MST가 완벽하게 완성될 때까지 현재까지 구성된 MST의 원소들에 연결된 간..
![]()
목차동적 계획법이란Top-Down와 Bottom-UpCoin Change ProblemKnapsack Longest Common Subsequence Longest Increasing Subsequence Edit Distance Matrix Chain Multiplication 1. 동적계획법이란 흔히 DP라 불리는 동적 계획법이란, 복잡한 문제를 여러 개의 작은 부분 문제(sub-problem)로 나누어 해결하는 문제 해결 기법입니다. 동적 계획법의 특징 중 하나는 이미 계산된 부분 문제가 다시 발생하면 새롭게 계산하지 않고 이전의 계산값을 참조하여 이용하는 것입니다. 이 방법은 부분 문제를 다시 해결하는 데 필요한 시간을 절약할 수 있지만, 이전 계산값을 저장해 둘 공간이 필요하므로 시간과 메..
![]()
위상 정렬이란 유향 그래프에서 정해진 순서를 위배하지 않도록 나열하는 것입니다.예를 들면 전략 게임에서의 빌드 오더나 선수강과목을 예로 들 수 있습니다.전략 게임의 빌드 오더에서 A를 짓지 않으면 B를 지을 수 없고, B를 짓지 않으면 C를 지을 수 없다와 같은 규칙이 있을 수 있고, 선수강과목은 자료구조 과목을 듣지 않으면 알고리즘 과목을 수강할 수 없다는 규칙이 있을 수 있습니다.이러한 순서에 따라서 나열하는 것이 바로 위상 정렬입니다.만약에 이런 규칙에 순환이 생긴다면 순환이 생긴 그 무엇도 나열할 수 없기 때문에 DAG(directed acylic graph)에서만 위상 정렬이 가능합니다. 구현 방법에 대해서 설명을 하자면, 먼저 그래프를 구성할 때 간선의 의미는 A->B 라면, A를 방문해야 ..
![]()
퀵 정렬(Quick Sort)은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고, 해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보내고 다시 왼쪽 파티션 구간에 한하여 pivot을 잡고 파티션을 나누고 오른쪽 파티션 구간에서도 pivot을 잡고 파티션을 나누는 과정을 반복하여 정렬시키는 정렬 알고리즘입니다.이 알고리즘의 핵심은 pivot을 잘 설정하여 왼쪽 파티션과 오른쪽 파티션을 적절하게 나누는 것입니다.왜냐하면 pivot을 해당 구간의 중앙값으로 잘 설정하면 합병 정렬과 같은 시간 복잡도 O(nlogn)에 수행할 수 있지만, 만약 매 케이스마다 구간의 가장 큰 값이나 가장 작은 값으로 나눠버리면 O(n^2)의 수행 시간을 갖게 됩니다. (1..
![]()
분할정복(Divide and Conquer)은 말 그대로 문제를 분할한 다음, 분할한 문제들 (sub-problems)을 해결하고, 그 결과를 합쳐서 원래의 문제를 해결하는 것입니다.분할정복의 대표적인 예로는 합병 정렬, 고속 푸리에 변환 등이 있습니다.합병정렬을 예로 설명해보겠습니다.영역을 나눈 후, 나누어진 영역을 투 포인터(Two Pointer) 알고리즘으로 합병하는 방식으로 동작합니다.투 포인터 알고리즘을 사용하려면 나눠진 영역이 정렬이 되어있어야 하기 때문에 먼저 영역을 작게 나눈 후 합치는 재귀적인 방법이 사용됩니다.이진탐색과 유사하게 전체 영역을 [L, R], M = (L + R) / 2이라고 할 때 [L, M], [M+1, R] 두 개의 영역으로 분할하겠습니다. 왼쪽 부분을 다시 분할해 보..
![]()
너비 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점들을 발견하면 그 간선을 통해 방문하지 않은 정점들을 자료구조 큐에 넣습니다. 그리고 큐의 front 정점을 방문하고 pop합니다.또 해당 정점에서 인접한 간선을 검사해 방문하지 않은 정점들을 큐에 넣고 방문하기는 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 종료합니다. 이러한 과정을 반복하여 큐에 더 이상 정점이 존재하지 않을 때까지 실행하여 그래프의 모든 정점을 방문하는 알고리즘이 BFS 알고리즘입니다위의 그림과 같은 유향 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정..
![]()
해싱은 임의의 길이의 데이터(키, Key)를 고정된 길이의 데이터(해시값, Hash value)로 변환해 작은 크기의 해시 테이블로 대응(Mapping)시켜 식별하는 하나의 기법입니다. 해시 테이블은 M개의 버킷으로 이루어져 있으며, 이 글에서 다루는 해시값은 해당 키가 저장될 버킷의 번호(해시 테이블의 인덱스)를 나타냅니다. 키에서 해시값을 추출하는 일련의 과정을 해시 함수(Hash function)라고 합니다. 해시 함수는 같은 키에 대해서는 동일한 해시값을, 다른 키에 대해서는 다른 해시값을 추출해야 합니다. 하지만 일반적으로 해싱에서 해시값의 범위(M)는 키의 범위보다 작기 때문에 어떤 이상적인 해시 함수라도 비둘기집의 원리에 의해 서로 다른 두 키가 같은 해시값을 가질 수 있습니다. 이런 경우..
![]()
힙(heap) 은 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 트리형 자료구조입니다.힙은 완전이진트리 형식을 따르며 모든 부모 노드의 값이 자식 노드들의 값과 일정한 대소 관계를 가지게 되는 규칙을 가지고 있습니다.또한 자식노드 사이의 상관관계는 없으므로 유의하여야 합니다.부모 노드의 값이 자식 노드의 값보다 크다면 최대 힙(Max Heap), 부모 노드의 값이 자식 노드의 값보다 작다면 최소 힙(Min Heap) 으로 부릅니다.힙의 규칙에 따라 트리의 가장 상단에는 최댓값 또는 최솟값이 있는 것이 자명하기 때문에, O(1) 만에 최댓값과 최솟값을 찾을 수 있습니다.힙의 삽입은 트리의 가장 마지막 부분에 데이터를 삽입한 후, 부모 노드와 삽입 부분 노드의 대소 관계를 확인하여 힙의 규칙에 맞도록 부모 노..
![]()
트리는 자식과 부모의 관계로 이루어진 계층적인 구조입니다. 필요에 따라 다양한 종류로 나뉘게 되는데 이번에는 제일 간단한 트리인 이진 트리에 대해서 설명하려고 합니다. 먼저 이진 트리에서 사용하는 용어들을 정리해보면 다음과 같습니다. Root : 트리에서 가장 최상위에 존재하는 노드Child : 어떠한 노드의 자식 노드Parent : 어떠한 노드의 부모 노드Siblings : 같은 부모를 갖는 형제 노드Leaf / Terminal : 자식 노드를 갖지 않는 노드Branch / Internal : 자식 노드를 적어도 1개 이상 갖는 노드Degree : 노드가 가지고 있는 자식 노드의 개수Height : 해당 노드부터 Leaf 노드까지의 가장 긴 거리Level : 트리 각 층의 단계 (Root 노드의 경우 ..
![]()
스택은 선형 구조이며, 마지막으로 삽입된 값이 가장 먼저 나오는 LIFO(Last in First Out)으로 되어 있습니다. 이 때 삽입하는 과정을 push라고 하며 값을 빼내는 과정을 pop이라고 합니다. 예를 들면 a, b, c 순서로 push하고 스택에 있는 값들을 모두 pop하면 c, b, a 순서로 나오게 되는 것입니다. 또한 스택에는 size, top, empty라는 함수가 있으며 size는 스택에 들어있는 값들의 수를 반환하는 함수이고, top은 마지막으로 삽입된 값을 반환하는 함수, empty는 스택이 비어 있는지 여부를 반환하는 함수입니다.아래의 두 그림은 stack의 push, pop 과정을 보여주는 그림입니다. 그리고 이러한 스택을 만드는 방법에는 2가지 방법이 있습니다. 하나는 ..
![]()
큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다.예를 들면 a, b, c 순서로 enqueue하고 큐에 있는 값들을 모두 dequeue하면 a, b, c 순서로 나오게 됩니다.또한 큐에는 size, front, empty라는 함수가 있으며 size는 큐에 들어있는 값들의 수를 반환하는 함수이고, front은 큐에서 가장 먼저 삽입된 값을 반환하는 함수, empty는 큐가 비어 있는지 여부를 반환하는 함수입니다. 그리고 이러한 큐를 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다. ..
![]()
연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다.연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인 헤드(Head)로 부터 노드에 다음 노드를 가리키는 포인터를 사용해 리스트를 순회할 수 있게 됩니다.위와 같은 연결리스트를 Singly Linked List라고 합니다.Singly Linked List의 각 노드에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 되고, 환형 큐(Circular Queue)와 같이 연결리스트의 마지막 노드인 테일(Tail)과 헤드를 이으면 Circular Linked List가 됩니다. 각 노드..
![]()
그래프란 어떤 상태 혹은 객체 간의 관계를 나타내는 자료구조입니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성됩니다.정점이란 어떠한 상태 혹은 객체를 나타냅니다. 간선은 그러한 정점 간의 관계, 그중에서도 연결성을 표현하는 요소입니다. 아래 그림은 그래프의 개념이 퍼지기 시작한 '쾨니히스베르크의 다리 건너기 문제'의 쾨니히스베르크의 다리를 도식화한 두 그림입니다.A, B, C, D로 나눠진 4개의 구역과 각 구역을 잇는 a, b, c, d, e, f, g 7개의 다리가 있습니다. 왼쪽이 일반적으로 사용되는 그림이며, 이를 그래프 형태로 나타낸 것이 오른쪽의 그림입니다.여기서 원으로 표현된 A, B, C, D가 정점이며 이 정점들을 연결하는 실선 a, b, c, d, e, f, g가 두 지역을..
![]()
깊이 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동하는 것입니다.이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색합니다. 이러한 과정을 반복하여 그래프의 모든 정점을 방문하는 알고리즘이 DFS 알고리즘입니다. 이해를 돕기 위해 움직이는 그림으로 그래프를 설명하도록 하겠습니다. 위의 그림과 같은 유향 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정을 하겠습니다. 이 때, 정점 1에서 깊..
