[ 알고리즘 ]/DP

[프로그래머스] N으로 표현

📌문제 https://school.programmers.co.kr/learn/courses/30/lessons/42895 🎖️난이도 Level 3 ✔️풀이 # 정답 (DP, Brute Force) def solution(N, number): if N == number: return 1 # 마지막 테스트 케이스 주의! (같으면 연산자 X) set_list = [set([int(str(N)*(i+1))]) for i in range(8)] for i in range(1, 8): for j in range(i): # 두 set의 product => 사칙연산 수행 for num1 in set_list[j]: for num2 in set_list[i-j-1]: set_list[i].add(num1 + num2) ..

[프로그래머스] 땅따먹기

📌문제 https://school.programmers.co.kr/learn/courses/30/lessons/12913 🎖️난이도 Level 2 ✔️풀이 # sol1) DP => getMax() def getMax(arr, idx): now_max = 0 for i in range(4): if i == idx: continue if now_max pythonic def solution..

[프로그래머스] 도둑질

📌문제 https://programmers.co.kr/learn/courses/30/lessons/42897 🎖️난이도 Level 4 ✔️풀이 # sol1 def solution(money): # 1. 첫 집을 무조건 터는 경우 (dp1) (마지막 집은 안 털음) dp1 = [0] * len(money) dp1[0] = money[0] # 집이 1개일 때 dp1[1] = max(money[0], money[1]) # 집이 2개 일 때 for i in range(2, len(money)-1): # 집이 3개 이상일 때 dp1[i] = max(dp1[i-1], money[i]+dp1[i-2]) # 2. 마지막 집을 무조건 터는 경우 (dp2) (첫 집은 안 털음) dp2 = [0] * len(money) d..

[프로그래머스] 등굣길

📌문제 https://programmers.co.kr/learn/courses/30/lessons/42898 🎖️난이도 Level 3 ✔️풀이 # sol def solution(m, n, puddles): grid = [[0]*(m+1) for _ in range(n+1)] # 테두리 하나 더 추가해서 0으로 채워두기 # 테두리랑 puddle들 따로 처리하지 말고 한번에 처리하기! (puddle도 -1말고 0으로 처리) for i in range(1, n+1): for j in range(1, m+1): if i == 1 and j == 1: grid[i][j] = 1 continue elif [j, i] in puddles: continue grid[i][j] = grid[i-1][j] + grid[i..

[프로그래머스] 정수 삼각형

📌문제 https://programmers.co.kr/learn/courses/30/lessons/43105 🎖️난이도 Level 3 ✔️풀이 # sol1 def solution(triangle): i_len = len(triangle) # 5 for i in range(1, i_len): for j in range(i+1): # i++ if j == 0: triangle[i][j] += triangle[i-1][0] continue # i++, j++ elif i == j: triangle[i][j] += triangle[i-1][j-1] continue # i++ or i++, j++ triangle[i][j] = max(triangle[i-1][j-1]+triangle[i][j], triangle[..