어재는 작은 파이썬 프로젝트 인가 하는 책을 공부하려고 했는데
막상 어제 공부한것들을 오늘 돌아와서 하자니 급 하기 싫어졌다.
딥러닝이든 배포같은거든 공부하긴 해야되는데
그전에 고전 알고리즘들을 쭉 정리해봐야할거 같아 이번에는 '고전 컴퓨터 알고리즘 인 파이썬' 책을 진행하고자한다.
근데 보다보니 이거 2년전에 원서로 보다가 뉴클레오타이드인가 꾸역꾸역하다가 포기했던 그책인거같다.
재귀를 이용한 피보나치 수 계산
5번째 피보나치수는 5인데
재귀적으로 이런식으로 계산된다.
fib2(3)이 2번, fib2(2)가 3번. fib2(1)이 5번? 호출된다.
결과가 똑같은걸 계속 계산하니 비용이 크다.
일단 피보나치수는 11235라 5번째 값이 맞게 계산되긴 했다.
이번에는
메모이제이션을 이용한 피보나치 계산.
왜 메모라이제이션이 아니라 메모이제이션인지는 모르겠지만 처음 쓴사람이 이렇게 불러서 하는거같은데
이름 그대로 이미 계산한걸 또 계산하지 않고 저장해둿다가 가져와서 쓰는 방법이라한다.
7번째 피보나치 수는 13
새로 계산한 결과가 있으면 dict에 저장했다가 필요할때 꺼내서 쓰니
재귀때보다 계산량이 훨씬 줄어들었다.
뉴클레오타이드 정보 압축하여 저장하기.
전에 원서로 이 내용공부하려다가 식겁했었는데, 번역서라 좋긴좋다.
뉴클레오타이드는 유전자를 형성하는건데 A, C, G, T 네 가지 중 하나의 경우만 있다고 한다.
'A', 'C', 'G', 'T'는 아스키로 한 글자 저장하는데 1바이트, 8비트가 필요하겠지만
4 경우 뿐이므로 2비트로 저장하면 공간을 아낄수 있단다.
"AGGGGTCTA" 같은 문자열 대신
A : 00
C : 01
G : 10
T : 11
로 해서 비트 문자열로 바꾸면 공간을 훨씬 절약.
_(언더스코어 1개)로 시작하는 변수나 메소드는 private
__(언더스코어 2개)로 시작하는 것들은 네임 맹글링이며, 다른 클래스에서 접근하지 못하게 함.
실행하면 엄청 긴 문자열 오리지날 데이타가
비트스트링으로 압축해서 크기가 많이 줄어들었다.
압축 해제 후에 결과도 동일하다.
하노이탑
EBS에서도 나오고, 정말 자주 듣긴 들었는데 한번도 구현해보거나 풀어본적은 없었지만 하기 싫어도 해야지.
여기선 하노이탑, 스택을 재내릭을 사용해서 구현한다.
제네릭.. 6,7년 전쯤에 웹 개발 학원에서 자바 배울때 처음 배운 개념인데
뭐라 하나 여러 데이터를 보관하는 자료 구조에서 보관할 데이터 타입을 정의했던 내용으로 기억하고 있지만 가물가물하다.
잠깐 검색해보니 내가 알고 있던 개념이 맞는거같다. 파이썬에선 안써도 되지만 이책에서는 타입 힌트를 쓰다보니 타입 자리에 int, str 넣던거 대신 T를 넣어서 구현하네.
제네릭 프로그래밍
어떤 함수의 파라미터에 대한 타입을 지정하지 않고 상황에 따라 다양한 타입을 파라미터로 사용하는 기법이다.처음엔 '이게 무슨 말인가' 싶었는데 아래 예제를 통해 이해했다.
velog.io
일단 스택 만들고, 첫번째 탑에다가 디스크를 3개 끼워넣자.
나는 하노이탑 푸는 방법에 크게 관심이 없다보니.
대충 동작 구현하고 보면 a타워에서 c 타워로 잘 옮겨졌다.
'컴퓨터과학' 카테고리의 다른 글
| python - 4. 그래프 구현, 최소신장트리, 다익스트라 최단경로찾기 (0) | 2022.10.24 |
|---|---|
| python - 3. 선형/이진/깊이우선/너비우선 탐색, A* (0) | 2022.10.23 |
| python - 1. hello world 힘들게 만들기(WSL, 파이썬 가상환경, argparse, 린터, 파이테스트) (0) | 2022.10.20 |
| 리눅스유틸 - 2. 컴파일 도구와 ELF 포멧 (0) | 2022.07.21 |
| 리눅스유틸 - 1. 개요 (0) | 2022.07.21 |