dp

🗂️ 문제링크: https://www.acmicpc.net/problem/11051  💡 접근법이항 계수란 그냥 조합이다. 즉, (5, 2)란 5C2를 구하는 것이다.이항계수의 성질을 이용하여 동적계획법으로 문제를 풀었으며, 이항계수의 성질은 다음과 같다. nCk = nCn-knCk = n-1Ck + n-1Ck-1파스칼의 삼각형을 본다면 더 쉽게 이해가 가능할 것이다.  위 두 성질을 기반으로 세운 DP 점화식은 다음과 같다.dp[i][k] = dp[i-1][k] + dp[i-1][k-1] (i≥1, k≥1) 추가적으로 코드에서는 1번 성질을 이용해서 for문의 반복횟수를 줄일 수 있다.예시로, 5C2 == 5C3이므로 5//2까지만 순회한다면 5에 대한 모든 조합의 경우를 구할 수 있다.5C0 ==..

🗂️ 문제문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.예를 들어..

🗂️ 문제링크: https://www.acmicpc.net/problem/1904 💡 접근법00과 1을 조합하여 N자리의 수를 만드는 문제이다.문제에서는 제시하는 자릿수에 따라 만들 수 있는 수의 개수가 달라진다. 규칙을 찾아보기 위해 다음과 같이 N에 따라 가능한 경우를 나열해보았다. N=1일 때, 1 ⇒ 1개 N=2일 때, 11, 00 ⇒ 2개 N=3일 때, 001, 100, 111 ⇒ 3개 N=4일 때, 1111, 0011, 1001, 1100, 0000 ⇒ 5개 N=5일 때, 11111, 00111, 10011, 11001, 11100, 00001, 00100, 10000 ⇒ 8개 규칙을 보니 DP인 걸 단숨에 알아낼 수 있었다. 하지만 왜 DP인가를 생각해보면, 그 이유는 다음과 같다. 2진..

🗂️ 문제링크: https://www.acmicpc.net/problem/14002 💡 접근법DP를 통해 LIS를 푸는 문제의 응용편이다. i번째까지 순열에 대해 증가하는 순열인 경우이면서 부분 순열의 길이가 더 길어질 때, dp에 현재까지의 부분 순열을 저장한다.이후, 가장 길이가 큰 부분 순열에 대해 부분 순열의 길이와 부분 순열을 출력한다. 😎 내 코드import sysN = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))dp = [[arr[i]] for i in range(N)]for i in range(1, N): for j in range(i): if arr[i] > arr[j] an..

🗂️ 문제링크: https://www.acmicpc.net/problem/2579  💡 접근법i번째 계단까지 오르는 데 최댓값을 구해야한다는 DP 관점은 이해했으나, 점화식을 제대로 세우지 못했다. 계단에 오를 수 있는 경우는 1. i-1번째 계단에서 오르는 경우, 2. i-2번째 계단에서 오르는 경우이다.하지만 i-1번째 계단에서 오르는 경우가 연속된다면, 최종적으로는 i-2 → i-1 → i번째 순으로 계단에 오르게 된다.이를 처리하기 위해 i-1번째 계단에서 오르는 경우에 대해서는 무조건 그 이전에는 i-3번째 계단을 거쳐야 한다. 따라서 이를 고려한 최종적인 점화식은 다음과 같다.dp[i] = max(dp[i-3] + stairs[i-1], dp[i-2]) + stairs[1] (i ≥ 2) ..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법DP의 top-down 방식으로 풀었다.triangle을 모두 탐색하면서 값을 업데이트 해나갔다. 현재 위치까지 도달하는 모든 경로 중 최댓값을 저장해야 한다. 따라서 위의 칸의 대각선 두 값 중 더 큰 값을 선택하여 더한다. 만약 대각선에 값이 존재하지 않는다면, 이는 삼각형의 범위를 벗어난 것이므로 이를 따로 처리해야 한다. 점화식은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (i>=1, ..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🚀 시행착오def solution(m, n, puddles): # m: 열, n: 행 answer = 0 dict = {} # key: 경로, value: 경로 개수 visited = [[False] * (m+1) for _ in range(n+1)] dx = [0, 1] # 아래쪽, 오른쪽 dy = [1, 0] def DFS(y, x, cnt): visi..

🗂️ 문제링크: https://www.acmicpc.net/problem/1149 💡 접근법모든 집에 대해 비용을 적은 것부터 많은 것으로 정렬한 뒤, 비용이 적은 집에 대해서 우선적으로 처리하는 방식이다.즉, 현재 순간에서 가장 비용이 적은 것을 선택한다. 이때 문제에서 제시한 바와 같이, 이전 집과는 같은 색을 칠하지 않는 조건을 처리한다. 😎 내 코드import sysfrom collections import dequeN = int(sys.stdin.readline())house_cost = []RGB = ["R", "G", "B"]for i in range(N): costs = list(map(int, sys.stdin.readline().split())) for c, r in z..