늦깎이 IT

이 포스팅은 이전의 [유니온 파인드] 내용을 보완하여 다시 작성된 포스팅입니다.이 포스팅을 작성하며 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 [우선순위 큐] 먼저 입력된 데이터가 먼저 처리되는 일반적인 FIFO큐와는 달리 우선순위 큐는 입력의 순서에 상관없이 우선순위가 높은 데이터를 먼저 처리하는 자료구조이다. 우선순위 큐는 힙과 밀접한 관계가 있으므로, 힙에 대한 내용은 이전 포스팅을 참고하기 바란다.2019/04/16 - [알고리즘 이론] - [정렬] 힙 정렬 (수정) :: 늦깎이 IT [데이터 삽입 하기] 데이터가 힙에 추가될 때에는 힙이 "완전 이진트리"라는 점을 명심해야 한다. "완전..

이 포스팅은 이전에 정리했던 "힙 정렬"에 대해서 핵심적인 부분만을 다시 작성한 포스팅입니다. [이전 포스팅]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)이다. [불안정한..

[백준 16985번] URL Maaaaaaaaaze URL [전체 소스코드 GitHub에서 확인하기] 1. 두 가지경우에 대한 완전탐색을 실행해야 한다. 2. 우선, 각각의 판의 순서(?)를 정하는 모든 경우의 수를 구해야한다.A,B,C,D,E 라는 5 x 5 크기의 판이 5개 있을 때, 이 판들을 바닥에서부터 쌓는 순서를 정해야한다. 3. 각각의 판을 쌓아올리는 경우에 대해서 1층부터 5층까지 자리잡은 판들을 각각 0회~3회씩 돌린 후 최단거리를 찾는다. [시계방향으로 돌리는 메소드] - prev[][][] 3차원 배열이 있을 때, prev[target][][]의 값들을 시계방향으로 한번 회전시키는 메소드이다. 123456789101112public static void rotate(int[][][] ..