2ssue
commented
4 years ago 짧지만 이전 문제에서 도움을 주었던 전자 목소리 강의도 있어서 첨부해봅니다😜 SW문제 해결 기본 - Stack1
Closed Junow closed 4 years ago
2ssue
commented
4 years ago 짧지만 이전 문제에서 도움을 주었던 전자 목소리 강의도 있어서 첨부해봅니다😜 SW문제 해결 기본 - Stack1
Dynamic Programming
동적계획법의 핵심 아이디어는 기존의 값을 재활용하는 것입니다. 그렇기 때문에 반복연산을 수행하지 않아 시간복잡도 측면에서는 유리하지만 그 만큼의 추가공간을 필요로하기 때문에 공간복잡도에서는 불리 할 수 있습니다. 하지만 알고리즘 문제에서 대부분 시간복잡도가 맞냐 틀리냐를 결정짓는 요소이기 때문에 개인적으로 큰 단점은 아니라고 생각합니다.
알고리즘 테스트에서 대부분의 어려운 문제들이 복잡한 자료구조를 동반한 DP 문제인 경우가 많은것 같습니다.
문제를 작게 나누어 반복되는 구간을 특정지을 수 있는 optimal substructure 를 가지는 문제들에서 점화식을 만들어 접근하는게 일반적입니다. 물론 점화식을 생각해 내는 과정이 어렵긴 하지만 대부분 저명한 문제들을 공부하다 보면 비슷한 류의 문제가 반복되어 나오는 것을 알 수 있습니다.
algorithm visualizer 를 보시면 관련된 문제들이 있으므로 같이 공부해봅시다.
문제가 많아 보이지만 비슷한 접근법을 가진 문제들이 많습니다. 되는대로 풀어주세요. 그 외에 풀고 싶은 문제가 있다면 댓글로 추가해주시면 되겠습니다.
학습자료
문제