목록메모이제이션 (1)

개발자는 기록이 답이다

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(DFS,BFS 활용_조합의 경우수_DFS)

7. 조합의 경우수(메모이제이션) 예시 입력 1 5 3 예시 출력 1 10 예시 입력 2 33 19 예시 출력 2 818809200 강의 풀이(Time: 153ms Memory: 27MB) 먼저 nCr에 대해 이해보자 nCr : n개 중에 r개를 뽑는다는 의미이다 종이에는 지우고 썼다가 불편해서 블랙보드로 샀더니 비치는건 양해부탁드립니다.. {1,2,3,4,5}라는 배열처럼 5명의 학생이 있는데, 5번 학생을 뽑을 경우와 안뽑을 경우로 DFS를 접근하면 된다 아래처럼만 해도 nCr을 구할 수 있긴하지만, 입력값이 크다면 재귀를 많이 뻗기 때문에 오래 걸릴 것이다. 그래서 메모이제이션이 필요하다 // 메모이제이션 X import java.util.Scanner; public class Main { publ..
알고리즘/인프런 - Java알고리즘 입문 2023. 10. 5. 16:38
이전 Prev 1 Next 다음