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

안녕하세요 ㅎㅎ

잘 하셨네요 ㅎㅎ

문득 문제를 풀면서 DP의 경우, 재귀방식의 top-down이 보통 취준 코딩테스트에서 시간복잡도에는 걸리는 케이스도 있을지 궁금합니다.

-> 드물지만 재귀호출이 너무 많을 때 for문 기반의 방식보다 시간소모가 더 커서 걸리기도 합니다.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. 너무어려워님.

재귀를 활용한 풀이와 동적 프로그래밍(이하 DP)의 top-down 접근 방식에 대해 궁금하신 것 같습니다.

재귀적 풀이와 top-down 방식의 DP는 문제를 해결할 때 유용한 전략긴 하지만, 코딩 테스트에서는 다음과 같은 주의 사항이 있습니다:

1. 시간 복잡도: 재귀적 풀이가 있는 경우, 메모이제이션이 적용되지 않으면 중복 계산으로 인해 시간 복잡도가 크게 증가할 수 있습니다. 특히, 재귀 깊이가 깊어질수록 성능 문제와 스택 오버플로우를 유발할 수 있습니다. 따라서, 코딩 테스트에서는 메모이제이션과 함께 사용하여 중복 계산을 방지하는 것이 중요합니다.

2. 스택 오버플로우: C++에서 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있으며, 이는 프로그램을 비정상 종료시킬 수 있습니다. DP의 bottom-up 방식이 이를 방지하는 데 도움을 줄 수 있습니다.

3. 함수 호출 오버헤드: 재귀 호출의 경우 함수 호출에 대한 오버헤드가 존재할 수 있으며, 이것이 반복문을 사용하는 bottom-up 방식에 비해 느릴 수 있습니다.

관련 질문을 추가적으로 찾아보았습니다:

• 7-L 재귀적 풀이 질문있습니다. - 이 링크에서는 재귀적 풀이의 디버깅과 관련한 답변이 있어 참고하시면 좋을 것입니다.
  

위의 정보를 바탕으로 문제를 재귀적으로 푸는 것이 충분히 가능하지만, 메모이제이션을 활용해 중복 계산을 피하거나, 필요시에는 bottom-up 방식을 고려해 보세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.