(미완)[Algorithm]알고리즘의 유형, 알고리즘 문제의 유형

알고리즘의 유형에 대해 알아보자.

simple recursive

backtracking

divide and conquer

dynamic programming

greedy

branch and bound

brute force

randomized

 

Simple recursive algorithms, 함수를 호출하면 그 내부에 다시 자기 자신을 호출하는 방식으로 정의된 함수

풀이의 Key point

-"정답을 찾은 경우", "다음을 호출해야하는 경우", "그만두어야하는 경우" 3가지 설정을 잘 해야함

-subproblem의 solution을 적절히 조합해서 본래문제의 solution으로 만들어야함

 

Backtracking algorithms, depth-first recurisve search, 주로 constraints satisfaction problem에서 사용, 각 지점마다 constraints을 만족하는 경우만을 헤아리면서 전체 solution을 찾아나선다. 진행 도중 진척이 없으면 직전 지점을 돌아와 남은 가능성을 시도한다. 따라서 depth-first search방식이다.

 

Divide and conquer algorithms, 본래 문제를 작은 문제로 나눠서(분할) 해결(정복)하고 조합하여 본래 문제의 해를 찾는 방식, 즉 (분할,정복,조합)을 따른다. 따라서 Top-down방식으로 구성. Subproblems가 reuse가 되지 않을 때를 Divide and conquer라 하고, reuse한다면 Dynamic programming algorithm이 된다.(Optimal substructure를 따른다면)

풀이의 Key point

-

 

Dynamic programming, Overlapping Subproblem(solutions to subproblems can be stored and reused in a bottom-up fashion), Optimal Substructure(Optimal solution contains optimal solutions to subproblems)의 성질을 요구한다. 즉 Dynamic programming은 remember past results and uses them to find new results. 특히 optimization problems에 사용한다. remember and reuse를 기법을 memoization이라 한다. 

풀이의 Key point

-문제의 환경(시간/메모리)제한에 따라 Top-down/Bottom-up을 골라야 한다.

-각 과정상 subproblem의 솔루션을 알필요가 없다면 table을 만들지 않아도 괜찮

-

 

Greedy algorithm, 매 순간 최적의 해를 찾아 최종적인 최적해에 도달하는 기법으로 2가지를 만족해야 한다. Greedy choice property(매 순간 최적의 해를 구할 때, 이전에 어떤 choice를 했는지는 고려해도 되지 않는 상황 혹은 비슷하게현재 최선의 선택을 할 때 미래에 무슨 선택을 할지 고려하지 않아도 되는 상황)와 optimal substructure의 성질을 띌 때 Greedy algorithm으로 해결한다. Greedy algorithm은 optimization problem에서 global optimum을 주지않을 수도 있지만, 계산 편리상 global optimum에 근사하는(혹은 global optimum이 될 수도 있어서)방식으로 자주 쓰인다.

풀이의 Key point

-

 

Branch and bound algorithms, optimization problem(예를 들어 feasible region R에서 f(x)의 최솟값을 찾는 문제)에서  R을 A/B로 나누어(branch), 각 subregion에서의 upperbound/lowerbound(bound)를 계산한다. 이 때 A의 lowerbound가 B의 upperbound보다 크다면 A를 폐기처분한다(pruning). Bound로 인해 pruning이 얼마나 효율적으로 되냐가 관건.

 

Brute force algorithms, 모든 경우의 수를 다 해보는 것

풀이의 Key point:

-모든 가능한 경우의 수를 헤아릴 것

-각 경우마다 해결법을 정의할 것

-위의 2개가 시간/메모리 내에 해결되는 지를 문제 풀이 방향을 잡을 때 계산해야함

 

Randomized algorithms, 문제를 품에 있어서 random number를 사용하는 알고리즘, 마치 quick sort에서 pivot으로 사용할 random number를 선택하는 과정.

 

 

 

-----------------------------------------------

알고리즘 문제의 유형에 대해 알아보자.

Decision problem:Search for a feasible solution.(Yes/No)

Optimization problem:Search for the best solution.

Enumeration problem:Find all feasible solutions.

 

Decision problem에서

P problem:the set of decision problems solvable in polynomial time by a DTM(Deterministic Turing Machine)

NP problem:the set of decision problems solvable in polynomial time by a NTM(Nondeterministic Turing Machine)

(NP는 Nondeterministic, Polynomial의 N과P)

NP-hard problem:the set of problems that every NP problem is reducible to in polynomial time.

NP-complete problem:the set of NP and NP-hard problem.(즉 NP인데 not NP-hard가 존재)

co-NP problem:the set of problems whose complement is NP.

 

P인 문제

NP and not P인 문제

not NP and not P인 문제

NP-hard and not NP인 문제

NP-complete인 문제

NP and co-NP인 문제

not NP and not co-NP인 문제

 

비고:

-DTM과 NTM의 주된 차이는 transition이 전자는 function 후자는 relation, 즉 가능한 action이 not unique

-reduce한 다는 것이 마치 4점짜리 문제를 2점짜리로 reduce한다는 어감이지만 사실은 반대의 의미임

-NP가 not P인 문제로 오해해서는 안된다. 

 

-----------------------------------------------

Graph, 문제의 상황을 점과 간선으로 표현하여 해결

풀이의 Key point

-node, edge, weight를 문제 상황에 mapping을 잘해야 함

-unweighted인 경우 dict_[node_i] = [node_i1, node_i2, ...] 형태로 문제 상황을 표현

-weighted인 경우 dict_[node_i] = [[node_i1, weight_i1], [node_i2, weight_i2],...] 형태로 문제 상황을 표현

-node x node size의 matrix(list of list)로 나타낼 수 있지만, space complexity가 O(V**2)로 메모리가 많이 필요

-격자형태의 경우 node별 연결된 node를 다 구해두지 않고, dx,dy를 통해 on-the-fly 방식으로 사용할 수도 있다.

 

DFS(Depth First Search), node에서 depth가 증가하는 방향으로의 search하는 방식

풀이의 Key point

-Graph정의

-node별 search했는지 확인용 배열

-dfs 재귀함수

 

BFS(Breadth First Search), node에서 1-depth로 가능한 nodes를 먼저 search하는 방식, 따라서 최단비용/시간 문제해결에 사용된다.

풀이의 Key point

-Graph정의

-node별 search했는지 확인용 배열

-queue

-while문

-문제 조건에 따라

  -각 node마다 다른 정보를 담는다면 그 정보를 포함하여 Graph정의, queue에 node와 정보를 함께 담기 등

  -다수의 queue사용, 혹은 deque를 사용

  -dist, 각 node별 시간/비용을 담은 배열

 

 

-----------------------------------------------------------------------------------------

Named problems의 나열(문제이름/솔루션/시간복잡도/공간복잡도/(P,NP-complete, NP-hard 등)/비고)

 

 

참고자료:

http://www.aistudy.com/heuristic/branch_and_bound.htm

http://www.aistudy.com/heuristic/branch_and_bound.htm