본문 바로가기

알고리즘106

[백준] 15990번 : 1, 2, 3 더하기 5 – JAVA [자바] https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 방법 이 문제는 다이나믹 프로그래밍 (DP) 문제이니 DP 이론은 밑에 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming [알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 목차 다이나믹 프로그래밍이란? 다이나믹 프로그래밍 (Dynamic Programming) 또는 동적 계획법은 큰 문제를 작은 문제로 쪼개서.. 2022. 1. 26.
[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 목차 다이나믹 프로그래밍이란? 다이나믹 프로그래밍 (Dynamic Programming) 또는 동적 계획법은 큰 문제를 작은 문제로 쪼개서 푸는 기법이다. 다이나믹 프로그래밍의 특징은 모든 작은 문제들은 단 한 번만 풀어야 한다는 것이다. 한 번 푼 것을 여러 번 다시 푸는 일이 없어 비효율적인 알고리즘을 개선시키는 방법 중에 하나다. 따라서 이미 정답을 구한 작은 문제의 결과는 따로 배열에 저장하고 나주에 필요할 때 다시 사용한다. 이것을 메모이제이션 (Memoization)이라고 한다. 그리고 다시 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞에서 메모한 작은 문제의 결괏값을O(1)의 시간복잡도로 이용해서 문제를 효율적으로 풀 수가 있다. 다이나믹 프로그래밍 접근 방법 다이나믹 프로그래밍의 .. 2022. 1. 23.
반응형

티스토리툴바