search

wooyn730 / Problem-Solving

백준&프로그래머스 풀이
0 stars 0 forks source link

DP 정복 #4

Open wooyn730 opened 6 months ago

wooyn730 commented 6 months ago

DP 정복

Dynamic Programming, 동적 계획법

정의

기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 특정한 알고리즘이 아닌 하나의 문제해결 패러다임?

큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 ('기억하며 풀기'라고도 함)

쓰는 이유

일반적인 재귀(Naive Recursion) 방식 또한 DP와 유사함. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다는 것이다.

사용 조건

DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.

1) Overlapping Subproblems (겹치는 부분 문제) => 동일한 작은 문제들이 반복하여 나타나야 함 2) Optimal Substructure (최적 부분 구조) => 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

image 출처

장단점

[백준] DP 필수 문제

image

wooyn730 commented 6 months ago

RGB거리

번호: 1149 사이트: 백준 난이도: 실버1

풀이

풀이를 참고했다.. 처음엔 재귀로 접근했는데 시간초과가 났다 DP의 필요성을 깨달았다.

wooyn730 commented 6 months ago

2×n 타일링 2

번호: 11727 사이트: 백준 난이도: 실버3

풀이

비슷한 문제를 풀어서 가물가물 기억났는데 점화식 찾는게 어려워서 결국 풀이를 참고했다. DP 정복하면서 점화식 찾아내는 연습을 열심히 해야 할 듯..

wooyn730 commented 6 months ago

연속합

번호: 1912 사이트: 백준 난이도: 실버2

풀이

풀이 참고 아직은 DP가 너무너무 낯설다 풀이를 참고하더라도 남은 3월 동안 DP에 익숙해지는 것이 좋을 듯

wooyn730 commented 6 months ago

가장 긴 증가하는 부분 수열

번호: 11053 사이트: 백준 난이도: 실버2

풀이

아이디어를 참고했다 (코드는 ㄴㄴ) 익숙해지는 과정이겠지~

image

wooyn730 commented 6 months ago

카드 구매하기

번호: 11052 사이트: 백준 난이도: 실버1

풀이

결국 또 풀이참고... 점화식 떠올리는 게 너무 어렵다 DP를 하기 싫으니 PS도 싫어진다

DP랑 안맞나? 강의 영상을 좀 봐야겠다

wooyn730 commented 6 months ago

포도주 시식

번호: 2156 사이트: 백준 난이도: 실버1

풀이

이번에도 어려워서 풀이를 참고했다. 근데 이번에는 뭔가 깨달은 느낌?

이번 문제에서의 포인트는 마지막 3잔 중 무엇을 마시지 않느냐고 xoo oxo oox로 표현할 수 있다.

이는 식에서 Oxoo Oxo Ox로 표현했다. 안먹는 잔의 전 잔을 마셨을 때의 최댓값을 가져와야 하는 것이다. O는 해당 위치에서의 최대 값이고, o는 해당 와인의 양이다.

사람의 논리적인 1번 표현을 구현에 사용하는 2번 표현으로 바꾸는 것을 떠올리는 게 포인트 같다.

wooyn730 commented 6 months ago

쉬운 계단 수

번호: 10844 사이트: 백준 난이도: 실버1

풀이

설명 참고 + 풀이 쪼끔 참고.. 점화식이 다양하고 아이디어를 요구해서 다른 알고리즘보다 어려운듯 DP 어렵따

wooyn730 commented 6 months ago

문제

wooyn730 commented 4 months ago

가장 긴 증가하는 부분 수열에 이은

가장 긴 ~ 시리즈 중 DP

LCS, 최장 공통 부분 수열 LIS(Longest Increasing Sequence)

가장 긴 감소하는 부분 수열

가장 긴 증가부분수열 참고함..

wooyn730 commented 4 months ago

이동하기

번호: 11048 사이트: 백준 난이도: 실버2

풀이

한 번에 풀었다 v^_^v 쉬운 문제였는지 조금 익숙해졌는지 모르겠다

wooyn730 commented 4 months ago

오르막 수

번호: 11057 사이트: 백준 난이도: 실버1

풀이

스스로의 힘으로 풀었다!! 오예 v^_^v

wooyn730 commented 3 months ago

Four Squares

번호: 17626 사이트: 백준 난이도: 실버3

풀이

쫄았는데 실3이라 쉽다

wooyn730 commented 3 months ago

숫자 야구

번호: 2503 사이트: 백준 난이도: 실버3

풀이

낮은 난이도의 문제였는데 처음에 DP가 아닌 인간이 숫자야구를 하는 방식으로 잘못 접근해서 조금 헤맸다 ㅠ