1. 오늘까지 학습한 내용
백준 동적프로그래밍 문제들 1463, 11726, 11727, 9095번
사용 언어 : 자바
2. 알게 된 내용
-
다이나믹 프로그래밍이란
하나의 문제를 단 한 번만 풀도록 한다!
정렬은 동일한 문제를 다시 풀게 되는 경우가 없음.
Ex) 피보나치 수열에서 15번째를 구하려면 14 13번째를 구해야 함. 14는 13, 12가 필요.. >> 반복적으로 데이터를 계산해야 함. 그냥 하면 1,2,4,8…. O(2^n) 시간복잡도를 가짐. 배열에다가 저장하고 하면 O(n)이 됨.-
Dp 가정
1.큰 문제를 작은 문제로 나눌 수 있다. (15는 13, 14번째로 분할해서 나눌 수 있다.)
2.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (저장해두고 제시만 하면 됨. : 메모이제이션 )
-
-
1463번 문제
-
참고한 자료들 (잘 모르겠어서 처음부터 해설을 보면서 익히는 시간을 가졌음)
-
-
11726번 문제
처음에는 배열 크기를 1000으로 설정했었는데, N이 1000까지 가므로 0부터 1000까지 해서 총 1001개인 크기의 배열을 만들어야 함을 알게 되었다.
3번째 것으로 했을 때에는 틀렸다고 나왔는데, 다른 분의 코드를 참고해서 아예 dp에 저장할 때 % 10007을 진행했다. 그랬더니 맞았다고 떴다. 무슨 차이인지 정확히는 잘 모르겠지만 아예 dp에 10007으로 나눈 값을 저장했어야 하나보다.
코드 참고한 글 : https://yeoeun-ji.tistory.com/46이유를 찾아보니, 10007 나머지 계산을 하지 않으면 이전의 dp[n]의 값도 값이 전부 틀려져버려서 dp[n]을 구할 때마다 나머지 계산을 진행해야 한다고 한다!
이유 참고한 글 : https://antaehyeon.github.io/devlog/2018/05/08/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-2xn%ED%83%80%EC%9D%BC%EB%A7%81-(11726)/
-
11727번 문제
앞의 문제와 비슷한 문제여서 해볼만 하다고 생각하고 이번에는 스스로의 힘으로 풀어보려고 했다.
- 처음 나의 풀이)
N=4일 때까지 직접 그려보고 유추를 해보았는데..
Dp[n-1]에다가 21 타일을 오른쪽에 하나 붙이는 방식 dp[n-1] 개
dp[n-1]에서 21로만 이루어진 타일조합(1개)을 제외하고 나머지들에서 21타일을 왼쪽에 하나 붙이는 방식으로 +2개…
그리고 dp[n-2]에서 21로만 이루어진 타일(1개)을 제외하고 나머지들(22짜리 2개)끼리 조합하는 방식으로 생각해서 (dp[n-2] – 1) 2…
해서 점화식을 dp[i] = (dp[i-1]+2 + (dp[i-2]-1)*2) % 10007; 라고 잡았었는데 뭔가 이 방법은 너무 틀린 방법인 것 같아서 다른 글을 찾아보니까
조금 더 정확한 방법으로 하셨다..
https://girawhale.tistory.com/34
설명은 여기 글을 참고했는데 정말 잘 설명해두셔서 출처를 밝힌다. Dp[n-1], dp[n-2]를 먼저 기준으로 두고 생각을 해보는 습관을 길러야겠다는 생각이 들었다.
- 처음 나의 풀이)
-
9095번 문제
앞에서 진행한 내용들을 토대로 약간 고민을 하긴 했지만 한번에 성공했다!
3. 느낀 점
동적 프로그래밍이 너무 낯설고 어렵게 느껴져서 초반에 정말 많이 헤매고 미루게 되었었는데.. 유튜브에서 말로 해주는 설명들을 찾아보면서 갈피를 잘 잡게 되었다. 아직 초반이지만 문제들을 앞으로 꾸준히 풀어서 동적 프로그래밍 문제들을 막힘없이 풀게 되면 좋겠다!
0개의 댓글
