인프런 커뮤니티 질문&답변
작성한 질문수
7-D 질문
작성
·
6
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요! 메모이제이션을 이용하지 않으면 최악 2^30까지 간다고 생각했습니다. (이동하는 경우, 이동하지 않는 경우 두 가지). 반면 메모이제이션을 이용하면 dp 배열 사이즈만큼 탐색되구요
그런데 메모이제이션 코드가 걸리지 않는 tc가 있다면 시간초과일텐데 왜 메모이제이션이 당연히 일어난다는 전제가 있는건가요?
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. ililil님.
메모이제이션 기법은 이전에 계산된 결과를 저장하여 동일한 연산을 반복하지 않도록 함으로써 알고리즘의 효율성을 지원합니다. 이를 통해 메모이제이션은 일반적으로 시간초과를 방지하는 데 유리합니다. 하지만 몇 가지 경우에서 충분한 시간복잡도 이득을 보지 못할 수도 있습니다. 이를 이해하기 위해서는 메모이제이션이 어떻게 작동하는지에 대해 명확히 이해할 필요가 있습니다.
메모이제이션의 원리:
- 재귀 호출을 통해 동일한 서브문제가 여러 번 중복하여 계산될 가능성이 있는 문제에서, 이미 계산된 결과를 저장하여 나중에 재사용하는 방식입니다.
- 이는 특히 dp 배열이나 맵을 사용하여 각 하위 문제의 결과를 저장합니다.
- 재귀 호출을 통해 동일한 서브문제가 여러 번 중복하여 계산될 가능성이 있는 문제에서, 이미 계산된 결과를 저장하여 나중에 재사용하는 방식입니다.
시간복잡도 개선:
- 메모이제이션이 없다면, 재귀적인 호출로 인해 최악의 경우 2^30에 해당하는 시간복잡도를 가질 수 있습니다. 이는 매우 비효율적이므로, 메모이제이션을 사용하여 이를 획기적으로 줄일 수 있습니다. 저장된 결과를 빠르게 재사용함으로써, 복잡도가 dp 배열의 크기 수준으로 감소합니다.
- 메모이제이션이 없다면, 재귀적인 호출로 인해 최악의 경우 2^30에 해당하는 시간복잡도를 가질 수 있습니다. 이는 매우 비효율적이므로, 메모이제이션을 사용하여 이를 획기적으로 줄일 수 있습니다. 저장된 결과를 빠르게 재사용함으로써, 복잡도가 dp 배열의 크기 수준으로 감소합니다.
시간 초과가 발생할 경우:
- 메모이제이션이 무조건적으로 모든 상황에서 최적의 성능을 보장하는 것은 아닙니다. 초기 상태의 잘못된 설정, 비효율적인 탐색 범위 설정, 끝없는 상태 탐색 등이 문제일 수 있습니다. 이럴 경우 심도 조정, 올바른 종료 조건 설정, 더 나은 탐색 전략 등이 필요할 것입니다.
- 메모이제이션이 무조건적으로 모든 상황에서 최적의 성능을 보장하는 것은 아닙니다. 초기 상태의 잘못된 설정, 비효율적인 탐색 범위 설정, 끝없는 상태 탐색 등이 문제일 수 있습니다. 이럴 경우 심도 조정, 올바른 종료 조건 설정, 더 나은 탐색 전략 등이 필요할 것입니다.
관련 설명과 사례:
- 메모이제이션을 잘 구현하였으나 시간 초과가 발생한다면, 그것은 다른 코드의 디자인 문제일 수 있습니다.
- 이와 관련된 포럼의 기존 답변에서 추가적인 최적화 힌트를 얻을 수 있습니다.
- 메모이제이션을 잘 구현하였으나 시간 초과가 발생한다면, 그것은 다른 코드의 디자인 문제일 수 있습니다.
기존 답변을 참고하여 두 가지 경우를 토대로 추가적인 최적화와 더 깊이 있는 메모이제이션 적용 방법에 대한 정보를 갖춘 링크를 참고하시기 바랍니다.
- 7주차 개념 DP(Dynamic Programming)
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.