[코테준비] 분할정복, DP, 그리디

분할정복

해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

대표적으로 퀵소트, 머지소트 등이 있고 고속 푸리에 변환 문제 FFT 가 대표적

 

FFT?

n차 다항식 두개를 곱할 때 시간을 줄이는 방법

O(n) → O(n log n)

---

다이나믹 프로그래밍

최적화 문제에 주로 사용

1. 최적해 구조의 특징을 찾는다
2. 재귀적으로 정의한다
3. 바텀업 방식으로 접근한다
4. 최적해를 구성한다

한 번 계산한 결과를 메모리 공간에 메모

리스트를 만들어서 값을 저장해놓고

계산하기전에 리스트를 체크하는 방식

 

*시간이 오래걸릴거 같으면 DP로 생각해보자

동적 프로그래밍은 시간-메모리 트레이드오프 관계를 가진다

---

그럼 다이나믹 프로그래밍을 언제 쓸 수 있을까?

최적 부분 구조 optimal substructure

→ 이는 그리디방법을 적용할 수도 있다

최적 부분 구조를 가지고 있지 않음에도 가지고 있다고 가정하지 않아야 한다 → np 완비 문제

 

무슨 소리입니까?

각각의 부분 문제들은 독립적이어야 한다는 것이다 → 하나의 해가 다른 부분 문제의 해에 영향을 주지 못함

하나의 부분 문제를 풀기 위해 어떤 자원을 사용하면 다른 부분 문제의 해로 그 자원을 사용할 수 없다

→ 자원을 공유하지 않아야 함

 

중복되는 부분 문제

부분 문제들의 범위가 작아야 한다

피보나치처럼 같은 계산을 여러번 해야할 때를 의미

→ 바텀 업이 더 효율적인 이유

 

그럼 탑 다운 문제에 DP를 쓰는 것은 별로인가요?

메모이제이션을 활용하면 탑 다운으로 설계 할 수도 있다

그리고 탑 다운의 경우 모든 부분 문제들의 해가 필요 없다면 백트래킹을 통해 시간적으로 유리할 수도 있다

---

그리디

최적의 해답을 구하지는 못하지만 많은 문제에 대한 해를 구할 수 있다

→ MST, 다익스트라, 집합 감싸기, 휴리스틱 문제(*휴리스틱 : 어림짐작의 기술)

 

부분 문제에서 모든 선택을 조사할 필요없이 한 개의 선택만 고려한다 → 그리디 선택

 

그럼 이 직관은 정확한 것인가?

네 증명가능하다 -> 부분문제에 대한 최적의 선택은 최종 문제의 최적 선택에 포함된다

 

그리디는 일반적으로 탑 다운 설계를 가진다

→ 미리 풀어 놓는 DP와는 다른 접근이기 때문

 

연속으로 선택을 하면서 문제의 최적해를 찾는 휴리스틱 방법론, 그리드 알고리즘

1. 최적 부분 구조를 찾는다
2. 재귀 해를 만든다
3. 그리디 선택을 하고 나면 한 개의 부분 문제만 남음을 보인다
4. 그리디 선택을 하여도 항상 안점함을 증명한다
5. 구현, 반복

---

그럼 언제 그리디를 쓰나요?

그리디 선택 특성

전체적인 최적해는 부분적인 최적 선택을 함으로써 만들 수 있다

 

무슨 소리입니까?

전체를 고려할 필요없이 지금 문제에서 최적을 고르면 된다는 의미

 

최적 부분 구조 optimal substructure

부분 분할로 풀 수 있는 문제여야 한다

 

그러면 그리디와 동적 프로그래밍은 취향차이 인가요?

미묘한 차이가 있다

→ 그 대표적인 문제가 냅색 문제(0-1 냅색과 같은 것)

분할 가능 배낭 문제의 경우 그리디로 풀 수 있지만 0-1의 경우 풀 수 없다

 

+

매트로이드

모든 그리디에 쓸 수는 없다

하지만 실용적인 대부분의 문제에 적용시킬 수 있기에 관심

나중에 알아보도록 하자

 

+ 23.09.19 추가

https://www.acmicpc.net/problem/9465

9465번: 스티커

규칙이 있는 것 같으면 구현을 할 때 앞에서 뒤를 가져온다는 생각으로 구현을 해야한다

dp[i] = max(dp[i-1], dp[i-2]) # 옳은 접근
dp[i] = max(dp[i+1], dp[i+2]) # 틀린 접근

코드로 보니 제대로 보이지만 첫 규칙을 찾을 때는 잘 안보이더라...