Algorithm(BOJ, Python)/Dynamic Programing56 [백준_1890] 점프 python 생각보다 까다로웠다, 처음에 bfs로 풀려 했으나, 시간초과에 걸리고 말았기 때문이다. # n 입력 n = int(input()) # grid 입력 grid = [ list(map(int, input().split())) for _ in range(n) ] # dp 설계 dp = [ [0] * n for _ in range(n) ] # dp 초기설정 dp[0][0] = 1 # dp 채워넣기 for i in range(n): for j in range(n): # 맨 마지막 좌표면, if i == n-1 and j == n-1: # 출력 print(dp[i][j]) break # 오른쪽으로 이동 가능한 경우 if j + grid[i][j] < n: # 이전까지 경로 수를 더해 줌 dp[i][j + grid[.. 2022. 8. 27. [백준_2293] 동전 1 python 확실히 dp의 경우 골드와 실버 차이가, 격렬하게 느껴진다,, 풀다가 모르겠어서 구글링을 통해 아이디어를 얻었다. 이걸 어케 생각하는거지,, # n, k 입력 n, k = map(int, input().split()) # coin_list coin_list = [] # coin_list 입력 for _ in range(n): coin_list.append(int(input())) # dp 설계 dp = [ 0 for _ in range(k + 1) ] # dp 초기설정 dp[0] = 1 # dp 채워넣기 # 코인리스트에서 코인을 하나씩 꺼내서 for coin in coin_list: # dp를 돌면서 for i in range(k + 1): # 지금 위치 - 코인 값 만큼이 존재하면, if i - coi.. 2022. 8. 24. [백준_2133] 타일 채우기 python dp 를 풀었을 때 뭔가 찜찜한 느낌이 들면 그 느낌은 결코 배신하지 않는 것 같다. 각 경우마다 새로운 조합이 2개씩 생겨난다는 것을 생각치 못하였다. # dp 설계 dp = [ 0 for _ in range(31) ] # dp 초기설정 dp[2] = 3 dp[4] = 11 # dp 채워넣기 for i in range(6, 31, 2): # 두번 전의 값 * 3 dp[i] = dp[i-2] * 3 # 네번째 전, 여섯 번째 전 ,,, for j in range(4, i, 2): # 각각 2개씩 경우의수가 붙음 dp[i] += dp[i-j] * 2 # 새로운 조합 2개 나옴 dp[i] += 2 # n 입력 n = int(input()) # 출력 print(dp[n]) 2022. 8. 17. [백준_14607] 피자(Large) python 처음에 dp로 해결하려 하였으나, 그대로 냈더니 메모리초과에 걸려버렸다. 고민하다 구글링 한 결과, 숫자들을 천천히 보면 수학적으로도 바로 해결 가능함을 알 게 되었다. # n 입력 n = int(input()) # 출력 print(n * (n-1) // 2) 2022. 8. 8. [백준_1788] 피보나치 수의 확장 python 설계를 짜고 보니 f와 g가 짝수 홀수 기준으로 대칭을 이루고 있다는 사실을 발견했다. # f 설계 f = [ 0 for _ in range(1000001) ] # f 초기설정 f[0] = 0 f[1] = 1 # f 채워넣기 for i in range(2, 1000001): f[i] = (f[i-2] + f[i-1]) % 1000000000 # n 입력 n = int(input()) # n == 0 일 경우 if n == 0: print(0) print(0) # n > 0 일 경우 elif n > 0: print(1) print(f[n]) # n < 0 일 경우 else: # n이 짝수이면, if n % 2 == 0: # 음수 print(-1) # 값 출력 print(f[n * -1]) # n이 홀수이면.. 2022. 8. 7. [백준_14495] 피보나치 비스무리한 수열 python 코테 캠프가 빡센 관계로,, 오늘은 날먹,, # fib 설정 fib = [ 0 for _ in range(117) ] # fib 초기 설정 fib[1] = 1 fib[2] = 1 fib[3] = 1 # fib 채워넣기 for i in range(4, 117): fib[i] = fib[i-3] + fib[i-1] # n 입력 n = int(input()) # 출력 print(fib[n]) 2022. 8. 6. [백준_15624] 피보나치 수 7 python n == 0일 경우를 따로 처리해 주지 않으면, dp길이가 맞이 않아 런타임 에러에 빠진다. # n 입력 n = int(input()) # n = 0 일 경우 if n == 0: print(0) # n >= 1 일 경우 else: # dp 설계 dp = [ 0 for _ in range(n + 1) ] # dp 초기설정 dp[0] = 0 dp[1] = 1 # dp 채워넣기 for i in range(2, n+1): dp[i] = (dp[i-2] + dp[i-1]) % 1000000007 # 출력 print(dp[n]) 2022. 8. 5. [백준_15991] 1,2,3 더하기 6 python 규칙 찾는데 진짜 시간 오래걸린다 이런문제는 개인적으로 이런류는 그냥 무지성 냅다 n = 10 까지 지르고 그리고 어거지로 규칙 찾는게 답인 듯 하다. # dp 설계 dp = [ 0 for _ in range(100001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 dp[3] = 2 dp[4] = 3 dp[5] = 3 dp[6] = 6 # dp 채워넣기 for i in range(7, 100001): dp[i] = (dp[i-2] + dp[i-4] + dp[i-6]) % 1000000009 # t 입력 t = int(input()) for _ in range(t): # n 입력 n = int(input()) # 출력 print(dp[n] % 1000000009) 2022. 8. 1. [백준_4883] 삼각 그래프 python dp자체보다 입력 형식, 그리고 무엇보다 비용이 음수일수도 있다는 점을 주의해야 하는 문제였다. 따라서 각 dp 칸에 오는 모든 경우의 수를 고려하여 점화식을 세워야 한다. # k 설정 k = 0 while True: # n 입력 n = int(input()) # 만약 n이 0이라면, if n == 0: # 테스트 종료 break # n이 0이 아니라면, 진행 else: # 테스트 번호 부여 k += 1 # grid 설계 grid = [ list(map(int, input().split())) for _ in range(n) ] # dp 설계 dp = [ [0] * 3 for _ in range(n) ] # dp 초기설정 dp[0][1] = grid[0][1] dp[0][2] = dp[0][1] + gr.. 2022. 7. 30. [백준_9711] 피보나치 python 미안 오늘까지만 좀 쉬자 그래도 문자열 포매팅 하나는 복습하고 갈 수 있는 문제잖아? # fib 설계 fib = [ 0 for _ in range(10001) ] # fib 초기설정 fib[1] = 1 fib[2] = 1 # fib 채워넣기 for i in range(3, 10001): fib[i] = fib[i-2] + fib[i-1] # t 입력 t = int(input()) # 출력 for i in range(1, t+1): p, q = map(int, input().split()) print('Case #%d: %d'%(i, fib[p] % q)) 2022. 7. 29. [백준_1793] 타일링 python 문제는 쉽다. 근데 처음 보는 입력 형식에서 당황했다. 그리고 n=0일때 0가지 아닌가,,,? 1가지로 풀어야 한단다,, 그리고 try except 안써주면 런타임 에러 뜬다. # dp 설계 dp = [ 0 for _ in range(251) ] # dp 초기설정 dp[0] = 1 dp[1] = 1 dp[2] = 3 # dp 채워넣기 for i in range(3, 251): dp[i] = dp[i-2] * 2 + dp[i-1] while True: try: # n 입력 n = int(input()) # 출력 print(dp[n]) except: break 2022. 7. 28. [백준_8394] 악수 python 천천히 세어보면 어렵지 않게 피보나치 라는 것을 알 수 있다. # dp 설계 dp = [ 0 for _ in range(10000001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 # dp 채워넣기 for i in range(3, 10000001): dp[i] = ((dp[i-2] % 10) + (dp[i-1] % 10))% 10 # n 입력 n = int(input()) # 출력 print(dp[n]) 2022. 7. 27. [백준_17175] 피보나치는 지겨웡~ python 시간이 없어서 급하게 풀다가 자기 자신의 호출 횟수 1을 더해줘야 한다는 것을 까먹었다. f(i) = f(i-2) + f(i-1) + 1이다 # fib 설계 fib = [ 0 for _ in range(51) ] # fib 초기설정 fib[0] = 1 fib[1] = 1 fib[2] = 3 fib[3] = 5 # fib 채워넣기 for i in range(4, 51): fib[i] = fib[i-2] + fib[i-1] + 1 # n 입력 n = int(input()) # 출력 print(fib[n] % 1000000007) 2022. 7. 26. [백준_9507] Generation of Tribbles python 거 너무 문제 꽁으로 먹는거 아니오 라고 나도 생각하지만, 이번주는 좀 봐줘라,, 못해먹겠다 기본적인 dp의 메모이제이션 개념만 알고 있다면 쉽게 해결할 수 있다. # koong 설계 koong = [ 0 for i in range(68) ] # koong 초기설정 koong[0] = 1 koong[1] = 1 koong[2] = 2 koong[3] = 4 # koong 채워넣기 for i in range(4, 68): koong[i] = koong[i-1] + koong[i-2] + koong[i-3] + koong[i-4] # t 입력 t = int(input()) for _ in range(t): # n 입력 n = int(input()) # 출력 print(koong[n]) 2022. 7. 25. [백준_9658] 돌게임 4 python 처음에 or 개념으로 조건을 생각했다가, 다 상근이가 이겨버리는 말도안되는 결과가 도출되었다. 돌게임 시리즈 생각보다 어렵다. # n 입력 n = int(input()) # dp 입력 dp = [ 0 for _ in range(1001) ] # dp 초기설정 dp[1] = 0 dp[2] = 1 dp[3] = 0 dp[4] = 1 # dp 채워넣기 for i in range(5, 1001): if dp[i-1] and dp[i-3] and dp[i-4]: dp[i] = 0 else: dp[i] = 1 # 출력 if dp[n]: print('SK') else: print('CY') 2022. 7. 24. [백준_17216] 가장 큰 감소하는 부분수열 python 이런 류의 문제에 이젠 익숙해진 기분이다. 마찬가지로 n의 범위가 1000이하이니 n^2까지의 시간복잡도는 인정해준다. # n 입력 n = int(input()) # a 입력 a = list(map(int, input().split())) # dp 설계 dp = [ 0 for _ in range(n) ] # dp 초기설정 dp[0] = a[0] # dp 채워넣기 for i in range(1, n): # 최댓값 설정 M = 0 # 이전까지 돌면서 for j in range(i): # 감소하는 수열 중 dp값이 가장 큰 것을 찾아 if a[j] > a[i] and dp[j] > M: # 최댓값 갱신 M = dp[j] # dp 넣어주기 dp[i] = M + a[i] # 출력 print(max(dp)) 2022. 7. 23. [백준_2491] 수열 python 어제 과음한 관계로 오늘은 쉬운문제를,, # n 입력 n = int(input()) # n_list 입력 n_list = list(map(int, input().split())) # dp1 (연속해서 같거나 커지는 최댓값 구하기 위한 dp) dp1 = [ 0 for _ in range(n) ] # dp1 초기설정 dp1[0] = 1 # dp1 채워넣기 for i in range(1, n): # n_list[i] 가 n_list[i-1]보다 크거나 같으면, if n_list[i] >= n_list[i-1]: # 전 dp + 1 dp1[i] = dp1[i-1] + 1 # 작으면 else: # 1로 초기화 dp1[i] = 1 # dp2 (연속해서 같거나 작아지는 최댓값 구하기 위한 dp) dp2 = [ 0 f.. 2022. 7. 22. [백준_11660] 구간 합 구하기 5 python grid 굳이 저렇게 받지 않아도 된다. 입력 어케해야 저렇게 앞에 0을 넣을 수 있을까 고민해봤는데 굳이 그럴 필요가 없었다. dp만 그렇게 만들어주면 된다. # 입력 속도 개선 import sys input = sys.stdin.readline # n, m 입력 n, m = map(int, input().split()) # grid grid = [ list(map(int, input().split())) for _ in range(n) ] # dp 설계 dp = [ [0] * (n+1) for _ in range(n+1) ] # dp채워넣기 for i in range(1, n+1): for j in range(1, n+1): dp[i][j] = dp[i][j-1] + grid[i-1][j-1] # x.. 2022. 7. 21. 이전 1 2 3 4 다음
