늦깎이 IT

[최단 경로란?] 최단 경로 (shortest path)는 정점 u와 v를 잇는 경로 중, 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.노드 u에서 v까지의 최단 경로의 값을 δ(u, v)라고 하자. [최단 경로의 유형] 1. Single-Source ( One-to-All )하나의 출발 노드 s로부터 그래프 내의 모든 노드들까지의 최단 경로를 찾는 문제.2. Single-Destination 그래프내의 모든 노드로부터 하나의 목적지 노드 d까지의 최단 경로를 찾는 문제.만약, 그래프가 무방향 그래프라면 Single-Source 문제와 Single-Destination 문제는 똑같은 문제가 된다.그러나, 그래프가 방향 그래프라면 모든 간선들의 방향을 거꾸로 뒤집는다면, Single-Source..

이 포스팅은 이전의 [유니온 파인드] 내용을 보완하여 다시 작성된 포스팅입니다.이 포스팅을 작성하며 Geek과 권오흠 교수님의 강의, [이곳]을 참고하였습니다. [ 디스조인트 셋(Disjoint Set)이란? ] 디스조인트 셋이란 "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.즉, 교집합이 없는 서로 다른 데이터들로 이루어진 자료구조라고 할 수 있다. S = { 1, 2, 3, 4 }라는 전체 집합이 있다고 가정한다. 이때 S의 부분 집합 A = { 1, 2 }와 B = { 3, 4 }는 서로Disjoint Set이라고 한다.S의 부분 집합 A와 B의 교집합은 공집합이기 때문이다.반대로, 부분 집합 C = { 1, 2, 3 }과 D = { 1, 2 }는 서로 ..

[신장트리란?] 신장트리 (Spanning Tree)는 그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 말한다.N개의 정점을 가지는 그래프의 최소 간선의 수는 (N - 1)개 이고, 모든 정점이 (N - 1)개의 간선으로 연결되어 있으면 필연적으로 트리의 형태로 이루어질 수 밖에 없다. 4개의 노드로 이루어진 아래와 같은 그래프를 보면, 신장트리를 구성하는 방법은 유일하지 않음을 알 수 있다. [최소 비용 신장트리란?] 최소 비용 신장트리 (Minimum Spanning Tree)는 그래프에서 가능한 신장트리들 중에서 가중치의 합이 최소인 신장트리를 말한다. 위의 그림에서는 간선의 가중치가 없기때문에 최소신장트리(MST)를 찾을 수 없다. 그러나, 아래의 그림과 같이..

이 포스팅은 이전에 정리했던 "힙 정렬"에 대해서 핵심적인 부분만을 다시 작성한 포스팅입니다. [이전 포스팅]2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙2019/02/16 - [알고리즘 이론] - [정렬] 힙 정렬 :: 늦깎이 IT [힙이란?] 힙은 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 [ 완전이진트리 ]를 기본으로 한 자료구조이다. 1. 최대 힙 (Max Heap)부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 "최대 힙"이라고 부른다. 2. 최소 힙(Min Heap)부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 "최소 힙"이라고 부른다. 3. 힙의 형태힙은 아래 그림처럼 한 노드가 최대 두 개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모..

[퀵 정렬] 퀵 정렬은 앞서 알아봤던 합병 정렬과 마찬가지로 '분할 정복'에 근거하여 만들어진 정렬 방법이다.실제로 퀵 정렬 역시 정렬대상을 줄여나가는 과정을 포함한다. 그러나, 정렬 대상을 반씩 분할했던 합병정렬과는 달리 퀵 정렬은 데이터를 반드시 균등한 크기로 분할하지 않는다. 우선, 퀵 정렬은 '피벗(Pivot)'이라고 불리는 기준점으로 정렬을 수행한다. 정렬해야 하는 데이터들 중, 임의의 데이터를 '피벗'으로 지정한 후, 다른 데이터들과의 비교를 통해 [피벗보다 작은 데이터] / [피벗보다 큰 데이터]로 나눈다. 퀵 정렬이 균등한 크기로 분할하지 않는 이유도 여기에 있다. '피벗'보다 [작은 값]의 갯수와 [큰 값]의 갯수가 균일하지 않을 수 있기 때문이다. [그림]에서는 마지막 값을 피벗으로, ..

[합병정렬] 합병정렬은 분할정복이라는 알고리즘에 근거하여 만들어진 정렬 방법이다.분할정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 단순한 문제로 '분할(Divide)'하여 '정복(Conquer)'하는 방법이다. 1. 분할 (Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다.2. 정복 (Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다.3. 결합 (Combine) : 분할해서 해결한 결과를 결합하여 큰 문제를 해결한다. 우리가 8개의 데이터를 정렬한다고 가정해보자.8개의 데이터를 정렬하는 것 보다는 4개의 데이터를 정렬하는 것이 더 쉽고, 또 4개보다는 2개의 데이터를, 2개보다는 1개의 데이터를 정렬하는 것이 더 쉽다는 것이다. 위의 아이디어를 근간으로, 합병정렬은 데이터..

1. 선택정렬선택정렬은 현재 위치에 들어갈 값을 찾아서 정렬하는 방법이다. 1) 정렬되지 않은 인덱스의 맨 앞부터, 가장 작은 값을 찾는다.2) 가장 작은 값을 찾았다면, 그 값을 현재 위치(인덱스)의 원소와 위치를 바꿔준다.3) 반복한다. [의사 코드]1234select-sort(A[], N) for first ← 1 to N-1 find smallest A[K] swap(A[first], A[K])cs 2)번 라인의 반복문은 N-1번 반복한다.3)번 라인의 가장 작은 값을 찾기 위한 비교 횟수는 N-1, N-2, ....., 2, 1번 수행한다.4)번 라인의 교환은 상수시간만큼 걸린다. 즉, 시간복잡도는 T(N) = (N-1) + (N-2) + ..... + 2 + 1 = O(N^2)이다. [불안정한..

이 포스팅은 [이곳] 에서 수정 및 보완되었습니다. 꼭! 참고하시기 바랍니다. 이 포스팅에서는 유니온 파인드의 연산 과정을 [그림] 위주로 이해하기만 하면 될 것 같습니다. 오늘은 '유니온 파인드 (Union-Find)' 알고리즘을 포스팅합니다. 유니온 파인드는 대표적인 그래프 알고리즘으로써 서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다.여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는알고리즘이다. 아래와 같은 노드들이 있다고 가정한다. 위 그림에서 노드 1, 2, 5와 3, 4, 6은 각각의 그룹으로 나뉘어있다. 위의 상태에서 5번 노드가 어느 그룹에 속해있는지 확인하는 것을 Find-Set이라고 한다. 임의의 노드들이 같은 그룹에 ..