728x90
반응형
배운점
1. fibonacci와 같이 재귀적으로 2개 함수의 합을 구하는 방식은 시간복잡도가 2^N이 된다.
ex) fibonacci(n-1) + fibonacci(n-2)
2. 제한적인 조건으로 초기 문제가 정의되고, 나머지 문제의 크기가 줄어드는데 초기 문제와 같은 형태가 된다면 recursion을 사용하는 것이 유리하다.
3. 26~41번 줄과 같이, 재귀함수를 쓰더라도 if문으로 분기하여 이미 구한 답은 리스트에서 꺼내오도록 하면 시간복잡도가 O(N)으로 줄어든다.
(사진 아래에 계속)
4. (기타) Combination값 구하는 함수
곱셉은 for문으로 a 까지 차례대로 곱하되,
나눗셈은 if문으로 2개로 분기하였다.
3개의 자리에 2명을 배치할 수 있는 경우의 수
보통 N C i (combination)를 구하는 것은 N개의 자리에 i개를 1개씩 배치하는 경우의 수를 의미한다. ( N > i )
ex) 3 C 2 를 도식화 하면,
[1, 1, 0], [0, 1, 1], [1, 0, 1] 의 3가지가 나온다.
728x90
반응형