인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

메모이제이션기법인 dp[MaxN][1<<MaxN]배열을 이용해

for문을 돌지 않음으로써 최악의 시간복잡도인 N^N을 회피하면서 최적해를 찾는방식이되는걸까요? 제가이해한게맞을런지요?

>> 네 메모이제이션은 맞는 말씀이시구 최악의 시간복잡도는 N^N이 아닌 N!이 되며 이를 다 계산하지 않고 최적해를 찾는 방법입니다.

예를 들어

1 -> 3 -> 2 -> 1과

3 -> 2 -> 1 -> 3 은 같은 의미이기 때문에 이를 이용한 것이라고 보시면 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.