나를 잃지 말자

문제:www.acmicpc.net/problem/2630

비고:

-Divide and conquer(분할-정복-조합)

-checker, divider, solve를 정의하여 사용, 최종적인 result인 dictionary를 유지

-난이도하

내소스코드:

boj.kr/39dad1f4b4aa4923a86f5f3f9d298ff4

문제:www.acmicpc.net/problem/1707

비고:

-dfs로 돌면서 label(dictionary)를 잡고 돌고

-이웃node가 label이 없으면 이전 nodes' label과 반대로 달고

-새로운 node마다 labeled 이웃 전체(이전 node를 지우고하는게 아니라)에 대해 label이 같은지 테스트가 관건

-난이도 중

내소스코드:

boj.kr/79b09fa7f4294aa19104a5d58d317c05

문제:https://www.acmicpc.net/problem/1931

비고:

-Greedy algorithm 활용(Optimal substructure, Greedy choice property)

-list.sort(key=lambda x: (x[1],x[0])) 형태로 주면, multiple fields에 대해 우선순위 줘가며 sorting이 가능

-다음 케이스를 놓쳐서 오래 걸림

5

4 4

4 4

3 4 

2 4 

1 4

정답은 3

-즉 포인트는 같은 종료 시간 내에 시작 시간을 정렬해야 한다는 점과 그 때 단순히 이어진 시작 시간 2개 교체해나가는 바람에 100%에서도 틀렸습니다를 얻게됨

-생각보다 오래걸림 ㅠㅠ

-난이도가 중

내소스코드:

boj.kr/d38992bbf196403e87c8619016a051c2

문제:https://www.acmicpc.net/problem/12845

비고:

-Greedy algorithm 문제가 뭐 없나 찾아보던 중 발견했는데, 너무 쉬운 문제

-Greedy를 떠나서, 잘 살펴보면 결국 max값이 (N-1)번 더해지고, 남은 것들을 더해주기만 하면 된다.

-따라서 Subproblem을 떠나서 Explicit solution을 구해버릴 수가 있음

-난이도가 낮음

내소스코드:

boj.kr/2d49ff4b4e924b0693a2574534588dd4

문제:https://www.acmicpc.net/problem/11047

비고:

-Greedy algorithm 활용(Optimal substructure, Greedy choice property)

-python3, divmod를 통해 몫과 나머지를 바로 구함

-난이도가 낮음

내소스코드:

boj.kr/d957b77f0a804e328ac66afd615ac0c6

문제:https://www.acmicpc.net/problem/14852

비고:

-Dynamic programming 활용

-점화식을 짤 때, 1개만 할지 보조를 둬야할 지 감이 옴

-이 문제는 다음과 같음

  -f(0)=1, f(1)=2, g(1) = 1

  -g(n) = g(n-1) + f(n-1)

  -f(n) = f(n-2) + g(n-1) + f(n-1) + g(n)

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

-결과를 나머지로 뱉어야되는 경우, 개별 계산에서 미리해서 숫자 절댓값 줄여서 계산하기 필요(이 짓을 안했더니 "시간초과" 받음)

내소스코드:

boj.kr/782710fea2044c59b94b89039aa4c440

문제:https://www.acmicpc.net/problem/2133

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = 3*D[n-2] + 2*D[n-4]로 생각했다가 고생했다.

여기서 3은

--

||

||케이스와

--

--

--케이스

||

||

--케이스 해서 총 3가지

2는

----

|--|

|--|와

|--|

|--|

----

이 때 n=6일 때 고려하지 못한 케이스가

------

|----|

|----|와

|----|

|----|

------이다.

따라서, 경우를 나눌 때, 우측 상단에 --로 시작해서

--

--

--로 끝나는 경우와

--

 |

 |

그리고

 |

--

--인 경우, 근데 마지막 2가지는 상하대칭성을 띄니까 1개의 함수로 세자

따라서, 구하고자하는 ans(n)과 보조함수 aux(n)을 정의

ans(n) = ans(n-2) + aux(n-1)

aux(n) = ans(n-1) + aux(n-1)

ans(0) = 1, ans(1) = 0

aux(0) = 0, aux(1) = 1로 두고 풀면 된다.

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

내소스코드:

boj.kr/7be8dbc0db4445888d24df8c7db663e8

문제:https://www.acmicpc.net/problem/11727

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = D[n-1] + (D[n-2] * 3) 에서  *3로 생각하면 안됨

(D[n-2]에서 2x1을 2개, 1x2을 2개, 2x2을 1개 사용하는 방식 총 3가지니까 *3하려고한다면, 3개 중 첫번째는 D[n-1]에서 count해서 중복발생)

따라서 D[n] = D[n-1] + D[n-2]*2

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

내소스코드:

boj.kr/d99f1a90f14341a090c4ba58bd460c33

문제:https://www.acmicpc.net/problem/11726

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = D[n-1] + (D[n-2] * 2), *2로 생각하면 안됨

(D[n-2]에서 2x1을 2개, 1x2을 2개 사용하는 방식 총 2가지니까 *2하려고한다면, 2개 중 전자는 D[n-1]에서 count해서 중복발생)

따라서 D[n] = D[n-1] + D[n-2]

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

내소스코드:

boj.kr/a173cca197ca42eb88e87bd88c47a6ba

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

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