넘치게 채우기

https://leetcode.com/problems/word-break-ii/description/leetcode - Word Break II문제 유형 : 문자열 처리, 다이나믹 프로그래밍문제 난이도 : Hard 문제Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.Note that the same word in the dictionary may be reused multiple times in the segmentatio..

"이미 알고있는 답은 또 구하지 않는다" 사실 전혀 다이나믹하지 않고, 프로그래밍이라고 하기에도 애매하다. 벨만이라는 수학자가 펀딩을 잘 받기 위해서, 눈에 띄는 이름을 지은 것이다. 이광근 교수님의 저서 "컴퓨터과학이 여는 세계"에서는 '기억하며 풀기'라는 이름이 쓰였다. 하나의 큰 문제를 작은 문제로 나누어서, 그 결과를 얻고, 큰 문제의 답을 구하는 방식이다. "분할 정복법"과도 유사하다. 다이나믹 프로그래밍에는 두 가지 방법이 있다: 종류 메모이제이션 타뷸레이션 과정 하향식(Top down) 상향식(Bottom up) 구현 재귀 함수 반복문 장점 직관적이다 시간을 더 아낄 수도 있다 단점 재귀함수의 호출이 잦아 느려질 수 있다. DP테이블을 잘 채워야 한다. 기타 Lazy - Evaluation ..