https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 나는 문제 보자마자... 백트레킹이다 하고 접근했는데.... 이게 다이나믹 이었다... 하하 오랜만에 푸는 문제라 감각이 많이 떨어졌다. 하하 다시 하루 생각해봤는데 전형적인 메모제이션이다! dp의 유형은 문제를 잘게 조깨는게 중요하다. 아래의 문제를 잘 해석해보자 중요한 부분은 def solution(n..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net dp = [0] * 1001 dp[1] = 1 dp[2] = 3 for i in range(3,1001): dp[i] = dp[i-1] + dp[i-2] * 2 n = int(input()) print(dp[n] % 10007) https://cijbest.tistory.com/21 [백준 11727 : PYTHON] 2xn 타일링 2 문제 풀기 : 11727번 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net dp = [0] * 13 dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in range(4,11): dp[i] = dp[i -3] + dp[i-2] + dp[i-1] t = int(input()) for _ in range(t): n = int(input()) print(dp[n]) dp 중 메모지에이션을 이용하여 풀었다. dp는 진짜 아이디어가 생각이 안나면 진짜 안풀리는거 같다. 이 문제의 풀이는 1 = 1 2 = 1+1 = 2 3 = 1 + 1 + 1 = 1 + 2 = 2..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 다이나믹프로그래밍으로 메모지에이션을 활용해서 푼 방법인다. 이문제를 풀기위해 나는 결국에는...? 못풀었지만 다른 분들의 풀이를 참고하며 풀었다 https://claude-u.tistory.com/208 #159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘 https://www.acmicpc.net/probl..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n = int(input()) num = list(map(int,input().split())) # n = 10 # num = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] dp=[0]* (len(num)) dp[0] = num[0] for i in range(1,len(num)): dp[i] = max(num[i],dp[i-1]+num[i]) print(max(dp)) 이 문제 풀때 ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net lcs_1=list(map(str,input())) lcs_2=list(map(str,input())) dp = [[0]*((len(lcs_2)+1)) for _ in range(len(lcs_1)+1)] for i in range(1,len(lcs_1)+1): for j in range(1,len(lcs_2)+1): if lcs_1[i-1] == lc..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제는 삼성 sw 문제이다. 동적 계획법으로 푸는 문제인 만큼 사고가 중요한 문제이다. n = int(input()) tt = [] tp = [] for _ in range(n): T,P=map(int,input().split()) tt.append(T) tp.append(P) dp = [0 for i in range(20)] for i in range(n): #지금이 다음날보다 보상이 높다면 지금껄 그냥 간다. if dp[i] >dp[i+1] : dp[i+1] = dp[i] # dp[i+tt[i]]는 지금부터 t일후 받을 보상이..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net n = int(input()) line = [] for i in range(n): line.append(list(map(int, input().split()))) line.sort(key= lambda x : x[0] ) li = [] for i in range(len(line)): li.append(line[i][1]) li_r = list(reversed(li)) dp = [1 for i in ran..