[SCCC 스터디] 7일차 DP1

SCCC 스터디 7일차 1月 21日

DP 어려워;;;;;;;;

1. DP1

DP는 다이나믹 프로그래밍의 약자로 한국말로 하면 동적계획법이라 한다. (DP가 부르기 좋은 듯)

처음에 디피가 뭔지도 모르겠고 그냥 "어렵다"라는 말만 들어서 접근하기가 매우 힘들었다. 근데 맨 처음 풀 때 삽질과 다른 사람이 푼 방식을 보고 대충 어떤 느낌인지 깨닫기 시작했다.

  - 중복계산을 피해 한번 계산 했던 것은 저장해서 처리속도를 높인다.

  - 큰 문제를 해결하기 위해 작은 문제를 이용(이전 작업을 이용)하여 큰 문제를 해결

  - 점화식을 이용해 문제 해결

첫 번째에 쓴 건 많이 들어봤을 것이다. (메모이제이션, memoization)

두 번째는 분할정복과 비슷하다는 것을 느낄 수 있다.

세 번째에는 점화식을 세워 풀면 된다는 아주 간단하게 말할 수 있지만, 이를 다시 말하면 재귀적인 특성을 파악하고 그 재귀적인 특성을 가지고 풀면 되는 것이다. (이것도 2번이랑 비슷한 얘기이긴 하다.)

DP를 풀때에는 Bottom-Up, Top-Down 이 두가지 방식으로 많이 사용하는데 둘 다 반복문으로 가능하긴 하다. 하지만 내가 풀 때에는 Bottom-Up은 반복문, Top-Down은 재귀를 이용해서 자주 푼다. (난 2번 방법을 이용해서 많이 푼다. 물론 1번은 필수로 이용한다.)

(난이도 표시는 매우 주관적인 것이며, 사람마다 어렵게 느껴지는 정도가 다를 수 있습니다.)

1. 피보나치 수 - ●○○○○

2. 파도반 수열 - ●◐○○○

3. 1로 만들기 - ●●○○○

4. 1, 2, 3 더하기 - ●●○○○

5. 2xn 타일링 - ●●○○○

6. 쉬운 계단 수 - ●●○○○

7. 동물원 - ●●◐○○

8. 1, 2, 3 더하기 3 - ●●◐○○

9. 2xn 타일링 2 - ●●◐○○

10. 01타일 - ●●○○○

11. 이친수 - ●●○○○

12. 계단 오르기 - ●●●○○

13. 오르막 수 - ●●○○○

14. 줄어들지 않아 - ●●○○○

15. 스티커 - ●●●○○

16. 돌 게임3 - ●●●○○

17. 사탕 가게 - ●●●○○

18. 축구  - ●●●◐○

19. 경찰차 - ●●●●◐