728x90
BST의 최악의 경우의 예와 시간복잡도에 대해서 설명해주세요.
한쪽으로 몰리는 경우(계속해서 작은 수가 들어오는 경우, 계속해서 큰 수가 들어오는 경우)가 최악의 경우
평균적으로는 O(logN)인 시간 복잡도가 이 경우엔 O(N)으로 증가함!
피보나치 수열을 코드로 구현하는 방법에 대해서 설명해주세요.
재귀 or 동적 계획법(탑다운, 바텀업 방식이 있음)
재귀
단순한 재귀로 구현할 경우, 시간 복잡도가 너무 크게 나올 수 있기 때문에 동적 계획법을 활용하여 구현하는게 좋음 !
동적 계획법
Top-Down
말 그대로 위에서 아래로 진행하면서 답을 구하는 방식, 흔히 재귀 호출을 이용해 구현.
100번째 피보나치 수를 찾기 위해 99번째, 98번째 수를 찾고, 그들을 찾기 위해 97번쨰, 96번째 수를 찾는 방식
Bottom-Up
말 그대로 아래에서 위로 진행하면서 답을 구하는 방식, 흔히 반복문을 이용해 구현. 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있음.
1번째 수 부터 2번째, 3번째, ... 이런 식으로 수를 구해가는 방식
728x90