heap sort는 힙의 특성을 이용하여 정렬하는 알고리즘이다. 여기서 힙은 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 이러한 두 값의 대소 관계가 일정하면 된다. 따라서 힙에서 어떤 부모와 자식 관계를 주목할 때, 부모의 값이 자식의 값보다 항상 큰 관계가 성립한다. 따라서 힙의 가장 위쪽에 위치한 루트가 가장 큰 값이 된다. 다만, 힙에서 부모와 자식 관계는 일정하지만, 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소 관계가 정해져 있지 않으므로, 부분 순서 트리(partial ordered tree)라고도 한다. 그럼 이번에는 힙의 원소를 배열에 어떻게 저장할 것인지를 알아보자. 먼..
개요 효율적인 알고리즘의 설계와 분석을 위해서는 3가지 중요한 기법들을 익혀야 한다. 이 것들에는 크기 동적 프로그래밍, 그리디 알고리즘, 분할상환 분석이 있는데, 이 기법들은 좀 더 복잡하지만, 컴퓨터로 해결할 수 있는 많은 문제들을 효과적으로 공력할 수 있게 도와준다. 동적 프로그래밍은 일반적으로 최적해(optimal solution)에 도달하기 위해 일련의 선택이 이루어지는 최적화 문제에 적용된다. 그리고 각각의 선택을 하는 과정에서 종종 같은 형태의 부분 문제가 생긴다. 동적 프로그래밍은 어떤 부분 문제가 둘 이상의 부분적인 선택 집합에서 발생하는 경우에 효과적이다. 또한 이 기법의 중요한 특징은 부분 문제의 해가 다시 나타나는 경우를 대비해 그 해를 저장해두는 것이다. 그리디 알고리즘도 동적 프..
DP란 다이나믹 프로그래밍이란 복잡한 하나의 문제를 여러 하위 문제들로 나누고, 각각의 결과를 저장한 후에 해당 문제에 대한 중복 컴퓨팅을 제거하여 효율성을 제거하는 문제 해결 방법이다. 즉, 같은 input에 대한 반복되는 호출을 하는 솔루션을 만났을 때, 우리는 그것을 Dynamic Programming으로 최적화 시킬 수 있다. 그리고 DP를 구현하는 방법에는 2가지가 있는데, 하나는 Tabulation이고, 하나는 Memoization이다. Tabluation ( bottom up ) tabulation을 사전에서 찾아보면, 표, 목록 등의 결과를 확인할 수 있다. 이러한 tabulation 방식은 순서대로 차근차근 값을 구하고 구한 값을 토대로 다음 값을 빠르게 구해나가는 bottom up 형태..
Union-Find의 개념은 다음과 같다. A와 B가 친구 관계에 있고, 내가 A와 친구 관계이면 자동으로 나와 B는 친구 관계가 된다. 이 개념을 이용해서 내가 A라는 사람과 친구 관계를 맺었는데, 그럼 내가 F라는 사람과 친구 관계가 될 수 있을지는 어떻게 알 수 있을까? 답은 친구 관계를 그래프로 나타낸 후에 나를 시작으로 그래프 탐색(DFS, BFS)를 통해 목표 지점까지 도달할 수 있는지 확인하면 간단할 것이다. 하지만 친구 관계는 언제나 새롭게 생겨날 수 있다. 그럼 친구 관계가 새로 생겼다고 할 때, F와 친구 관계가 될 수 있는지 알기위해서 다시 그래프 탐색을 진행해야 한다. 따라서 이런 방식을 사용하기 때문에 사용하는 사용자의 수가 엄청 많다면 새로운 친구 관계가 생겨날 때마다 그래프 탐..
그래프에서 Spanning Tree란 그래프의 모든 정점을 잇지만 사이클은 없는 부분 그래프를 의미한다. 즉, 형태와 관계없이 모든 정점을 사이클없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종으로 V개의 모든 정점을 연결하는 간선의 수는 V-1개가 된다. 이때 최소 Spanning Tree(MST)는 이러한 스패닝 트리 중에서 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 즉, 간선의 가중치가 있을때 최소 스패닝 트리를 만들 수 있다. 그리고 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruscal과 Prim 알고리즘이 존재한다. 그럼 먼저 Kruscal 알고리즘에 대해서 알아보자. Kruscal Algorithm 크루스칼 알고리즘은 간선들을 ..
최단 거리 알고리즘이란 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다. 일반적으로는 네비게이션과 같은 길찾기에 적용된다. 이러한 최단 거리 알고리즘의 종류에는 크게 3가지가 있다. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그래프 상의 특정 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 다르게 표현하면 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘 중 하나이다. 그래서 다익스트라는 그리디와 동적 계획법이 합쳐진 형태이다. 왜냐하면, 현재 위치한 노드에서 최선의 경로를 반복적으로 찾으면서도 계산해둔 경로를 활용해 중복된 하위 문제를 풀기 때문이다. 또한 다익스트라는 만약 그래프에 음의 가중치가 있다면 사용할 수 없다. 그 이유는 그..
다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어에서 많이 사용되며, 개념적으로는 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함할 수 없다. 물론 현실 세계에서는 음의 간선이 존재하지 않기때문에 다익스트라는 현실 세계에서 사용하기 매우 적합한 알고리즘인 것이다. 여기서 다익스트라 알고리즘이 왜 DP인지 궁금할 것이다. 그 이유는 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해있기 때문이다. 즉, 다익스트라는 하나의 최단 거리를 구할 때, 그 이전까지의 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 그리고 다익스트라 알고리즘은 정렬 후에 ..
개념 위상 정렬(Topology Sort)는 순서가 정해져있는 작업을 차례대로 수행해야할 때 그 순서를 결정해주기 위해서 사용하는 알고리즘이다. 쉽게 말하면 그래프의 흐름이 있고, 다양한 조건이 얽혀있을 때 정확히 1열로 그래프의 노드를 나열할 수 있도록 하는 알고리즘이 위상 정렬인 것이다. 따라서 다음과 같이 모든 조건을 만족하도록 일직선의 순서를 하나 만들어낼 수 있는 것이다. 대학생 되기 -> 학과 사이트 가입하기 -> 4학년 되기 -> 정보처리기사 합격하기 -> 자격 서류 제출하기 -> 졸업시험 신청하기 -> 졸업하기 이렇게 정렬을 하면 순서대로 작업을 수행했을 때 성공적으로 '졸업하기'까지 갈 수 있다. 또한 위 말고도 다른 답도 존재하게 된다. 그래서 위상 정렬은 여러 개의 답이 존재할 수 있..
tree는 부모-자식 관계를 가지는 구조로 계층이 있고, 그룹이 있다. 이 것을 가능하게 한 것이 노드가 하나 이상의 자식 노드를 가지기 때문이다. 트리의 노드 중에는 부모를 아는 경우도 있고, 자식만 아는 경우도 있고, 데이터가 잘 정렬된 것도 있고, 섞여있는 것도 있다. 그리고 트리중에서 자식 노드가 최대 2개 까지만 붙는 경우를 이진 트리라고 한다. 그리고 그 이상의 3개씩 자식이 붙는 경우를 ternary tree라고 한다. 그럼 이 중에서 가장 중요한 이진 트리를 알아보자. Binary Tree는 이진 트리다. 즉, 자식 노드가 최대 2개인 트리이다. 여기서 Binary Search Tree는 왼쪽 자식에는 현재 루트 값보다 작은 값이 들어가고, 오른쪽 자식에는 현재 루트 값보다 큰 값이 들어가..
그래프란? 그래프는 다음과 같이 연결되어있는 원소간의 관계를 표현한 자료구조이다. 이 그래프라는 것은 연결할 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. 즉, 그래프 G를 G(V,E)로 정의하고, 여기서 V는 정점의 집합, E는 간선들의 집합을 의미한다. 그래프의 종류에는 그래프에는 크게 무방향 그래프(undirected graph)와 방향 그래프(directed graph)가 있는데, 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 V1, V2를 표현시에 (V1, V2)처럼 표현할 수 있고, 이는 (V2, V1)과 같은 간선을 나타낸다. 방향 그래프는 간선에 방향이 있는 그래프이다. 정점 V1, V2를 연결하는 간선을 로 표현하는데..
