프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def solution(n): answer = 0 if n == 1: return 1 dp = [0 for _ in range(n+1)] dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = (dp[i-2] + dp[i-1]) % 1234567 return dp[n]
다이나믹 프로그래밍
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def solution(m, n, puddles): dp = [[0 for _ in range(m+1)] for _ in range(n+1)] for i in range(1, n+1): for j in range(1, m+1): if i == 1 and j == 1: dp[i][j] = 1 continue if [j, i] not in puddles: # 물에 잠긴 지역이 아니라면 dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007 else: # 물에 잠긴 지역이라면..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def solution(n): dp = [0 for _ in range(n+1)] dp[0], dp[1] = 0, 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] % 1234567 이건 왜 레벨2 문제일까...? 재귀함수로도 풀 수 있고, DP로도 풀 수 있는 피보나치 문제이다. 그렇지만 재귀함수로 풀면 같은 연산을 여러번 반복한다는 매우 큰 단점이 있다. 시간복잡도가 O(2^n)으로 n이 커질수록 연산의 수가 급증한다. 그렇기 때문에 ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def solution(sticker): answer = 0 if len(sticker) == 1: return sticker[0] # Case1) 0번 뜯음 dp = [0 for _ in range(len(sticker))] dp[0], dp[1] = sticker[0], sticker[0] for i in range(2, len(sticker)-1): dp[i] = max(dp[i-2] + sticker[i], dp[i-1]) answer = dp[-2] # Case2) 1번 뜯음(0번 못 뜯음) d..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def solution(triangle): n = len(triangle) for i in range(n-2, -1, -1): # 행 for j in range(i+1): # 열 triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]) return triangle[0][0] dp 배열을 따로 만들어서 했더니 효율성에서 걸리는거 같아서 그냥 triangle에 바로 저장했다. 아래에서 위로 올라가며 최대값을 갖는 경로를 찾도록 했다.
