다이나믹_프로그래밍

[C++] 백준 2096번 내려가기

다이나믹 프로그래밍 문제. 메모리 제한이 상당히 제약적인데, 이 부분을 잘 이해했으면 쉽게 풀 수 있는 문제다. 처음에 배열을 10만 x 3개씩 만들어서 풀어보려 했는데, 메모리 초과가 났다. 결국 게시판을 참고해서 풀 수 있었다. 문제풀이 문제에 표현된 그대로, N번째 줄마다 1, 2, 3번째에 도달했을 때 최대, 최소값을 기록해두면 된다. 첫번째 칸에 도달한 경우에는 이전에 1, 2번째 칸인 경우이다. 두번째 칸에 도달한 경우에는 이전에 1, 2, 3번째 칸인 경우이다. 세번째 칸에 도달한 경우에는 이전에 2, 3번째 칸인 경우이다. 이 문제의 핵심은 이전에 지나온 칸, 앞으로 지나올 칸의 수는 저장할 필요가 없다는 것이다. 따라서 입력을 받을 때마다 i번째 칸에서의 최대, 최소값을 기록해두면 된다...

[C++] 백준 1965번 상자넣기

다이나믹 프로그래밍 문제. 어렵게 생각 안하고 풀었는데 틀렸습니다. 를 엄청많이 받고서야 풀었다. 그냥 완전탐색 비슷한 DP 느낌의 문제였다. 문제풀이 내가 푼 방식은 다음과 같다. 1번째 상자 ~ N번째 상자를 탐색한다. i번째 상자를 탐색하면서 자기 앞에 있는 상자들(1 ~ i) 중 가장 많이 담을 수 있는 상자를 골라서 + 1 해준 후 현재 상자가 최대 이만큼 담을 수 있다는 것을 기록해놓는다. 상자들 중 몇번째 상자가 가장 많이 기록할 수 있는지 출력한다. #include #include using namespace std; int boxCnt; int boxSize[1001]; int dp[1001]; int ans = 1; int main() { ios_base::sync_with_stdio(..

[C++] 백준 1890번 점프

다이나믹 프로그래밍 문제. 처음에 Bottom-Up 방식으로 시도했는데 틀렸다. Top-Down 방식으로 풀었을 때에도 방문처리를 안했어서 틀렸다. [C++] 백준 1520번 내리막 길 그래프 탐색 + 다이나믹 프로그래밍 문제 사실 이 문제를 본 건 엄청 오래 전이였는데, 그 당시엔 못 풀었었다. (검색도 했었는데, 그냥 이렇게 푸는거구나. 만 알고 넘어감. 바로 풀면 의미가 없 kimyunseok.tistory.com 위 문제와 거의 유사한 문제이다. 난이도는 왜이렇게 차이나는지는 모르겠지만, 위 문제를 풀 수 있다면 이 문제도 풀 수 있다. 문제풀이 다이나믹 프로그래밍의 TOP DOWN 방식과 DFS과 비슷한 로직을 혼용해서 풀었다. (1, 1)에서 시작해서 오른쪽, 아래쪽 방향으로 가면서 (r, c..

[C++] 백준 1520번 내리막 길

그래프 탐색 + 다이나믹 프로그래밍 문제 사실 이 문제를 본 건 엄청 오래 전이였는데, 그 당시엔 못 풀었었다. (검색도 했었는데, 그냥 이렇게 푸는거구나. 만 알고 넘어감. 바로 풀면 의미가 없으므로!) 이번에 학교에서 주최한 프로그래밍 대회에서 비슷한 문제를 봤었는데, 이 문제에 대한 기억이 떠올라서 검색해서 비슷한 문제를 맞춘 후에 다시 풀어봤다. 그래프 탐색 이론과 DP (Top-Down)방식을 사용하는 문제가 있다니 신기했다. 문제풀이 결국, (1, 1)에서 (M, N)까지 몇 개의 길이 있는지를 구하는 문제다. 나는 지금까지 DP는 Bottom-Up 위주로 많이 풀었었는데 이 문제는 지금 (1, 1)에서 알 수 있는 경우의 수가 없다. 그런데 (M, N)에서 (M, N)으로 가는 경우의 수는 ..

[C++] 백준 11660번 구간 합 구하기 5

다이나믹 프로그래밍 문제의 한 분야인 누적 합 문제. 처음에는 어떤 문제인지 몰라서 헤맸는데, 검색해서 이렇게 푸는 문제구나 라고 알게된 후 풀었다. 누적 합이라는 알고리즘을 사용해서 푸는 대표적인 문제였다. 문제풀이 문제에서 입력하는 (x1, y1)과 (x2, y2)를 입력받으면, 구간의 사이즈가 정해진다. 문제의 예시인 (2, 2)부터 (3, 4)까지라면 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 위에 파란색 배경에 흰색 글자로 된 숫자들이 구간으로 된다. 즉, x1이 행의 시작, y1이 열의 시작이 되고 x2가 행의 끝 y2가 행의 끝이 된다. 따라서 우리는 입력을 받을 때, 누적 합의 정보를 배열로 저장해놔야 한다. 어떻게 저장할 수 있을까? 누적 합 저장하기 나 같은 경우에는 위처..

[C++] 백준 11048번 이동하기

처음에 그래프 탐색 문제인 줄 알았던 문제. 알고보니 다이나믹 프로그래밍 문제였다. DFS로 구현하려고 하니까 시간 초과가 났다. 생각해 보면 최대 정점의 개수가 1000 x 1000 해서 1,000,000개가 되는데 각 점마다 3번의 메서드를 호출하게 된다. 이렇게 되면 3^1000000이므로 시간초과가 날 수 밖에 없다. DP인 것을 알고나면 쉽게 해결할 수가 있다. 문제풀이 DP의 관점에서, 각 칸의 도달할 수 있는 경우는 다음 세가지이다. y, x의 좌표로 부른다고 할 때, (y - 1, x)에서 (y, x) : 이전 칸이 위에서 아래로 이동한 경우 (r + 1, c) (y, x - 1)에서 (y, x) : 이전 칸이 좌측에서 우측으로 이동한 경우 (r, c + 1) (y - 1, x - 1)에서..

[C++] 2294번 동전 2

다이나믹 프로그래밍 문제. 분명 동전 1을 풀었었는데, 풀이가 잘 생각이 나지 않아서 예전에 블로그에 썼던 글을 살짝 보고 풀었다. 문제가 비슷하긴 한데 동전 1은 경우의 수의 개수를 묻는 문제라면 이 문제는 어떤 경우의수가 나오는지를 묻는 문제였다. 물론 동전 1의 풀이를 안다면 쉽게 풀 수 있었을 것 같다. 처음에 동전의 가치가 100,000보다 작거나 같은 자연수 라는 조건을 읽지 못해서 틀렸었다. 이 말의 뜻은, 동전의 가치가 원하는 값보다 클 수 있다는 것을 의미한다. 문제풀이 n가지 동전이 있을때, 각 동전을 몇 가지를 사용하는지를 나누어서 계산하면 된다. 테스트 케이스를 예시로 들자면, 1만 사용했을 때 1 2 3 4 5 6 7 ... 1개 2개 3개 4개 5개 6개 7개 1, 5를 사용했을..

[C++] 백준 1699번 제곱수의 합

수학적 사고를 묻는 다이나믹 프로그래밍 문제. 결국 풀지못하고 구글링해서 답을 보고 나서야 이해를 했다. 수학에 많이 약한 것 같다. 특별히 어려운 것은 없어보인다. 근데 이렇게 생각해 내는 과정이 너무 어려운 것 같다. i번째의 수에서 제곱수들을 빼 주어서 제곱수는 한 개이므로 하나를 더해주고 원래값과 대소비교를 해 주는 방식이다. 뭔가 계속 고민했어도 생각 못했을 것 같다. 정수론 / 수학의 문제이므로 문제를 풀이한다기보다는, 따로 정리를 하고 싶어서 올렸다.

[C++] 백준 9465번 스티커

다이나믹 프로그래밍 문제. 엄청 오래전에 풀었던 기억이 있는데, 사실 그 땐 못 풀어서 블로그에 검색해서 이해도 못하고 그냥 코드 제출해서 맞았었다. 지금은 새로 풀었는데 초기화 안해서 한 번 틀리고 맞췄다. 문제풀이 어려운 문제는 아니였다. Bottom Up 방식을 사용해서 각 칸에 도달했을 때, 어떤 경우가 최대가 될 수 있을지를 생각해보면 된다. ... 2 1 O ... ... ... 2 1 O ... O에 갈 수 있는 경우의 수를 봐보자. 여기를 가로기준 i번째라고 한다면 각 칸에서 최대값을 기록하는 배열을 dp배열이라고 하고 각 칸의 값을 기록하는 배열을 sticker 배열이라 하고 max(A, B)를 A, B중 더 큰값을 반환한다고 하자. dp[1][i] = max(dp[2][i - 1], d..

[C++] 백준 2293번 동전 1

다이나믹 프로그래밍 문제. 처음에 문제에 접근할 때, 재귀함수로 접근하려 했는데 시간제한을 보고 포기했고, 알고리즘 분류를 보고 DP인 것을 봐도 어떻게 풀어야 할 지 감이 잘 오지 않았던 문제. 많이 고민해봤지만 생각하기 어려워서 결국 솔루션을 보고 해결했다. 이런 방법으로 생각할 수도 있구나라고 생각했다. 풀이를 정리할 겸 글을 적는다. 문제 풀이 먼저 DP문제를 풀 때에는 항상 규칙을 찾아야 한다. 어떻게 Bottom Up 방식을 적용할 것인지 생각해야한다. 예시 케이스인 n = 3 / {1, 2, 5}, k = 5일때의 규칙을 찾아 보자면 1 2 3 4 5 6 7 8 9 10 1가지 { 1 } 1 1 1 1 1 1 1 1 1 1 2가지 { 1, 2 } 1 2 2 3 3 4 4 5 5 6 3가지 {..