전체 글
-
그리디(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은 특..