7. 조합의 경우수(메모이제이션) (1) 썸네일형 리스트형 [인프런 자바/java] 7. 조합의 경우수(메모이제이션) _디버깅의 눈물 조합식 nCr이 의미하는 것은 n개 중에서 중복없이 r개를 뽑는 모든 경우의 수를 구하는 것이다. 예시 1의 5C3을 예로, '5개 중에서 3개를 중복없이 뽑는 경우'를 구하려면, 1)5를 무조건 포함시키고 나머지 4개 중에서 2개를 뽑는 경우(4C2), 2)5를 무조건 배제하고, 나머지 4개 중에서 3개를 뽑는 경우(4C3) 이 두 가지 경우로 나눌 수 있다. 따라서 두 가지 경우의 합(4C2 + 4C3)이 5C3이 되는 것이다. 체크 포인트 1. DFS(깊이 우선 탐색) 사용 -모든 경우의 수를 구하는 문제이기 때문에 최단 값을 구하는 BFS 대신 DFS를 사용했다. 2. DP(Dynamic Programming, 동적 계획법)의 하나인 '메모이제이션' 방법을 사용 -DFS를 통해 모든 경우의 수를 .. 이전 1 다음
