본문 바로가기

알고리즘/알고리즘 이론

 (24)
탐욕 알고리즘(greedy algorithm) Goal 탐욕 알고리즘과 특징에 대해 설명할 수 있다. 탐욕 알고리즘으로 최적해를 구할 수 있는 경우에 대해 설명할 수 있다. 탐욕 알고리즘(greedy algorithm) 현재 순간 최적(local optimal)이라고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법 탐욕법(greedy method)이라고도 한다. 특징 순간 최적 선택한 결과가 전체 문제의 최적이라는 보장이 없다. 현재의 선택이 앞으로 남은 선택에 어떤 영향을 끼칠지는 고려하지 않는다. 다음 그림은 탐욕 알고리즘이 항상 최적을 보장하지 않음을 나타낸다. 그렇다면, 항상 최적의 결과라는 것을 보장하지 못하는데 왜 탐욕 알고리즘을 사용하는가? 그 이유는 다음과 같다. 빠르다 : 탐욕 알고리즘을 사용해도 항상 최적해를 구할 수 있는..
동적 계획법(Dynamic Programming) Goal 동적 계획법에 대해 설명할 수 있다. 동적 계획법(Dynamic Programming) 복잡한 문제를 여러 개의 작은 문제로 나누어 푸는 방법을 말한다. 분할 정복과의 차이점 동적 계획법과 분할 정복의 가장 큰 차이점은 계산 결과의 재활용이다. (부분 문제를 각각 독립적으로 나눠지지 않음) 동적 계획법의 경우 두 번 이상 계산되는 중복되는 부분 문제(overlapping subproblems)의 계산 결과를 캐시에 저장함(재활용)으로써 여러번 계산되는 것을 막아 속도 향상을 꾀할 수 있다. 이때, 한번 계산된 결과같은 캐시에 저장하는 최적화 기법을 메모이제이션(momoization)이라고 한다. 구분 하자면 다음과 같다. 부분 문제를 비슷한 크기로 나누고, 각각을 독립적으로 나누어 푼다. 큰 문..
분할 정복(Divide and Conquer) Goal 분할 정복에 대해 설명할 수 있다. 분할 정복 한 문제를 둘 이상의 부분 문제(sub-problem)로 나누어 해결하고 이를 합쳐 원래 문제를 해결하는 기법 분할 정복 알고리즘은 다음과 같이 세 부분으로 나누어서 생각해볼 수 있다. 분할 정복의 단계 분할(Divide) : 원래 문제를 분할하여 더 작은 하위 문제들 나눈다. 정복(Conquer) : 하위 문제 각각을 재귀적으로 해결. (정복 과정에서 더이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제를 기저 사례(base case)라 한다.) 병합(merge) : 하위 문제들의 답을 합쳐서 원래 문제를 해결 분할 정복을 적용하기 위해서는 문제에 다음과 같은 몇 가지 특성이 성립해야 한다. 부분 문제로 나누는 자연스러운 방법이 있어야 한다. 부..
백트래킹(back tracking) Goal 백트래킹에 대해 설명할 수 있다. DFS와 백트래킹을 설명할 수 있다. 백트래킹(backtracking)이란? 솔루션을 찾는 과정에서, 유망(promising)하지 않은 후보해에 대해 대해 빠르게 포기하고 이전 단계로 되돌아(back track)가 다른 후보해를 찾는 알고리즘 기법 DFS와 Backtracking DFS : 완전 탐색을 기본으로 하는 그래프 순회 기법으로, 모든 노드를 방문하는 것을 목표로 한다. Back-tracking : 불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법 => 일단 가보고 후보해가 될 수 없으면 다음 단계로 진행하지 않고 되돌아 나온다. DFS와 Back-tracking 둘다 재귀 호출 형태로 자주 구현이 되기 때문에 헷갈린다...
브루트 포스(brute force) Goal brute force에 대해서 설명할 수 있다. 브루트 포스(brute force)란? 완전 탐색(exhaustive search) 알고리즘 기법으로, 가능한 모든 경우의 수를 탐색하면서 문제 요구 조건을 만족 시키는지 확인하는 방법이다. *brute : 무식한, *force : 힘 즉, 무식하게 모든 경우에 대해 확인해 나가는 방법이다. 이 알고리즘은 자원이 충분하다면 100% 문제 해결이 가능한 알고리즘이다. 하지만 시간적 제한과 같이 자원의 제약이 있을 경우 적합하지 않을 수 있다. 완전 탐색 방법 선형 구조 : 순차 탐색 비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) *BFS, DFS에서 search는 일반적으로 생각하는 특정 값을 찾기 위한 탐색이 아니라, 순회(t..
Prim 알고리즘 Goal Prim 알고리즘에 대한 이해 Prim 알고리즘을 구현할 수 있다. Prim 알고리즘이 사용되는 예시를 들 수 있다. Prim(Prim's algorithm) 트리를 확장해 나갈 때 인접 정점 중 간선 가중치가 가장 작은 정즘을 선택하여 트리를 확장해 나가는 알고리즘 Prim알고리즘 동작 과정 그래프에서 정점 하나를 선택해서 트리를 만든다. 현재 트리가 n-1개의 간선을 가질 때 까지 다음 과정을 반복한다. (n은 그래프 전체 노드 개수) 트리에 포함되지 않은 인접 정점 중, 간선 가중치가 가장 작은 정점을 트리에 추가한다. 트리에 정점 v가 추가 되면, 트리에 인접한 정점이 갱신 될 수 있다. (v에 연결 되어 있으면서 트리에 없는 정점) 또한, 트리와 인접 정점 사이의 최소 가중치가 갱신 될..
유클리드 알고리즘(최대 공약수, 최소 공배수) Goal 유클리드 알고리즘(Euclidean algorithm)이란? 최대 공약수(GCD)를 구하는 알고리즘으로, 두 자연수 또는 두 다항식 사이에서 최대 공약수를 구할 때 사용되는 알고리즘이다. (유클리드 호제법이라고도 한다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.) 성질 2개의 자연수(또는 다항식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 즉, a와 b의 최대 공약수를 gcd(a, b)라고 하면, gcd(a, b) = gcd(b, r) 이 성립한다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 ..
모듈로 연산(modulo operation) Goal 모듈로 연산에 대한 이해 모듈로 덧셈, 뺄셈, 곱셈 연산에 대한 이해 모듈로 연산(Modulo Operation)이란? 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 정수론에서 모듈라 연산(modular arithmetic)이란, 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. *나눗셈 정리(division theorem) 더보기 두 정수로부터 몫과 나머지를 얻는 연산 나머지 있는 나눗셈(division with remainders) 또는 유클리드 나눗셈(Euclidean division)이라고도 한다. *정의 정수 a와 양의 정수 b에 대하여 $a = bq + r$을 만족하는 q, r이 유일하게 존재한다. (q는 몫, r은..

티스토리툴바