728x90 반응형 동적프로그래밍5 [백준/Python] 11722 가장 긴 감소하는 부분 수열 문제: https://www.acmicpc.net/problem/11722 사용 알고리즘: DP 수열 A 가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 문제 ex) A = {10, 30, 10, 20, ,20, 10} -> 30, 20, 10 입력수열 A 의 크기 N (1 수열 Ai (1 여기서 중요한 것은 부분 수열이 연속적일 필요가 없다는 것!-> 이중 for 문을 돌면서 현재 위치의 수와 (처음~현재 위치) 까지의 수들을 비교해서 현재 위치에서 가장 긴 감소하는 배열의 길이를 찾기 i 는 현재 위치, j 는 처음~현재 위치까지 수들을 비교하기 위한 인덱스 현재 위치를 고정시켜놓고 현재 위치까지 수열을 돌면서 현재 위치와 방문한 수열의 값을 비교for i in range(n): .. 2024. 7. 2. [백준/Python] 11726 2*n 타일링 문제: https://www.acmicpc.net/problem/11726 사용 알고리즘: DP 2 * n 크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 방법의 수를 구하는 문제 -> 전형적인 DP 문제 주어진 직사각형을 채우기 위한 방법의 수를 구하기 위해 도미노를 쪼개어 생각해보자. 1 * 2 / 2 * 1 의 두 가지 타일로 주어진 직사각형의 가장 오른쪽 부분을 채우는 방법을 생각해보면 아래와 같이 2가지 방법이 있다. -> dp[n] = dp[n-1] + dp[n-2] # 입력n = int(input())# dp 초기화, 인덱스 1 부터 사용할 것이기 때문에 1001 칸을 만들어줌dp = [0] * 1001dp[1] = 1dp[2] = 2for i in range(3, n+1):.. 2024. 7. 2. [백준/python] 1463 - 1로 만들기(DP) 문제: https://www.acmicpc.net/problem/1463 사용 알고리즘: DP 할 수 있는 연산- 1 빼기- 2로 나누기- 3으로 나누기 나는 dp 문제를 풀 때 잘 모르겠으면 손으로 써가면서 규칙을 찾아 점화식을 쓰는 편인데 이번 문제도 쓰면서 풀다보니 규칙이 보였다. dp[1] = 0 -> 1 은 아무 연산을 하지 않아도 1 이기 때문에 연산 횟수는 0dp[2] = 1 -> 2 는 2-1 또는 2//2 를 해서 1 로 만들 수 있고 최소 연산 횟수는 1dp[3] = 1 -> 3 은 3//3 을 해서 1로 만들 수 있고 최소 연산 횟수는 1 dp[4]: 4 -> 2 -> 1dp[5]: 5 -> 4 -> 2 -> 1dp[6]: 6 -> 2 -> 1dp[7]: 7 -> 6 -> 2-> .. 2024. 5. 20. [백준/python] 2156 - 포도주 시식 문제: https://www.acmicpc.net/problem/2156 사용 알고리즘: DP n 개의 포도주를 처음부터 차례로 돌면서 먹을지 안 먹을지 결정 - i 번째 포도주를 먹지 않는다 -> dp[i-1]- i 번째 포도주를 먹는다i-1 번째 포도주를 먹는 경우 (직전 포도주를 먹는 경우) -> dp[i] = dp[i-3] + wine[i-1] + wine[i]i-2 번째 포도주를 먹는 경우 (전전 포도주를 먹는 경우) -> dp[i] = dp[i-2] + wine[i] 점화식: dp[i] = max(진전 포도주를 먹는 경우, 안먹는 경우, 전전 포도주를 먹는 경우) (i > 2) -> dp[i] = max(dp[i-3] + wine[i-1] + wine[i], dp[i-1], dp[i-2].. 2024. 5. 20. 이전 1 2 다음 728x90 반응형
