연습문제
📝 1-1
자신의 설계 기법을 사용하여 피보나치 수열의 항목 n을 구하는 또 다른 함수를 작성하라.
이 장의 피보나치 수열 코드와 비교하여 정확성과 성능을 평가하는 단위 테스트도 작성하라.
알고리즘 수업에서 배운 defaultdict를 사용한 바텀업 방식으로 문제를 해결한다.
1
2
3
4
5
6
7
8
from collections import defaultdict
memo:defaultdict = defaultdict(int)
memo[1] = memo[2] = 1
def fib(n:int) -> int:
for i in range(3, n + 1):
memo[i] = memo[i - 1] + memo[i - 2]
return memo[n]
피보나치 수열의 N번째 원소를 구하기 위해서는 순차 자료형에 약 N번의 값 할당이 이루어지므로 위 알고리즘은 O(N)의 선형 시간복잡도를 갖는다.
Note
행렬을 통한 접근을 사용하면 O(logN)의 로그 시간복잡도를 얻을 수 있다.
📝 1-2
파이썬 int 타입을 사용하여 단순히 비트 문자열을 표현하는 방법을 살펴봤다.
일반적으로 일련의 비트로 사용할 수 있는 int 타입 래퍼 클래스를 작성하라(순회 가능Iterable해야 하며, __getitem__() 메서드를 구현한다).
…
📝 1-3
하노이탑 문제에서 탑 수와 상관없이 작동하는 코드를 작성하라.
…
📝 1-4
일회용 암호를 사용하여 이미지를 암호화하고 복호화하라.
…