인프런 커뮤니티 질문&답변
작성한 질문수
조합 최적화 방법이 있을까요?
작성
·
423
0
안녕하세요 강사님 좋은 강의 항상 감사드립니다!
강의를 듣고 알고리즘 연습 문제 중에 조합 문제가 나와 이번강의를 참고하게 되었는데요.
문제는 시간이 너무 많이 걸려서 시간초과 에러가 발생하게 됩니다..
예를들어
"ABCDE" 문자열 중 4개를 뽑았을 때 발생하는 모든 경우를 먼저 구해야 하는 과정이 있는데, 입력으로 받는 문자열의 길이가 길면 시간이 기하급수적으로 증가해버리게 됩니다.
이전 강의 조합수 (메모이제이션) 처럼 조합을 구할때도 시간을 단축시킬 방법이 있을까요?
답변 1
2
김태원
지식공유자
안녕하세요^^
그래서 조합을 구하는 재귀는 문자열의 길이가 30을 넘어가면 DFS로는 힘들다고 생각하고 다른 방법을 모색해야 합니다. 즉 다이나믹으로 이 문제가 해결되는제 확인해봐야 겠죠.