📚 알고리즘/DP(다이나믹 프로그래밍)
[백준 2156 ] 포도주 시식 (Java) - 실버1
# 문제 2156번: 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net # 접근법 구하는것 마실 수 있는 Max의 포도주 양 조건 연속으로 3잔은 못먹음 ← 얘 때문에 애먹음 포도주 잔의 갯수의 범위는 1 ≤ n ≤ 10,000 임 ← 즉, 음의 정수는 X 포도주의 양은 순서대로 주어진다(순서 바꾸지 못함) DP문제임을 알고 접근했지만, 3개 연속으로 먹지 못한다는 것을 어떻게 해결하면 좋을지 고민을 많이했음. 일단 Top-down 방식으로 푼 블로그도 있던데, 재귀함수로는....지금 내 머리로는 도..
[알고리즘] 동적계획법
동적 계획법 ( Dynamic Programming ) 1. 개요 동적 계획법 ( Dynamic Programming, 줄여서 DP ) 은 프로그래밍 대회에서 출제되지 않으면 이상할 정도로 높은 출제빈도를 보이고 있을 만큼 중요한 알고리즘 설계 기법입니다. 동적 계획법은 주어진 문제를 여러 개의 하위문제들로 나누어 먼저 처리한 후 그 답들을 이용해 문제를 처리하는 방법을 뜻합니다. 하위문제들을 수행할 시에는 같은 문제를 여러 번 처리하는 경우가 발생하는데 이 때, 한번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도가 비약적으로 빨라지게 할 수 있습니다. 2. DP 기본 예제 – 피보나치 수열 피보나치 수열은 F[0] = 0, F[1] = 1, F[i] = F[i-1] ..
[백준 11727] 2×n 타일링 2_dp(c++)
[문제] https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net [접근법] 다이나밍프로그래밍이란걸 보자마자 느낌..! 점화식을 찾아내기 위해 애썼음 [문제풀이] 고민하다가 찾은 점화식은 //홀수인경우 if (i % 2 != 0) { memo[i] = ((memo[i-1] * 2) - 1) % 10007; } else { memo[i] = ((memo[i -1] * 2) + 1) % 10007; } 근데 알고보니 원리가 따로있었다 경우의 수는 가로가1인 경우와, 가로가2인경우(2x2..
[백준 2096] 내려가기_dp(c++)
[문제] https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net [접근법] BFS랑 DP를 섞어서 접근할 생각으로 풀었다.. 풀다보니 메모리제한이 4MB인걸 보고 절망.. DP만으로 풀어야 한다는것을 깨달음..(친구의 도움을 받았다ㅠㅠ) [문제풀이] 구하고자 하는 값이 최대값과 최소값이므로, 2차원배열로 만들었다. (배열을 n x 3으로 나면 메모리 초과가 난다그래서 1x3 크기의배열을 만들어서 계속 갱신하는 식으로 풀었다.) dp1의 min, max값을 가지고 d..