본문 바로가기

dp6

[프로그래머스] Lv2 - 피보나치 수 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr def solution(n): dp = [0 for _ in range(n+1)] dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-2]+dp[i-1] re.. 2022. 5. 17.
[프로그래머스] Lv2 - 땅따먹기 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr def solution(land): N, M = len(land), len(land[0]) dp = [[0 for _ in range(M)] for _ in range(N)] for j in range(M): dp[0][j] = land[0][j] for i in range(1, N): for j in range(M): dp[i][j] = m.. 2022. 5. 14.
[프로그래머스] Lv2 - 가장 큰 정사각형 찾기 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr def solution(board): N, M = len(board), len(board[0]) dp = [[0 for _ in range(M)] for _ in range(N)] for i in range(N): dp[i][0] = board[i][0] for j in range(M): dp[0][j] = board[0][j] for i in range(1, N): for j in range(1, M): if board[i][j] == 1: dp[i].. 2022. 5. 14.
[프로그래머스] 고득점Kit (7) - 동적계획법 (파이썬) 1. N으로 표현 (Lv. 3) # N으로 표현 def solution(N, number): arr = [0] for i in range(1, 9): temp = make(i, N, arr) if number in temp: return i arr.append(temp) return -1 def make(i, N, arr): result = set() temp = int(str(N) * i) result.add(temp) for half in range(1, i//2+1): for x in arr[half]: for y in arr[i-half]: result.add(x+y) result.add(x-y) result.add(y-x) result.add(x*y) if y != 0: result.add(x/.. 2022. 3. 10.
[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) # 가장 긴 증가하는 부분 수열 import sys N = int(input()) arr = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(1, N): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) print(max(dp)) DP, LIS알고리즘 1. 2중 for문을 이용해서 (j < i) - dp(현재까지의 가장 긴 증가하는 부분수열의 길이)를 업데이트 해나간다 - i 까지 이전의 dp를 이용해서 업데이트 해나가고 i를 하나씩 늘려가면서 다시 해나간다 2. dp의 값중 가장 큰 값을 출력 LIS(가장 긴 증가하는 부분 수열 알고리즘) 시간복잡도.. 2022. 1. 27.
[백준] 14501번 - 퇴사 (파이썬) # 퇴사 N = int(input()) arr = [] for _ in range(N): day, pay = map(int, input().split()) arr.append((day, pay)) dp = [0] * (N+1) for i in range(N-1, -1, -1): day = arr[i][0] pay = arr[i][1] if day + i 2022. 1. 27.

티스토리툴바