분류 전체보기
-
그리디(Greedy) 알고리즘이란?Computer Science/Algorithm 2020. 1. 29. 17:20
1. 탐욕 알고리즘 이란? Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 그리디 알고리즘은 항상 최적의 결과를 도출해내는 것은 아니지만 어느정도 최적의 해에 근접하게 구할 수 있다는 장점이 있다. 2. 탐욕 알고리즘 예 문제1: 동전 문제 지불해야 하는 값이 1260원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식이다. 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 가장 큰 동전부터 최대한 지불해야 한다..
-
동적 계획법 (Dynamic Programming)이란?Computer Science/Algorithm 2020. 1. 28. 23:21
1. 정의 동적계획법 (DP 라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 Memoization 기법을 사용함 Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 예: 피보나치 수열 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 일반적으로 재귀함수로 구현 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음 예: 병합 정렬, 퀵 정렬 등 동적 계획법의 핵심은 하나의..
-
Dijkstra의 최단 경로 알고리즘이란?Computer Science/Algorithm 2020. 1. 28. 18:00
최단 경로 문제 종류 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 예를 들면 A, B, C, D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면, A 외 모든 노드인 B, C, D 각 노드와 A 간에 (즉, A - B, A - C, A - D) 각각 가장 짧은 경로를 찾는 문제를 의미함 2. 최단 경로 알고..
-
Prim 알고리즘 이란?Computer Science/Algorithm 2020. 1. 27. 22:25
1. 프림 알고리즘 (Prim's algorithm) 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함 Prim's algorithm은 특..
-
Union-Find(합집합 찾기)란?Computer Science/Algorithm 2020. 1. 23. 22:12
Union-Find 란? union-find 연산은 Kruskal의 알고리즘에서만 사용되는 것은 아니고 일반적으로 널리 사용된다. union(x, y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다. find(x)연산은 원소 x가 속해있는 집합을 반환한다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 위와 같이 여러 개의 노드가 연결되지 않은 채로 있다고 가정하자. 여기서 union(1, 4)와 union(5, 2)를 하면 아래와 같은 집합으로 변환된다. {1, 4}, {5, 2}, {3}, {6}, {7}, {8} 위와 같이 합쳐지는 것이다. 더 이해가 필요하기 때문에 구체..
-
Kruskal 알고리즘이란?Computer Science/Algorithm 2020. 1. 23. 22:11
Kruskal 알고리즘 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에서 있어서 중요한 기법 중의 하나이다. 탐욕적인 방법이란 선택할 때마다 그 순간 가장 좋았다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법이다. 탐욕적인 알고리즘에서 순간의 선택은 그 당시에는 최적이다. 하지만 최적이라고 생각했던 지역적인 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 반드시 지역적으로 최적이라는 보장은 없다. 하지만 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여, 각 단계..
-
최소 비용 신장트리(MST, Minimum Spanning Tree)란?Computer Science/Algorithm 2020. 1. 23. 19:41
신장트리 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 또한 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며 (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 된..
-
[Java] Generic 개념 및 정리Language/Java 2020. 1. 22. 17:21
Generic 정의 일반적인 코드를 작성하고, 이 코드를 다양한 타입의 객체에 대하여 재사용하는 프로그래밍 기법이다. 타입을 파라미터화해서 컴파일시 구체적인 타입이 결정되도록 하는 것이다. 클래스 내부에서 사용할 데이터 타입을 외부에서 지정하는 기법이다. Generic은 컬렉션, 람다식, 스트림등에서 널리 사용된다. 1 2 3 4 5 6 7 8 9 public class Person { public T info; public static void main(String[] args) { Person p1 = new Person(); Person p2 = new Person(); } } Generic 타입이란? 타입을 파라미터로 가지는 클래스와 인터페이스를 말한다. 선언시 클래스 또는 인터페이스 이름 뒤에 ..