나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12905🔑 다이나믹 프로그래밍 (DP)점화식 : dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1board[i-1][j-1] == 1일 때 dp배열의 왼쪽, 위, 왼쪽 위 중 최솟값 + 1을 dp[i][j]에 기록한다.board리스트(위) dp리스트(밑) 결과 def solution(board): answer = 0 dp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)] for i in range(1, len(board) + 1): for j i..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42898 🔑 DP (동적 계획법) n, m 보다 1크게 리스트를 만든다. 1, 1 시작 위치에 1을 표시한다. 시작 위치일때와 물에 잠긴 지역일때는 건너뛴다. continue 그냥 길이면 좌표의 위 값 + 왼쪽 값을 현재 위치에 넣는다. 위에서 오는 경우와 왼쪽에서 오는 경우의 합 def solution(m, n, puddles): MAP = [[0] * (m+1) for _ in range(n+1)] MAP[1][1] = 1 for r in range(1, n+1): for c in range(1, m+1): if r + c == 2 or [c, r] in puddles: continue ..

문제 : https://www.acmicpc.net/problem/5557 🔑 DP dp 배열에 경우의 수를 저장 n = int(input()) num = list(map(int, input().split())) dp = [[0] * 21 for _ in range(n)] dp[0][num[0]] = 1 for i in range(1, n-1): for j in range(0, 21): if dp[i-1][j]: if j + num[i] = 0: dp[i][j-num[i]] += dp[i-1][j] print(dp[n-2][num[-1]])

문제 : https://www.acmicpc.net/problem/11057 DP n = int(input()) dp = [[1] * n for _ in range(10)] for i in range(len(dp)): dp[i][0] = i+1 for i in range(1, len(dp[0])): for j in range(1, len(dp)): dp[j][i] = (dp[j-1][i] + dp[j][i-1]) % 10007 print(dp[-1][-1])

문제 : https://www.acmicpc.net/problem/17202 DP 두 개의 번호를 풀이에 맞는 형태로 하나의 dp 리스트에 담는다. 점화식 : dp[i] = (dp[i] + dp[i+1]) % 10 dp.pop()으로 맨 뒤의 요소를 뺀다. 두 자리가 완성되면 종료, 출력 a = list(map(int, input())) b = list(map(int, input())) dp = [] for i in range(8): dp.append(a[i]) dp.append(b[i]) while len(dp) != 2: for i in range(len(dp)-1): dp[i] = (dp[i] + dp[i+1]) % 10 dp.pop() print(dp[0], end="") print(dp[1])

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12913 DP (Dynamic Programming) def solution(land): for i in range(1,len(land)): for j in range(4): tmp = land[i-1][j] # 이전 행 같은 열 값 저장 land[i-1][j] = -1 # max() 함수 사용에 의미 없는 값으로 설정 land[i][j] += max(land[i-1][0], land[i-1][1], land[i-1][2], land[i-1][3]) # 가장 큰 값을 누적 land[i-1][j] = tmp # 다음 열에서는 계산에 포함해야 하니까 다시 값 복구 return max(land[i..

문제 : https://www.acmicpc.net/problem/2294 Dynamic Programming (DP) n, m = map(int, input().split()) coins = [int(input()) for _ in range(n)] dp = [10001] * (m + 1) dp[0] = 0 for c in coins: for i in range(c, m+1): dp[i] = min(dp[i], dp[i - c] + 1) if dp[m] != 10001: print(dp[m]) else: print(-1)

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43105 DP(Dynamic Programming) 동적 프로그래밍 문제 삼각형의 꼭대기에서부터 바닥까지 값을 누적해나가고 바닥에 있는 값 중 가장 큰 값을 리턴 def solution(triangle): answer = 0 for i in range(1, len(triangle)): # 꼭대기에서 한칸 밑 부터 시작 for j in range(len(triangle[i])): if j == 0: # 가장 왼쪽 값이면 위 칸의 가장 왼쪽 값을 더한다. triangle[i][j] += triangle[i-1][j] elif j == len(triangle[i]) - 1: # 가장 오른쪽 값이면..