본문 바로가기

전체 글

 (638)
[다이나믹 프로그래밍] 바닥 공사 - 파이썬(python) 바닥 공사 난이도 : 中下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) d = [0] * 1001 d[0] = 0 d[1] = 1 d[2] = 3 for i in range(3, n+1): d[i] = (d[i-1] + d[i-2]*2) % 796796 print(d[n]) 예시 # 정수 N을 입력 받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업) d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796 ..
[다이나믹 프로그래밍] 개미 전사 - 파이썬(python) 개미 전사 난이도 : 中 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) array = list(map(int, input().split())) d = [0] * 100 d[0] = array[0] d[1] = max(d[0], array[1]) for i in range(2, n): d[i] = max(d[i-1], d[i-2] + array[i]) print(d[n-1]) 예시 # 정수 N을 입력 받기 n = int(input()) # 모든 식량 정보 입력 받기 array = list(map(int, input().split())) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 # 다이나믹 프로그래밍(Dyna..
[다이나믹 프로그래밍] 1로 만들기 - 파이썬(python) 1로 만들기 난이도 : 中下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 x = int(input()) dp = [0] * 30001 for i in range(2 , x+1): dp[i] = dp[i-1] + 1 if i % 2 == 0: dp[i] = dp[i//2] + 1 if i % 3 == 0: dp[i] = dp[i//3] + 1 if i % 5 == 0: dp[i] = dp[i//5] + 1 print(d[x]) 예시 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1000001 # 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) for i in range(..
[다이나믹 프로그래밍] 다이나믹 프로그래밍 다이나믹 프로그래밍 - 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 - 탑다운과 바텀업 2가지 방식, 메모이제이션 기법이 있음 - 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식 - 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 문제들의 중복 여부를 확인 - 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤 (탑다운 방식) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션 기법을 적용할 수 있으면 코드를 개선 다이나믹 프로그래밍을 사용 가능한 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 ..
[이진 탐색 알고리즘] 떡볶이 떡 만들기 - 파이썬(python) 떡볶이 떡 만들기 난이도 : 中 풀이 시간 : 40분 시간 제한 : 2초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) array = list(map(int, input().split())) start, end = 0, max(array) while(start mid: total = total + (i - mid) if total < m: end = mid - 1 else: result = mid start = mid + 1 print(result) 예시 # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력 n, m = list(map(int, input().split(' '))) # 각 떡의 개별 높이 정보를 입력 array = list(map(int, in..

티스토리툴바