[BAEKJOON]백준 1003번 피보나치 함수 문제 파이썬(Python) 풀이 - 다이나믹프로그래밍(Dynamic Programming, DP)
문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 ..
[BAEKJOON]백준 11726번 2xn 타일링 문제 파이썬(Python) 풀이 - 다이나믹프로그래밍(Dynamic Programming, DP)
문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력1 2 출력1 2 입력2 9 출력2 55 코드 from sys import stdin from collections import defaultdict class Solution: def tiling(self, n: int): if n == 1: return 1 if n == 2: return 2 dp = defaultdict(int) dp[1], dp[2] = 1, 2..
[BAEKJOON]백준 9095번 1, 2, 3 더하기 문제 파이썬(Python) 풀이 - 다이나믹 프로그래밍(DP, Dynamic Programming)
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력1 3 4 7 10 출력1 7 44 274 코드 from sys import stdin from collections import defaultdict class Solution: def sumOneTwo..
[Algorithm] 다이나믹 프로그래밍 - 0-1 배낭 문제(중복된 하위 문제들)
0-1 배낭 문제 분할 가능 배낭 문제와 달리 짐을 쪼갤 수 없는 0-1 배낭 문제를 풀이해 보자. 이 문제는 '탐욕 선택 속성'이 있는 문제가 아니며 '중복된 하위 문제들' 속성을 갖고 있으므로 다이나믹 프로그래밍으로는 풀 수 있다. 단가 순으로 그리디하게 배치해서 풀이했던 분할 가능 배낭 문제와 달리, 0-1 배낭 문제는 짐을 쪼갤 수 없다. 이 경우 모든 경우의 수를 계산해야 한다. 먼저, 입력값으로 짐을 정의하고 zero_one_knapsack() 풀이 함수를 호출한다. cargo = [ (4, 12), (2, 1), (10, 4), (1, 1), (2, 2), ] print(zero_one_knapsack(cargo)) zero_one_knapsack() 함수는 다음과 같이 정의한다. def z..
[Leetcode] 리트코드 - 피보나치 수(fibonacci-number) 파이썬(python) 풀이
문제 피보나치 수를 구하라. F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. 입력 : n = 2 출력 : 1 입력 : n = 3 출력 : 2 입력 : n = 4 출력 : 3 코드 """ fixme. https://leetcode.com/problems/fibonacci-number/ fixme. Q85. 피보나치 수 fixme. 피보나치 수를 구하라. fixme. 입력 : n = 2 fixme. 출력 : 1 """ import collections import numpy as np class Solution: def fib(self, N: int) -> int: if N int: if N int: self.dp[1] = 1 for i in range..
[Algorithm]그리디(Greedy) 알고리즘, 분할 정복, 다이나믹 프로그래밍 이란? 비교 및 분석하기 - 알고리즘 문제를 풀기전에 알아야 하는 개념(배낭 문제, 동전 바꾸기, 피보나치 수열 등)
그리디 알고리즘 그리디 알고리즘이란 바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 그리디 알고리즘이 잘 작동하는 문제들은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다. 여기서 탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다. 다시 말해 그리디 알고리즘은 선택을 다시 고려하지 않는다. 또한 최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 이렇게 탐욕 선택 속성과 최적 부분 구조의 2가지 조건을 만족하면 최적해를 찾을 수 있다. 하지..