위상 정렬

위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 하는 것이다. 사용 예시 선수과목을 고려한 학습 순서 설정 A 과목을 수행하고 B 과목을 수강하는 것을 권장할 때, A, B 를 각각 노드로 표현하고 A -> B 로 가는 방향을 갖는 간선을 그린다. 즉, 그래프 상에서 선, 후 관계가 존재하면 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다. 진입 차수(Indegree) 진입 차수(Indegree)란 특정한 노드로 들어오는 간선의 개수를 의미한다. A -> B, B -> C, D -> B 의 ..

신장 트리와 크루스칼 알고리즘

신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm) 신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)에 대해서 배워보자. 신장 트리 신장 트리(Spanning Tree)란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 크루스칼 알고리즘 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree, MST)를 구하기 위해서 사용되는 알고리즘 이다. 크루스칼 알고리즘은 그리디(Greedy) 알고리즘으로 분류된다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼 알고리즘을 구현할 때에는 Union-Find 알고리즘을 사용하므로,..

서로소 집합

서로소 집합(Disjoint Sets) 서로소 집합(Disjoint Sets)은 공통 원소가 없는 두 집합을 의미한다. 예를 들면 {1, 2}와 {3, 4} 가 서로소 집합에 해당된다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union 과 find 이 2개의 연산으로 조작할 수 있다. union(합집합) 연산 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find(찾기) 연산 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합집합과 찾기 연산으로 이루어져 있다. 따라서 union-find 자료구조라고도 한다. 서로소 집합 자료구조 서로소 집합 자료구조를 구현할 때는 트..

플로이드 워셜 알고리즘

플로이드 워셜(Floyd Warshall) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용할 수 있는 경우이다. 다익스트라 알고리즘에서는 한 지점에서 다른 모든 지점까지의 최단거리인 반면, 플로이드 워셜은 모든 지점 to 모드 지점인 것이다. 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다. 노드의 개수가 N 개일 때 알고리즘상으로 N 번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 총 시간 복잡도는 O(N^3)이다. 플로이드 워셜 알고리즘을 사용해야 하는지에 대한 판단 기준 가중치 방향 그래프가 주어진다. A -> K ->..

최단 경로와 다익스트라 알고리즘

최단 경로(Shortest Path) 최단 경로(Shortest Path)는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 길 찾기 문제라고도 불린다. 아래 세 개의 알고리즘이 주로 사용된다. 다익스트라 알고리즘(Dijkstra Algorithm) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 벨만 포드 알고리즘(Bellman-Ford's algorithm) 최단 경로 문제의 특징은 다음과 같다. 도로, 길찾기 문제 도로(길)와 가중치(값, 시간 등)가 주어지는 경우 Ex. A 위치에서 K 를 거쳐 X 로 도착하려고하는 경우에는 플로이드 워셜 알고리즘 사용. (즉, 어디를 거쳐간다고하면 플로이드 워셜 알고리즘일 가능성이 높음) 최단 경로의 문제는 대부분 가중치 방향 그래프..

다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming) 동적 계획법을 듣기전에 재귀와 메모이제이션에 대한 이해가 먼저 필요하다. 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이 있는데 대표적인 방법에 동적 계획법(Dynamic Programming)이 있다. 다이나믹 프로그래밍 방식은 TopDown and BottomUp 두 가지가 있으며 메모이제이션 기법을 자주 사용한다. Memoization : 메모리를 더 많이 사용하여 시간 복잡도를 줄이는 방법 다이나믹 프로그래밍으로 해결할 수있는 대표적인 예시가 피보나치 수열이다. 재귀에서 배웠듯이 재귀를 사용하려면 점화식을 작성해보는 것이 좋다. 피보나치 수열에 대한 점화식은 다음과 같다. $$ n > 2 ? f(n) = f(n-2)..

결정 알고리즘과 파라메트릭 서치

결정 알고리즘(Decision Algorithm)과 파라메트릭 서치(Parametric Search) 결정 알고리즘과 파라메트릭서치를 배우기 전에 이진 탐색(Binary Search, 이분 검색)에 대한 이해가 선행되어야 한다. 따라서, 이진 탐색에 대해서 먼저 배워보도록 하겠다. 순차 탐색(Sequential Search) 순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용하며, 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 결과를 찾을 수 있다. 구현 /** * @param n 입력 데이터 개수 * @param target 찾고자 하는 문자열 * @param arr 배열 */..

재귀 함수(Recursion Function)

재귀 함수(Recursion Function) 재귀 함수는 내부적으로 스택(Stack)을 이용한다. JVM(Java Virtual Machine) 의 메모리인 Runtime Data Areas 영역에 스택 영역이 존재한다. 자바에서 함수를 호출하게 되면 함수에 대한 정보들이 스택 공간에 적재되기 때문에, 재귀 함수는 스택 자료구조를 이용한다고 볼 수 있다. 재귀 함수는 자기 자신을 다시 호출하는 함수를 의미 하는데, 재귀 함수를 제대로 이해하기 위해선 다음과 같은 내용에 대한 이해가 되어있어야 한다. JVM 메모리 스택 영역 JVM 메모리 힙 영역 스택 자료 구조 Call Frame(Call Stack) 먼저, 이 부분에 대한 이해를 다루기 전에 팩토리얼(Factorial) 구현을 예시로 들어서 재귀 함..