우노

문제 링크 https://www.acmicpc.net/problem/11722 코드 import sys n = int(sys.stdin.readline()) item = list(map(int, sys.stdin.readline().split())) # 아이템 역순 정렬 item_reversed = item[::-1] # DP 테이블 생성 dp = [1] * n for i in range(n): for j in range(i+1,n): # 현재 위치의 값(item_reversed[i])보다 비교 대상(item_reversed[j])보다 크면, # 증가하는 순서가 성립하므로 DP 테이블 업데이트 if (item_reversed[i] < item_reversed[j]): dp[j] = max(dp[i]+1,..

들어가기 앞서, 배낭 문제(Knapsack Problem)는 제한된 공간에 가치가 높은 물건들을 최대한 많이 넣는 문제입니다. 이 문제는 물건을 나눌 수 있냐 없냐에 따라 두 가지 유형으로 나뉩니다. 분할 가능한 배낭 문제(Fractional Knapsack Problem) 물건을 일부분으로 나눌 수 있는 경우 (예: 설탕 500g 중 300g만 넣기) 그리디 알고리즘으로 해결 가능 0-1 배낭 문제(0-1 Knapsack Problem) 물건을 나눌 수 없고, 전부 넣거나 전혀 넣지 않아야 하는 경우 동적 프로그래밍(Dynamic Programming)으로 해결 가능 해당 문제는 0-1 배낭 문제(0-1 Knapsack Problem)에 해당됩니다. 설명 문제 설정 물건 개수: N = 4 배낭 용량: ..

문제 링크 https://www.acmicpc.net/problem/2011 풀이 마지막 숫자까지 해석할 수 있는 경우의 수는 아래 두 가지 경우의 수의 합과 같습니다. 마지막 1개 숫자 이전의 숫자들로 가능했던 경우의 수 마지막 2개 숫자 이전의 숫자들로 가능했던 경우의 수 따라서, “251”을 해석할 수 있는 경우의 수는 아래 두가지 경우의 수의 합과 같습니다. “마지막 1개 숫자 이전의 숫자들로 가능했던 조합” + “1” 즉, “25”의 경우의 수와 동일합니다. 마지막 1개의 숫자가 0 이상이기 때문에 가능합니다. “마지막 2개 숫자 이전의 숫자들로 가능했던 조합” + “51” 즉, “2”의 경우의 수와 동일합니다. 해당 경우엔 마지막 2개의 숫자가 10 이상 26 이하가 아니기 때문에 불가능합니다..

문제 링크 https://www.acmicpc.net/problem/2293 풀이 우선, 동전 1원으로 10을 만들 수 있는 경우의 수와 동전 1, 2원으로 10을 만들 수 있는 경우의 수를 구함으로써 규칙을 찾을 수 있습니다. 즉, 새로 갱신되는 dp[n]의 값은 이전의 dp[n]의 값에 dp[n - 현재 사용한 동전의 종류 크기] 가 됩니다. 해당 규칙을 통해 1, 2, 5원으로 10을 만들 수 있는 경우의 수를 계산할 수 있습니다. 추가적으로, dp[0]은 주어진 동전을 통해 0원을 만들 수 있는 경우의 수인데, 아무 동전을 사용하지 않았을 때 0을 만들 수 있으므로, 경우의 수는 1입니다. 코드 import sys n, k = map(int, sys.stdin.readline().split()) ..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 풀이 대표적인 경로 찾기 알고리즘입니다. 2차원 DP 테이블을 생성한 뒤, 시작 위치는 1로, 웅덩이의 위치는 -1로 변환합니다. 이후, DP 테이블의 칸들을 순서대로 탐색해 나갑니다. 현재 칸이 웅덩이(-1)일 경우엔, 0으로 변환합니다. 현재 칸이 웅덩이가 아닐 경우엔, 왼쪽 칸과 위쪽 칸의 합으로 변환합니다. 세부 알고리즘은 아래 코드와 같습니다. 코드 def solution(m, n, puddles): # 2차원 DP 테이블 초기화 dp = [[0] * (m+1) for _ in range(n+1)] # 시작 위치는 1로 처리 dp[1][1] = 1 # 웅덩이는 -1로 처리..

문제 링크 https://www.acmicpc.net/problem/2240 풀이 예제 입력1에 대한 DP 테이블은 아래와 같이 구성할 수 있습니다. 행 : 지난 초 (i) 열 : 사람이 움직인 횟수 (j) dp[i][j] : i초까지 j번 움직였을 때, 얻을 수 있는 최대 자두 수 DP 테이블은, i초에 자두를 먹을 수 있는 조건과 먹을 수 없는 조건을 통해 채울 수 있습니다. 자두를 먹을 수 있는 조건 i초에 자두가 2번 나무에서 떨어지고, 사람의 이동 횟수가 홀수라면(j % 2 == 1), 현재 2번 나무에 위치해 있다는 뜻이므로, 자두를 받아먹을 수 있음 dp[i][j] = max( i-1초 때 j 열의 자두 수, i-1초 때 j-1 열의 자두 수 ) + 1 이전 위치로부터 움직여서 받아 먹을 것..

문제 링크 https://www.acmicpc.net/problem/10844 풀이 자릿수 N이 주어졌을 때, 해당 자릿수의 자연수 중에서 계단 수를 만족하는 자연수는 몇개인지? 1의 자리 자연수들 중, 1~9는 계단 수를 만족하므로, 총 9개가 계단 수가 됩니다. 해당 문제는 아래 점화식과 2차원 DP 테이블을 사용해 해결할 수 있습니다. dp[자릿수][해당 자릿수에서 가장 뒤에 오는 숫자] = 경우의 수 해당 점화식은 아래와 같이 세분화할 수 있습니다. 가장 뒤에 오는 숫자 = 0 dp[자릿수][0] = dp[자릿수 - 1][1] 0의 앞에는 1만 올 수 있기 때문입니다. 가장 뒤에 오는 숫자 = 1~8 dp[자릿수][가장 뒤에 오는 숫자] = dp[자릿수 - 1][가장 뒤에 오는 숫자 - 1] + ..

문제 링크 https://www.acmicpc.net/problem/15486 풀이 예제 입력이 아래와 같다고 가정해봅시다. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 만약, 1일차에 상담을 진행한다면, 해당 상담은 3일동안 진행되며, 4일차부터 다시 상담을 진행할 수 있습니다. 따라서, 1일차에 상담을 진행할 경우의 최대 이익은, ‘1일 차의 상담 금액 + 4일부터의 최대 상담 금액’이 됩니다. 이러한 원리를 뒤쪽 날짜부터 적용함으로써 문제를 해결할 수 있습니다. 뒤쪽 날짜부터, 매 상담에 대하여 ‘현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[t[i] + i]])’을 계산하면 됩니다. 이후, 계산..

문제 링크 https://www.acmicpc.net/problem/11053 풀이 최장 증가 부분 수열이란? 각 원소가 이전 원소보다 크다는 조건을 만족하는 부분 수열 중, 가장 긴 부분 수열을 의미합니다. 따라서, 아래 DP 테이블과 점화식을 사용해 해결할 수 있습니다. dp[i] : i번째 수를 마지막 원소로 가지는 부분 수열의 최대 길이 0 ~ i-1번째 원소들을 순서대로 탐색하며, [i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + 1]을 dp[i]로 기록합니다 세부 동작 과정은 아래 링크를 통해 이해할 수 있습니다. https://wooono.tistory.com/575 코드 import sys n = int(sys.stdin.readline()) arr = list(map(int, ..

문제 링크 https://www.acmicpc.net/problem/11055 풀이 증가 부분 수열이란? 각 원소가 이전 원소보다 크다는 조건을 만족하는 부분 수열을 의미합니다. 따라서, 아래 DP 테이블과 점화식을 사용해 해결할 수 있습니다. dp[i] : i번째 수를 마지막 원소로 가지는 부분 수열의 합 0 ~ i-1번째 원소들을 순서대로 탐색하며, [i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + i번째 원소의 값]을 dp[i]로 기록합니다. 코드 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().rstrip().split(" "))) # dp 테이블 초기화 dp = [x for x in ar..