반응형 Algorithm/Dynamic28 [동적계획법, 난이도 중] 백준 1463번 1로 만들기 첫 번째 동적계획법 문제풀이 포스팅이니, 동적계획법이 뭐하는 알고리즘인지 설명이 필요할 것이다. 동적계획법은 간단하게 말하면 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활용하는 알고리즘이다. 해답을 바로 구하는것은 그리디(탐욕) 알고리즘이다. 동적 계획법은 대부분 점화식을 요한다. 그런데 해답을 바로 구하는 것이 아니라는 말이 무슨말인가 이해가 안될 수 있다. 이번 문제가 이를 설명할 좋은 예가 될것이다. 예제 입력2 에서 입력값으로 10을 줬을 때 3이 출력되는데 아래 사진이 접근 과정이다. s배열=save배열 식을 보면 인덱스 0부터 순차적으로 계산해나가며 이전에 계산했던 값을 활용하고 있다. 다르게 말하면 입력값 10까지의 경우를 모두 계산했다는 말도 된다. 이러한 방식으로 접근하는 알.. 2020. 8. 13. 이전 1 2 3 4 다음
