lmcoa15   2년 전

시간 복잡도와 관련하여 질문있습니다.

처음에 단순한 재귀 호출이라고 접근하였다가 DP로 문제를 풀게 되었는데

찾다보니 시간복잡도가 O(N^2 * M) 이라고 되어있는 것을 봤는데 제가 생각했을 때 재귀 호출이여서

O(2^n) 이라고 생각했습니다.

근데 다시 보니깐 이미 처리한 부분을 dp로 처리하고 바로 리턴하는 것을 보면서 잘못된 생각인 것은 알았지만

정확히 저 코드에서 어떤 부분이 O(N^2 * M)인지 잘모르겠습니다. 이와 비슷한 유형의 문제를 보면 시간복잡도를 생각해야 될 것같은데

이 부분이 잘 이해가 되지 않습니다.

그리고 이런 유형의 문제를 메모이제이션이라고 하는데 정확히 메모이제이션이 다이나믹 프로그래밍인지 아니면

다이나믹 프로그래밍중에서 Top-down으로 하는 것을 메모이제이션이라고 하는지 궁금합니다.

답변부탁드립니다 ㅠㅠ

kesakiyo   2년 전

dynamic programming 이란 말의 정확한 정의는 큰 문제를 여러개의 작은 문제들로 나눠서 해결하는 방법론입니다.

이에 반해 memoization 이란 한번 계산한 값을 array와 같이 접근이 용이한 곳에 저장한 뒤 필요할 때 다시 사용하는 기법입니다.

두개의 뜻이 엄연히 다르지요.

dynamic programming과 memoization은 둘 중 어떤것도 다른 것의 서브셋 개념이 아닙니다.

이 개념을 정확히 이해를 하셨다면 본인이 작성한 코드가 어떤 패턴으로 작성이 됐고 어떤 방법론을 사용해서 풀었는지 자세히 설명할 수 있을것이라 생각합니다.


시간 복잡도를 계산하는 부분 또한 훈련이 필요한 부분인데 정말 간략하게 설명을 하자면

최대 dp테이블의 크기만큼 함수호출이 일어날텐데 각각의 그 함수호출 내에서 n번만큼 for문이 돌게되니

그러한 시간복잡도가 나오는 것입니다.

lmcoa15   2년 전

dynamic programming랑 메모이제이션을 명확하게 구분해주셔서 감사합니다.

시간복잡도는 뭔가 확실이 이해가 되지는 않지만 말씀해주신게 무슨 말인지 알 것 같기도해서.. 문제를 조금 더 많이 풀어봐야 할 것 같습니다.

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.