DP4 [백준 10844번] 쉬운 계단 수 - Python 문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 import sys input = sys.stdin.readline n = int(input().rstrip()) d = [[0] * 10 for _ in range(n+1)] for i in range(1, 10): d[1][i] = 1 for i in range(2, n+1): for j in range(10): if j == 0: d[i][j] = d[i-1][1] elif j == 9: d[i][j] = d[i-1][8] else: d[i][j] = d[i-1][j-1] + d[i-1][j+1] print(sum(d[n]) % 1000000000) 이해하는데 .. 2024. 3. 22. [구름톤 챌린지 WEEK 3 - 탐색과 동적 프로그래밍] DAY 11. 통증 (2) 통증 문제는 아래 링크 DAY 8 참고 2023.08.21 - [구름/구름톤 챌린지] - [구름톤 챌린지 WEEK 2 - 완전 탐색] DAY 6 ~ 8 리뷰 DAY 11. 통증 (2) n = int(input()) a, b = map(int, input().split()) d = [float('inf')] * (n + 1) d[0] = 0 for i in range(2, n+1): if i - a >= 0: d[i] = min(d[i], d[i - a] + 1) if i - b >= 0: d[i] = min(d[i], d[i - b] + 1) print(-1 if d[n] == float('inf') else d[n]) 구름톤 매주 주제와 같은 유형으로 알고리즘 스터디를 진행하는데 스터디에서 풀어본 문제.. 2023. 8. 30. [백준 2156번] 포도주 시식 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 아이디어 DP 개념: 2023.08.27 - [Algorithms/이코테] - [Dynamic Programming] - 다이나믹 프로그래밍이란? / 문제 1로 만들기 # 포도주 잔의 개수 입력 받기 n = int(input()) # 포도주 list 입력 받기 + 여유 인덱스로 1 ~ n으로 맞춰주기 k = [0] + [int(input()) for _ in range(n)] + [0] .. 2023. 8. 29. [Dynamic Programming] - 다이나믹 프로그래밍이란? / 문제 1로 만들기 컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 대표적인 방법 => 다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming)이란? = 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 🌟 다이나믹 프로그래밍 사.. 2023. 8. 27. 이전 1 다음
