그리디 & 완전 탐색 & DP

 

그리디

 

마주하는 모든 문제들이 그리디로 풀리는 문제인지 일일이 증명할 수 없으므로 직관 + 판수로 감각을 익혀야겠다.

 

문제를 푸는 방법이 바로 떠오르지 않을 때 한 번쯤은 혹시 그리디로 풀리나? 하고 의심하는 것도 좋은 방법일 듯.

 

 

완전 탐색

 

개인적으로 문제를 접근함에 있어 가장 우선돼야 하는 방법이라고 생각한다.

 

완전 탐색으로부터 시작하여 규칙을 찾아내든, dp를 이용하여 연산 횟수를 효과적으로 줄이던지 문제를 이해하기 가장 좋은 접근 방법이다.

 

 

DP

 

까다로운 문제가 있었다.

 

state를 나타내기에 필수적으로 필요한 정보들을 잘 생각해봐야겠다.

 

+ 같은 상태를 나타내더라도 어떤 정보를 사용하는가에 따라 메모리 크기 차이가 날 수 있다. 잘 고려해주자.

 

 

P (Polynomial)

 

All decision problems that can be solved in polynomial time.

 

$$ T(n) = O(C * n^k) $$

 

 

NP (Nondeterministic Polynomial)

 

All decision problems that can be solved by a nondeterministic Turing machine in polynomial time.

 

Nondeterministic Turing machine - Wikipedia

 

P is NP, but not vice versa

 

 

NP-Complete

 

1. in NP

2. Every problem in NP is reducible to an NP-Complete problem in polynomial time.

 

ex. SAT (Boolean Satisfiability Problem), partition, vertex cover, independence set, clique, coloring, set cover, longest path, TSP, Hamiltonian Cycle, 

 

 

NP-Hard

 

Every problem in NP is reducible to an NP-Hard problem in polynomial time.