BOJ - DP

백준 12865번 - 평범한 배낭dp\[i]를 i 무게일 때 가능한 최대 가치로 가정한다.각 무게는 여러 가지 조합에 의해 가능하다.예를 들어 최대 무게(k)가 7일 때, 7, 1+6, 2+5, 3+4 등의 무게 조합이 있을 수 있다.각 물건의 무게에 대해 딱 맞는 무

백준 9251번 - LCS대표 문자열 DP 문제인 LCS 문제다.각 문자열을 축으로 하는 2차원 DP 배열을 생성한다.특정 위치의 두 문자의 값이 같으면 (왼쪽 대각선 값 + 1)을 현재 위치에 저장한다.값이 다르면 왼쪽 값과 위쪽 값 중 큰 값을 선택해 저장한다.두

백준 2293번 - 동전 1동적 계획법으로 문제를 해결한다.dp\[k]\[n]을 0원~k원에 대해 n번 동전까지 확인했을 때 가능한 경우의 수라 가정한다.현재 동전의 가치로 현재 목표 금액을 구성할 수 있다면 가능한 경우의 수는 이전 동전 가치에서 가능한 경우의 수

백준 11054번 - 가장 긴 바이토닉 부분 수열dp\[n]을 n번째 자리에서 가장 긴 바이토닉 부분수열의 길이라고 가정한다.정방향과 역방향을 각각 구한다.n번째 자리의 합 중 최댓값 - 1 이 정답이다.\-1 은 교집합 부분을 제외한 것이다.이중 for문으로 정방향과

백준 1520번 - 내리막 길DFS + DP단순하게 DFS나 BFS로 풀면 시간초과가 발생한다.단순 DFS라면 끝점만 찍고 오면 끝이겠지만 이 문제의 경우 가능한 모든 경로의 개수를 구하는 것이므로 메모이제이션을 사용해야 한다.dp 배열을 현재 자리에서 도착 지점까지

백준 2294번 - 동전 2dp 배열 int\[k]\[n] 을 k원을 n번째 동전까지 탐색했을 때 동전의 최소 개수라 가정한다.현재 n번째 동전으로 k원을 채울 수 있다면 min(이전 경우의 수, 자신의 가치를 뺀 경우의 수 + 1)을 고른다.n번째 동전이 k원보다 더

백준 2225번 - 합분해dp 배열 dp\[n]\[k]를 0~n 숫자 중에 k개를 사용하여 n을 만드는 경우의 수라 가정한다.dp\[0]\[1~k]는 1로 초기화 할 수 있다. 왜냐하면 합이 0이 되기 위해 0밖에 못 쓰기 때문이다.dp\[0~n]\[1]은 1로 초기화

백준 2133번 - 타일 채우기dp\[n]을 3xn 크기일 때 타일을 채울 수 있는 경우의 수라 가정한다.우선 n이 홀수이면 타일을 채울 수 없으므로 경우의 수는 0이다.그리고 3x2 크기는 항상 3가지 경우의 수이다.(세로2가로1, 가로3, 가로1세로2) 그래서 dp

백준 2565번 - 전깃줄없애야 하는 전깃줄의 수는 전체 전깃줄 - 제거하고 남은 전깃줄의 개수와 같다.그럼 제거하고 남은 전깃줄을 어떻게 구해야 할까?전깃줄이 서로 교차하지 않기 위해서는 전깃줄이 서로 크로스 되지 않고, 연속적으로 위치해 있어야 한다.즉, 전깃줄이

백준 17070번 - 파이프 옮기기 1dp\[x]\[y]\[k]를 (x, y)에 k 방향으로 도착한 경우의 수라고 가정한다.k는 가로(0), 세로(1), 대각선(2)으로 나눌 수 있다.(x, y) 위치에 가로(0)로 도착하는 경우의 수는 이전 열에서 가로로 도착한 경우

백준 2096번 - 내려가기최댓값 DP 배열과 최솟값 DP 배열을 준비한다.첫번째 열은 이전 행의 첫번째 열과 가운데 열 중 최댓값/최솟값을 통해서만 올 수 있다.가운데 열은 이전 행의 첫번째, 가운데, 마지막 열 중 최댓값/최솟값을 통해서 올 수 있다.마지막 열은 이

백준 14002번 - 가장 긴 증가하는 부분 수열 4기본적인 LIS 문제에 더해 부분 수열까지 출력해야 한다.여기서 중요한 것은 가장 긴 증가하는 부분 수열이 여러가지인 경우 아무거나 출력할 수 있어야 한다.LIS를 계산하면서 LIS의 마지막 인덱스도 함께 구한다.이후

백준 9252번 - LCS 2기본 LCS 문제에 더해 LCS를 출력해야 한다.LCS 길이를 구하는 방법은 동일하고, LCS를 구하는 방법은 다음과 같다.dp 배열 마지막에서 시작한다.해당 위치의 문자열이 같으면 스택에 문자를 기록하고, 왼쪽 대각선으로 이동한다.문자가

백준 10942번 - 팰린드롬?가장 단순한 방법은 M개의 질문마다 계산하는 것이다. 하지만 이는 O(N x M)으로 비효율적이다.M개 질문을 받기 전에 미리 길이가 1~N의 팰린드롬을 구해놓으면 계산없이 바로 출력할 수 있다.우선 길이가 1이면 무조건 팰린드롬이고, 길

백준 11049번 - 행렬 곱셈 순서dp\[s]\[e]를 s ~ e 구간의 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값이라 가정한다.최종 구하려는 것은 dp\[1]\[N]이라 할 수 있다.예를 들어 행렬의 크기 N이 4라면 가능한 경우의 수는 다음과 같다.dp

백준 11066번 - 파일 합치기dp\[s]\[e]를 s ~ e구간의 최소비용이라 가정한다.예제 1을 기준으로 1~4 구간의 최소비용을 구하려면 다음과 같은 경우의 수가 있다.dp\[1]\[1] + dp\[2]\[4] => 2~4번 합치고 1번 합치기dp\[1]\[2]

백준 1915번 - 가장 큰 정사각형dp\[x]\[y]를 (x, y) 위치를 정사각형의 오른쪽 아래 꼭짓점으로 보고 가능한 최대 한변의 길이라고 가정한다. 그리고 오른쪽 아래 방향으로 탐색한다.dp\[x]\[y]가 1이면 정사각형이 가능한 것이다. 그러면 왼쪽과 위쪽,

백준 2011번 - 암호코드dp\[n]을 n번째 자리에서 가능한 가지수라 가정한다.첫번째 자리가 0이면 잘못된 암호다.첫번째 자리는 무조건 하나로만 해석할 수 있으므로 dp\[1] = 1로 초기화하고, 두번째 자리부터 구한다.해당 자리의 수가 0이 아니면, 이전 경우의

백준 7579번 - 앱우선 그냥 눈으로 풀어봤다.위 표는 0~c의 합의 비용으로 확보할 수 있는 최대 메모리를 구한 것이다. 6의 용량으로 최소 60의 메모리를 확보할 수 있으므로 6이 정답이다.구한 과정을 코드로 구현해야 한다. 비용 6으로 최대 확보 메모리를 구할

백준 17404번 - RGB거리 21번 집부터 빨강 또는 초록 또는 파랑으로 칠하기 시작했을 때 각각을 비교해야 한다.dp\[i]\[j]를 i번 집까지 탐색했을 때 j 색깔(빨강0, 초록1, 파랑2)의 최소비용이라 가정한다.딱 세번 반복하여 각 색깔로 시작하는 경우 해

문제 백준 15486번 - 퇴사 2 아이디어 dp[i]를 i번째 날부터 퇴사일(N+1일)까지 얻을 수 있는 최대 금액이라 가정해본다. 그럼 i가 1일때를 구해야 하므로 N일부터 1일 순으로 결과를 도출해 나간다. 현재 일수 i에서 T[i]을 더했을 때 퇴사일(N+

백준 9084번 - 동전DP로 해결할 수 있는 기본적인 문제이다.M원의 경우의 수를 찾기 위해 1원부터 M원까지 점진적으로 경우의 수를 찾아나가야 한다.dp\[M]\[N]을 M원을 N개의 동전으로 만들 수 있는 경우의 수라고 가정한다.0원을 만드는 것은 동전을 하나도

백준 5557번 - 1학년dp\[i]\[j]를 i번째 숫자까지 계산했을 때 결과가 j가 되는 경우의 수라 가정한다.j는 0 ~ 20으로 제한할 수 있으며, dp\[1]\[첫번째숫자] = 1 로 초기화 가능하다.2번째부터 경우의 수를 구해나가면 된다. 이전 번째에 j가

백준 2631번 - 줄세우기문제 예제에서 옮겨지지 않은 번호의 특징이 무엇인지 살펴보았다.옮겨지지 않은 번호는 이미 정렬이 된 상태이기 때문에 움직이지 않아도 된다.즉, 전체 길이 N에서 LIS를 구해 뺀 값이 정답이 된다.예상 시간 복잡도 : O(N^2)

백준 5582번 - 공통 부분 문자열기본적인 LCS 문제 해결 과정으로 해결한다.두 문자열의 길이 : N, M예상 시간 복잡도 : O(N x M)

백준 2629번 - 양팔저울확인하고자 하는 구슬들의 입력을 받을 때마다 계산하지 않고 dp 테이블로 미리 결과를 구해놓고 dp 테이블을 참조해 결과를 출력한다.dp\[i]\[j]를 i번째 추까지 저울에 올렸을 때 j 무게를 알 수 있는지 여부라고 가정한다.구슬을 항상

백준 13398번 - 연속합 2수를 제거하지 않은 경우와 수를 제거하는 경우 중에서 최대 부분합이 나올 수 있다.수를 제거하지 않은 경우는 dp1\[i] = max(dp1\[i-1] + arr\[i], arr\[i]) 점화식으로 구할 수 있다. 연속된 부분을 이어가는

백준 15989번 - 1, 2, 3 더하기 4"dp\[n] = 1, 2, 3으로 n을 나타내는 방법의 수"라고 가정해서 시작했다가 순서가 다르면 같은 것으로 쳐야 하는 조건 때문에 도저히 일반화할 아이디어가 생각나지 않아 다른 점화식을 생각해봤다."dp\[i]\[n]

백준 2098번 - 외판원 순회우선 가장 단순한 방법은 다음과 같이 재귀를 통한 완전 탐색이 있다.시작 도시 N개, 다음 도시는 N-1개, 그 다음 도시는 N-2개 ... 이런 식으로 선택 가능하므로 완전 탐색의 시간 복잡도는 N!과 같다. N이 12만 돼도 5억에 가

백준 1562번 - 계단 수일반적인 계단 수 문제같은 경우 직전의 수만 알면 됐기 때문에 2차원 배열이면 충분했다.하지만 이 문제의 경우 추가적으로 지금까지 사용했던 수들을 기억해야 하기 때문에 비트 마스킹을 활용한 3차원 배열을 사용한다.dp\[n]\[i]\[bit]

백준 2240번 - 자두나무자두가 몇 번 움직이느냐에 따라서 받을 수 있는 자두의 양이 달라질 수 있어 DP를 사용해 구한다.처음에는 dp\[t]\[w] 2차원 배열을 두어 t초에 w번 움직여 얻는 자두의 최대 개수라고 가정했다가 현재 자두의 위치도 최대 개수에 영향이

문제 백준 1446번 - 지름길 아이디어 처음에는 거리만큼 그대로 dist 배열의 각 인덱스를 초기화해준다. N개의 지름길 정보를 저장하고, 0 ~ D까지 DP 방식으로 최솟값을 갱신해간다. 가중치가 모두 1이기 때문에 이전 거리에서 1을 더한 값만 비교하고, 연

문제 백준 10844번 - 쉬운 계단 수 아이디어 인접한 모든 자리의 차이가 1이기 때문에 특정 수 x(0~9) 이전, 이후에 올 수 있는 수는 제한되어 있으므로 DP로 값을 채워나갈 수 있다. dpn 를 길이가 n, 마지막이 x인 계단 수의 개수라고 가정한다.

문제 백준 14501번 - 스티커 아이디어

문제 백준 1509번 - 팰린드롬 분할 아이디어 DP로 길이별 팰린드롬 구하는 방법을 통해 0부터 모든 길이까지 팰린드롬 배열을 구한다. dp[i]를 0부터 i까지 분할의 최소 개수라고 하고, 0부터 N-1 까지 팰린드롬 배열을 사용해 dp 배열을 채운다. 만약

문제 백준 2342번 - Dance Dance Revolution 아이디어

문제 백준 10164번 - 격자상의 경로 아이디어 > 예상 시간 복잡도 예상 시간 복잡도 : 코드 구현 - 자바 코드 구현 - 파이썬

문제 백준 2169번 - 로봇 조종하기 아이디어 > 오른쪽과 아래로만 움직일 수 있으면 간단한 DP 식으로 해결할 수 있지만 이 문제에서는 왼쪽으로도 움직일 수 있다는 조건이 있다. 예상 시간 복잡도 예상 시간 복잡도 : 코드 구현 - 자바 코드 구현 -