-
(백준 2193번/1904번 이친수/01타일 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법PROGRAMMING/알고리즘 2024. 1. 19. 17:11
DP만 잘 알아도 코테가 쉬워진다는 말을 어디서 들은 적이 있는뎁...!ㅎㅎ 라이님 블로그를 보면서 실력을 키워보쟈!
동적 계획법(Dynamic Programming) (수정: 2019-02-07)
안녕하세요. 오늘 소개해 드릴 것은 바로 그 유명한 다이나믹 프로그래밍(Dynamic Programming)입니다. ...
blog.naver.com
🚨위 블로그에 있는 문제(1463번 1로 만들기, 9465번 스티커, 2294번 스티커)는 내 Tistory에서 따로 코드를 올리지 않을 예정이다. 또한 나의 모든 DP 풀이는 위 블로그에 있는 코드를 정답 코드로 생각하고 응용해서 푼 코드다!!
DP는 재귀함수를 사용하는 탑다운 방식과 반복문을 사용하는 바텀업 방식이 존재한다. 나도 개인적으로 직관적인 탑다운 방식을 선호하기는 하는데, 풀리기만 한다면 어떤 방식이든 다 좋다..😊
라이님 블로그에서 풀어준 문제는 다음과 같다.
1. 피보나치 수열 문제
2. 백준 1463번 : 1로 만들기 ← 점화식을 만드는 방식을 눈여겨보자
★3. 백준 9465번 : 스티커 ← 점화식의 변수를 2개로 만드는 방식을 눈여겨보자
★4. 백준 2294번 : 동전 2 ← Base case를 설정하는 방식을 눈여겨보자
dp 문제를 풀 때 지켜야 할 것
1. dp배열의 크기를 잘 정해야한다.
(스티커의 경우 2 * n 배열을 입력으로 받으며, dp 배열은 n * 3의 크기로 지정했다.)
2. dp배열은 문제를 풀면서 절대로 나올 수 없는 수로 초기화한다.
(피보나치수와 같이 양의 정수만이 답이 될 경우 -1로 초기화한다)
3. Base case를 꼼꼼하게 설정한다.
4. int result = ~로 정하고, max/min함수를 이용해서 업데이트하면 된다.
5. 탑다운 방식은 처음부터 정답을 호출하고, 바텀업 방식은 Base 케이스부터 올라간다.
(참고)
$(A+B) % M = (A%M + B%M) %M$
$(A-B) % M = (A%M - B%M) %M$
$(A*B) % M = (A%M * B%M) %M$
정수 리스트 초기화 하기
dp를 하기 위해서는 배열을 원하는 숫자로 초기화할 줄 알아야 한다!
int dp[100] = {5} 의 결과가 {5, 0, 0, ...., 0}이기 때문에 다른 방법으로 초기화해야 하는데, 많이 쓰는 방법은 memset과 fill이 있다.
1. fill 사용법(fill_n)
(매우 자세히 잘 알려준다!!)
[C++] fill, fill_n 배열을 초기화 하는 방법, 2차원, 3차원 배열 초기화
c++에서 배열을 초기화하는 방법으로 다음과 같은 초기화 방법이 있다 int a[3] = { 1, 2, 3 }; int b[3] = { 0 }; int c[] = { 0, 0, 0 }; 이것은 정수형 배열을 초기화 하는 방법이고 정수형 배열에서 배열의 모
zynar.tistory.com
//fill(시작 주소, 끝 주소, 변경 값); int iarr[9]; fill(iarr, iarr + 9, 5); fill(iarr, iarr +sizeof(iarr) / sizepf(iarr[0]), 5}; fill(&iarr[0], &iarr[9], 5); fill(&iarr[0], &iarr[sizeof iarr / sizeof iarr[0]], 5); //fill_n(시작 주소, 몇 번 할지, 변경 값); int iarr[9]; fill_n(iarr, 9, 5); fill_n(iarr,sizeof(iarr) / sizepf(iarr[0]), 5}; fill_n(&iarr[0], 9, 5); fill_n(&iarr[0], sizeof iarr / sizeof iarr[0], 5);
2. memset 사용법
https://blockdmask.tistory.com/441
[C언어/C++] memset 함수 메모리 초기화
안녕하세요. BlockDMask 입니다. 오랜만에 C언어, C++주제를 포스팅 하네요. 2020년 남은 11월 12월에는 C언어 C++주제는 목요일에 포스팅할 예정입니다. 일요일에는 파이썬 남은 문법들을 진행할 예정
blockdmask.tistory.com
//memset(변경하고자 하는 목적지의 첫번째 주소, 변경하고자 하는 값, 변경하고자 하는 길이 * sizeof(type)) char arr1[] = "HelloWorld"; memset(arr1, 'c', 5 * sizeof(char)); // 출력 결과 : cccccWorld
* 0과 char 타입 초기화에만 사용 가능하다!
백준 2193번
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
규칙성을 찾다가 보니 피보나치 수열과 같이 풀면 되는 문제였다!
종이가 없어서 급하게 냅킨에,, 쉽다고 생각했는데...
??????? 틀렸다고 해서 당황했다. 롱롱 문제가 아닐까 했는데 역시나 long long문제였다.
피보나치수도 잘 보면 숫자가 급격하게 커지는데, 이 문제도 피보나치 90번째 수를 부르는 것과 동일한 문제라서 터진 것 같았다.
맞는거 같은데 틀리는 분들은 int를 long long으로 바꿔보세용!!!
//백준 2193번 #define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <algorithm> const long long MAX = 90 + 1; long long dp[MAX]; long long f(long long N) { // N == 1 : 1 if (N == 1) return 1; // N == 2 : 10 if (N == 2) return 1; // N == 3 : 100, 101 if (N == 3) return 2; if (dp[N] != -1) return dp[N]; dp[N] = f(N - 1) + f(N-2); return dp[N]; } int main() { long long N; scanf("%lld", &N); std::fill_n(dp, MAX, -1); printf("%lld", f(N)); return 0; }
백준 1904번
https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
백준 1904번은 2193번 이친수 문제에서 초기값만 바꿔주면 바로 풀 수 있다.
//백준 1904번 #define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <algorithm> const long long MAX = 1000000 + 1; long long dp[MAX]; long long f(long long N) { // N == 1 : 1 if (N == 1) return 1; // N == 2 : 10 if (N == 2) return 2; // N == 3 : 100, 101 if (N == 3) return 3; if (dp[N] != -1) return dp[N]; dp[N] = (f(N - 1)%15746 + f(N-2) % 15746) % 15746; return dp[N]; } int main() { long long N; scanf("%lld", &N); std::fill_n(dp, MAX, -1); printf("%lld", f(N)); return 0; }
과거 풀이를 보니 바텀업 방식으로 풀었던데, 바텀업 방식이 확실히 메모리와 시간이 적게 걸리는 것 같다.
아래는 과거의 바텀업 풀이!!
#백준 1904번 #include <cstdio> int Arr[1000023]; int main(void){ int n,i; i = 4; scanf("%d", &n); Arr[1] = 1;Arr[2] = 2;Arr[3] = 3; for(i=4;i<1000010;i++){ Arr[i] = ((Arr[i-1]+Arr[i-2])%15746); } printf("%d", Arr[n]%15746); return 0; }
'PROGRAMMING > 알고리즘' 카테고리의 다른 글