알고리즘 정리

7. Greedy Method

 

 

탐욕적 알고리즘의 개요

 

설계 절차 : 선정과정 -> 적정성 -> 해답 점검

 

탐욕적 알고리즘은 항상 최적의 결과를 준다고 보장 할 수 없다. 

 

---

최소 비용 신장 트리 : MST

신장 트리 : 순환경로(cycle)가 없어지도록 이음선을 제거하여 구성한 연결된 부분 그래프를 신장트리라 한다. (모든 정점은 포함 해야됨)

 

 

신장트리의 예

 

최소 비용 신장 트리 : G 그래프를 가지고 만든 여러 신장트리 중에서 가중치의 합이 최소가 되는 신장트리를 최소 비용 신장 트리라고 한다.

 

 

MST 구하는 알고리즘 종류

• Prim 알고리즘 : O(n^2)
• Kruskal 알고리즘 : O(nlogn) O(n^2logn)

 

 

Prim 알고리즘

 

---

최단 경로 구하기  : Dijkstra's Algorithm

 

 

 

Prim 알고리즘과의 차이점 : 다익스트라는 출발점에서의 거리를 고려해야한다

 

그리디 방법의 다익스트라 알고리즘 시간복잡도 : O(n^2)

DP 방법의 다익스트라 알고리즘 시간복잡도 : O(n^3)

 

 

---

 

A* 알고리즘

---

스케줄 짜기

 

대기시간 + 실제 실행 시간의 합을 최소로하는 최적의 스케줄을 찾는 법

CPU 스케줄링에서 이용됨

 

최적의 스케줄 : t3 -> t1 -> t2

 

무작정 알고리즘( 모든 경우의수 구하는법 ) : O(n!)

그리디 알고리즘 ( 정렬하면 끝 ) : O(nlogn)

 

 

---

배낭 채우기 문제

배낭 채우기 문제는 그리디로 풀면 최적의 해를 보장 받지 못하므로, 동적 프로그래밍 또는 branch and bound 로 풀어야 한다.

 

핵심 알고리즘

 

P[3][30] = ?

 

 

 

동적 계획으로 푼 배낭 채우기의 시간 복잡도 : O(2^n)

---

정리

 

 

 

 

 

 

 

---

8. Backtracking

 

기본 DFS

되추적이란? 어떤 노드의 유망성을 점검한 후, 유망하지 않다면 후손에 대한 검색을 중지하고 부모로 되돌아 간다.

자식노드를 검사해야함으로 Backtraking의 상태공간 트리에서는 DFS를 이용한다.

 

 

4 - Queens Problem

 

 

 

• 4^4승 = 256가지의 경우의 수가 생긴다. 
• n-Queens 일 경우 n^n의 경우의수로 매우 비효율적으로 보임
• 따라서 DFS의 방법을 쓰되 노드의 유망성(promising)을 검사하는 방법을 쓰자.

되추적 기법이 적용된 DFS

 

27개의 노드만 검사하면 정답이 처음으로 찾아짐.

프라미싱의 조건

 

개선된 알고리즘

 

• 분석 : 시간복잡도를 구하려면 얼마나 많은 노드를 검색하는지 구해야하는데, 유망한 노드의 조건이 어떠냐에 따라 달라진다. 정확하게 하려면 직접 세어보는 수 밖에 없음.
• 그래서 나온게 Monte Carlo Technique (확률적 알고리즘)

 

---

 

Monte Carlo Technique 

무작위로 공간트리르 생성하고 그과정을 여러번 반복하여 나오는 결과의 평균치를 사용한다 (확률적 복잡도를 구하는것)

 

 

Monte Carlo Technique를 사용하기 위해 선행되어야 하는 조건

• 상태공간 트리는 같은 수준에 있는 모든 노드의 유망성을 점검하는 절차는 같아야한다.
• 상태공간 트리의 같은 수준에 있는 모든 노드는 반드시 같은 수의 자식노드를 가지고 있어야 한다.

 

 

---

Graph Coloring

 

 

 

 

 

 

 

• Monte Carlo 기법을 사용하여 수행시간복잡도를 추정하여야 한다

 

 

---

Hamiltonian Circuits

 

 

• Monte Carlo 기법을 사용하여 수행시간복잡도를 추정하여야 한다

---

정리 

 

• Bactracking 에선 isPromising 조건을 잘 따져야하며, 시간 복잡도는 Monte Carlo 기법을 사용하여야한다.
• DFS를 이용하여 구하지만 생각보다 효율적이다

---

9. Branch and Bound

 

• 되추적 기법과 유사하게 상태공간트리를 만들어서 문제를 해결한다. 분기한정기법이라고도 함
• 최적의 해를 구하는 문제에 적용된다.
• 최적의 해인지 아닌지 알기 위해서는 모든 해를 다 고려하여야한다. (Backtracking과의 차이점)

 

분기한정과 되추적의 비교

 

---

배낭채우기 문제

 

• 분기 한정에서 배낭채우기 문제를 푸는데 필요한 핵심 수식

 

 

Best FS > DFS > BFS (효율이 높은 순서)

 

• DFS 기반 분기한정 

 

 

 

• BFS 기반 분기한정 

BFS는 큐를 이용한다

노드의 개수는 17개 이므로 DFS보다 더 좋지 않음을 알 수 있다.

 

• Best FS

 

 

가장 우수한 효율성을 보인다

우선순위 큐를 이용하여 구한다

 

 

• DP를 이용한 배낭채우기보다 분기한정으로 구한 배낭채우기 문제가 더 좋은 알고리즘 인가?  :
  확실하게 대답하기 어려움. 이유는 되추적 기법이나 분기한정은 시간복잡도를 구하기 어렵기 때문
• 하지만 1978년에 어떤 남자 둘이 Monte Carlo기법을 사용하여 DP보다 일반적인 경우 더 빠르다고 입증하였

---

Traveling Salesman : TSP ( 일주 여행 문제 )

 

• 모든 경우의 수를 센다면 (무작정 알고리즘) O(n!)의 성능이 나옴

 

 

DP 기반 으로 푸는 여행자 일주 문제

 

핵심 알고리즘

 

 

• 무작정 vs DP

n=20이면 무작정은 19!번 시간으로 3857년걸림

n=40일때 DP 또한 6년 걸린다

 

따라서 DP는 딱히 효율성이 좋다고 할 순 없음

 

 

분기한정으로 푸는 여행자 일주 문제

 

 

 

 

하지만 이것도 n=40이라면 지수적 시간복잡도가 나오고, 풀 수 없는 것이나 마찬가지

 

 

 

---