백준2 백준 1003번 문제 (다이나믹 프로그래밍) python 이중 배열 요즘 다이나믹 프로그래밍 완벽 숙지를 위해 매일 하나씩 풀고 있습니다. 백준 1003번 문제는 이중 배열을 이용하여 풀었는데요. 이중 배열을 대입 연산자를 이용하여 변경할 때 꼭 알아야 하는 내용이 있어 같이 들고 왔습니다. 문제 1003번 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 피보나치수열의 응용문제인데 당연히 다이나믹 프로그래밍으로 해결이 가능하다. 문제를 보면 fibonacci(1), fibonacci(0) 일 때 각각 1과 0을 리턴한다. 그렇다면 fibonacci(2) 일 때는 fibonacci(1) + fibonacci(.. 2022. 11. 2. 다이나믹 프로그래밍(동적 계획법) ex)백준 2839번 -python 다이나믹 프로그래밍 dynamic programming, DP 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘에 유리 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 예로 피보나치 수열, 점화식, 최단 경로 문제, 행렬의 제곱 문제 등 최적화에 사용 이미 계산한 결과를 별도의 메모리에 저장하여 다시 계산하지 않아 수행시간 효율이 좋다. ex) 피보나치 function fib(n): if n = 0: return 0 elif n = 1: return 1 else: return fib(n - 1) + fib(n - 2) 재귀함.. 2022. 10. 28. 이전 1 다음