인프런 커뮤니티 질문&답변
작성한 질문수
7-L 질문드립니다.
해결된 질문
작성
·
28
0
안녕하세요 7-L을 재귀적으로 푸는 아이디어가 먼저 떠올라 풀어서 통과했습니다. (인사하거나 안하거나)
https://www.acmicpc.net/source/99284102
문득 문제를 풀면서 DP의 경우, 재귀방식의 top-down이 보통 취준 코딩테스트에서 시간복잡도에는 걸리는 케이스도 있을지 궁금합니다.
퀴즈
동적 계획법(Dynamic Programming)을 적용하기 위한 주요 조건은 무엇일까요?
탐욕적 선택 속성, 최적 부분 구조
최적 부분 구조, 중복되는 부분 문제
중복되는 부분 문제, 결정론적 결과
탐욕적 선택 속성, 메모이제이션
답변 2
0
안녕하세요 ㅎㅎ
잘 하셨네요 ㅎㅎ
문득 문제를 풀면서 DP의 경우, 재귀방식의 top-down이 보통 취준 코딩테스트에서 시간복잡도에는 걸리는 케이스도 있을지 궁금합니다.
-> 드물지만 재귀호출이 너무 많을 때 for문 기반의 방식보다 시간소모가 더 커서 걸리기도 합니다.
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다. 너무어려워님.
재귀를 활용한 풀이와 동적 프로그래밍(이하 DP)의 top-down 접근 방식에 대해 궁금하신 것 같습니다.
재귀적 풀이와 top-down 방식의 DP는 문제를 해결할 때 유용한 전략긴 하지만, 코딩 테스트에서는 다음과 같은 주의 사항이 있습니다:
시간 복잡도: 재귀적 풀이가 있는 경우, 메모이제이션이 적용되지 않으면 중복 계산으로 인해 시간 복잡도가 크게 증가할 수 있습니다. 특히, 재귀 깊이가 깊어질수록 성능 문제와 스택 오버플로우를 유발할 수 있습니다. 따라서, 코딩 테스트에서는 메모이제이션과 함께 사용하여 중복 계산을 방지하는 것이 중요합니다.
스택 오버플로우: C++에서 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있으며, 이는 프로그램을 비정상 종료시킬 수 있습니다. DP의 bottom-up 방식이 이를 방지하는 데 도움을 줄 수 있습니다.
함수 호출 오버헤드: 재귀 호출의 경우 함수 호출에 대한 오버헤드가 존재할 수 있으며, 이것이 반복문을 사용하는 bottom-up 방식에 비해 느릴 수 있습니다.
관련 질문을 추가적으로 찾아보았습니다:
- 7-L 재귀적 풀이 질문있습니다. - 이 링크에서는 재귀적 풀이의 디버깅과 관련한 답변이 있어 참고하시면 좋을 것입니다.
위의 정보를 바탕으로 문제를 재귀적으로 푸는 것이 충분히 가능하지만, 메모이제이션을 활용해 중복 계산을 피하거나, 필요시에는 bottom-up 방식을 고려해 보세요.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.