본문 바로가기

DP4

[Java] 알고리즘 다이나믹 프로그래밍 [Java] 알고리즘 다이나믹 프로그래밍 다이나믹 프로그래밍 큰 문제를 작은 문제로 쪼개서 앞에 저장을 하고, 해결해 나가는 것이다 피보나치 수열 예시) 1, 1, 2, 3, 5, 8, 13, 21 - 이렇게 순서대로 공식대로 계산을 하면서 문제를 해결하는 방식이 있다 (시간이 오래 걸릴 수 있다) f(1) f(2) f(3) f(4) f(5) f(6) f(7) f(8) f(9) f(10) 1 1 2 3 5 8 13 21 34 55 위와 같이 f(10) 까지 저장이 되어 있으면, f(11)을 구할 때 f(1)부터 다시 구하는 것이 아니라 f(9)와 f(10)만 찾아서 더해주면 된다 피보나치 수열을 구할 때에, 재귀를 사용할 때에는, 위와 같이 A zone과 B zone 모두 작동하게 된다 즉 B zone에.. 2023. 7. 6.
[Python] 백준 1915 가장 큰 정사각형 🧑‍💻 [Python] 백준 1915 가장 큰 정사각형 Gold 4 - DP 인덱스가 벗어나지 않는 선에서, 위, 왼쪽, 외쪽 위의 숫자들 중 min 값을 구한 다음에 1을 더해준다 코드 N, M = map(int, input().split()) matrix = [list(map(int, input())) for _ in range(N)] dp_table = [[0] * M for _ in range(N)] for i in range(N): for j in range(M): if matrix[i][j] == 1: dp_table[i][j] = 1 if 0 2023. 3. 30.
[Python] 백준 10844 쉬운 계단 수 🧑‍💻 [Python] 백준 10844 쉬운 계단 수 Silver 1 - DP 코드 N = int(input()) stairs = [[0] * 10 for _ in range(N)] for i in range(1, 10): stairs[0][i] = 1 for i in range(1, N): for j in range(10): if j == 0: stairs[i][j] = stairs[i-1][j + 1] elif 0 < j < 9: stairs[i][j] = stairs[i-1][j+1] + stairs[i-1][j-1] elif j == 9: stairs[i][j] = stairs[i-1][j-1] print(sum(stairs[N-1]) % 1000000000) 2023. 3. 24.
[Python] 백준 11726 2 x n 타일 🧑‍💻 [Python] 백준 11726 2 x n 타일 Silver 3 - DP n을 1부터 5까지 타일을 임의로 채워주다보면, 피보나치 수열이란 것을 알 수 있다 cache 리스트에 0을 1001개를 넣는다 먼저 cache[1]과 cache[2]에 1과 2를 넣어 피보나치 수열을 시작한다 for문에 피보나치 수열을 계산하는 식을 넣는다 코드 Num = int(input()) cache = [0] * 1001 cache[1], cache[2] = 1, 2 for i in range(3, 1001): cache[i] = cache[i - 1] + cache[i - 2] print(cache[Num] % 10007) 2023. 3. 22.

티스토리툴바