본문 바로가기

dp2

[알고리즘] 다이나믹 프로그래밍(DP) 중복되는 연산을 줄이자 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 잇는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. ➡️ 연산 속도가 메모리 공간을 최대한으로 활용할 수 있는 효율적 알고리즘 작성의 필요성 ⬆️ 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 이는 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치.. 2023. 11. 28.

[DP][백준] 9095 - 1, 2, 3 더하기 + DP 에 대해서 생각해보기... dp 문제는 구현에서 애를 먹지 않는다. 그럼 dp에서 중요한 부분은 무엇이냐... 바로 아이디어와 발상이다! 그리고 제일 중요한 부분은 이 문제가 DP 문제인지 알아 차리는 것이다!!! 요즘 dp 문제를 중점적으로 풀어보고 있는데, 앞의 항과 뒤에 항의 연관성이 있는지 살펴보고 연관성이 있으면 dp문제라고 거즌 생각하고 푼다! 이렇게 앞의 항과 뒤의 항 사이에 연관성이 있는것을 점화식이 있다! 라고 나는 표현한다. 동적계획법(DP)은 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는것을 반복하는 분할정복과 비슷하다고 생각한다. 이 문제가 DP 문제라는것을 알아챈 이후에는, 이 문제의 점화식을 찾고 구현해내면된다! 구현 방법으로는 두가지가 있다. Top-down : 재귀(함수)를.. 2023. 7. 31.

이전 1 다음

티스토리툴바