부분 문제 그리고 메모이제이션 : 다이나믹 프로그래밍 할 때 많이 나오는 데 무엇일까요?
간혹 가다가, 이런 이야기를 들으실 수 있을 거에요. 사실, 이 용어는 다이나믹 프로그래밍 뿐만이 아니라, 다른 기법에서도 종종 나오니, 고수 분들의 설명을 들으시려면, 정확한 정의는 모르셔도 됩니다. 그냥 아. 이런 거구나. 이해만 하셔도 무난합니다. 솔직하게 말해서, 시험에 나올 일도 거의 없을 겁니다. 간단한 예제를 들기 위해서, 16690번 paper Cuts 문제를 보도록 합시다. 문제를 요약하면 아래와 같습니다. str이 "abbaaddccee"이고 pat이 aaabbeeddcc입니다. 저는 str에서 칸막이 몇 개를 사용해서 잘게 쪼개려고 합니다. 위 그림에서는 "abb", "aa", "ddcc", "ee" 이렇게 쪼개졌습니다. 칸막이 u개를 써서 잘 쪼갠 문자열들을, 어떻게 잘 배치해서 p..
자료알고/알고리즘
2020. 2. 7. 22:02
최근댓글