Python Algorithm Chapter1
Python Algorithm
1. 피보나치 수열
피보나치 수열이란, 처음 0, 1을 제외하고 그 뒤 수는 앞의 두 수를 더해서 만든 수로 이루어진 수열이다.
fib(n) = fib(n-1) + fib(n-2)
1.1 재귀함수
재귀 함수를 통해 구현하여 보자
fib() 함수를 위의 수식으로 구현하고, fib(n)을 호출하면 무한 재귀가 발생한다.
1.2 기저 조건
무한 재귀가 발생하는 이유는 계속 재귀를 하기 때문에 재귀가 멈춰지는 부분이 필요한 것이다. 그것을 기저 조건이라고 한다.
즉, 처음의 수 0과 1을 선언해 주어서 재귀를 멈추는 부분이 필요하다.
1.3 메모이제이션
숫자가 커질수록 fib() 함수를 재귀 호출 하는 수가 기하 급수적으로 증가하여 호출하므로 효율성이 떨어진다.
그러므로 이미 계산한 결과는 저장하여 기억하는 기술을 사용할 수 있다. 그 것을 메모이제이션이라고 한다.
즉, n번째에 피보나치 수열의 수를 찾을 때, 먼저 계산한 적이 있는지 확인해보고, 없다면 계산하도록 한다.
1.4 메모이제이션 데커레이터
파이썬에서 자동으로 메모이징하는 내장형 데커레이터를 사용한다.
@functools.lru_cache()데커레이터를 사용한다.
즉, 호출된 함수의 결과값을 메모리에 캐싱(저장)한다.
1.5 반복문 사용
재귀 함수를 사용하지 않고, for 반복문을 이용할수 있다.
- 기저 조건으로 0, 1을 선언해준다.
last, next = next, last+next를 이용하여 다음 순서의 숫자들을 찾아나간다.
n-1번의 반복문만 사용되면 되므로 재귀함수로 해결하는 것보다 훨씬 효율적이다.
- 단순 재귀 : 상향식이며, 직관적이라는 장점
- 반복문 : 하향식이며, 성능적으로 효율적
모든 재귀적으로 해결할 수 있는 문제는 반복문으로 해결할 수 있다.
1.6 제너레이터
해당 번째의 숫자를 구하는 것말고, 그까지의 순열 전체를 구하려면 제너레이터를 이용할 수 있다.
yield문으로 계속 반환시키는 것이다.
2. 압축 알고리즘
저장 공간을 절약하기 위해 데이터를 인코딩(데이터 형식 변경)하는 것, 압축 풀기는 반대의 과정, 디코딩(원래 형식으로 데이터를 되돌림)
시간과 공간 사이의 트레이드 오프가 있다. 데이터를 원래대로 되돌리는데 시간이 걸린다.
빠른 데이터 실행 < 저장 공간의 효율성인 상황에서 유의미
예를 들어 65,635보다 작은 부호가 없는 정수는 64비트 부호 없는 정수로 저장되면 비효율적이다.
16비트의 부호 없는 정수로도 충분히 저장 될 수 있기 때문이다.
이는 저장 공간의 75%를 줄이는 셈이다.
2.1 유전자 예제
A,C,G,T의 뉴클레오 타이드는 각각 문자열이기 때문에 8비트의 저장공간을 차지한다.
이를 2진수의 숫자로 대체하면 2비트로 00,01,10, 11로 저장하여 저장 공간을 절약할 수 있다.
- 8비트가 2비트가 되므로
75%공간 절약
압축 : 8비트 문자(A,C,G,T) -> 비트문자열(00, 01, 10, 11)
압축 해제 : 비트문자열(00, 01, 10, 11) -> 8비트 문자(A,C,G,T)
압축할 때는 비트를 왼쪽으로 쉬프트 시키면서 if문으로 문자를 비교하여 해당 비트 문자열을 추가하는 방식으로 이루어집니다.
압축 해제 할 때는 반대로 마지막에서부터 비트 문자열을 문자로 읽어오는 과정을 이용하여 마지막에 뒤집어서 다시 추출해냅니다.
3.암호화
깨지지않는 일회용 암호(OTP)
-
원본데이터 + 더미 데이터 --XOR(암호화)--> 프로덕트 키 -
프로덕트 키 + 더미 데이터 --XOR(복호화)--> 원본데이터
즉, 원본 데이터에 더미 데이터를 이용하여 암호화를 하는 방식이다.
다시 원본 데이터를 찾기 위해서는 다시 더미데이터와 우리가 암호화 시킨 결과 두개가 모두 있어야합니다.
모든 데이터는 바이트의 데이터를 비트 문자열 정수로 바꾸어서 진행됩니다.
암호화 하기 위해서는 먼저, 원본데이터를 비트 문자열로 바꾸고, 랜덤으로 생성된 더미 데이터도 비트 문자열 정수로 바꿉니다.
그리고 두개를 XOR 연산을 시킵니다. XOR 연산은
- 피연사자 중 하나만
TRUE일때,TRUE반환 - 피연사자 모두
TRUE거나FALSE이면,FALSE반환
이 XOR 연산의 유용한 속성은 연산 결과를 다시 피연산자 중 하나와 연산을 하면 다른 피연산자가 결과로 나온다는 것입니다. 즉,
피연산자1 XOR 피연산자2 = 키일 경우키 XOR 피연산자1 = 피연산자2키 XOR 피연산자2 = 피연산자1
즉, 다시 원래 값을 복호화하여 찾아야하는 암호화 문제에 사용될 수 있다는 것입니다.
즉, 이것을 다시 생각해보면 우리가 암호화 한 키를 다시 더미데이터와 XOR 연산을 시키면 원본 데이터를 구할 수 있다는 말이 됩니다.
예를 들어 1111이라는 원본데이터와 0101이라는 더미 데이터가 있다고 하면
- XOR 연산을 하여 구한
키 : 1010 - 다시 더미데이터와 XOR 연산하면
원본데이터 : 1111을 구할 수 있습니다.
4. 파이 계산
파이를 구하는 것을 기계변환(수식을 코드로)하여 보자
파이는 무한 급수의 합으로 표현할 수 있다.
파이 = 4/1 - 4/3 + 4/5 - 4/7 +4/9 - 4/11...
특징을 보면
- 분자는 4로 유지
- 분모는 2씩 증가
- 빼기와 더하기가 번갈아 사용
즉, for문을 통해 합계를 누적시켜 구현시킬 수 있다.
5. 하노이 탑
디스크를 다른 탑으로 이동시키자.
규칙
- 한번에 하나의 디스크만 이동 가능
- 제일 위의 디스크만 이동 가능
- 큰 디스크는 작은 디스크 위로 이동 불가능
각각의 탑을 Stack 자료구조로 표현할 수 있다.(후입선출(LIFO))
- 푸쉬 : 새 항목을 스택에 넣는 것
- 팝 : 스택에 마지막으로 넣은 항목 제거 후 반환
해결하는 방법은 기저 조건과 재귀 조건을 나누어 볼 수 있다.
- 기저 조건 : 하나의 디스크를 이동하는 것
- 재귀 조건 : 나머지 디스크를 나머지 탑에 임시 이동
즉, 나머지를 임시 이동하고 하나 옮기고 또 남은 것들로 그것을 반복하면 되는 일이다.
코드를 짤 때
- n-1개를 임시탑 이동
- 1개를 최종탑으로 이동
하는 것을 재귀함수를 통해 구현하면 되는 것이다.
마찬가지로 재귀를 통해 해결하므로 디스크 수의 증가에 따라 함수 호출도 기하 급수적이다.
6. 적용
- 재귀 : 함수형 프로그래밍에 많이 사용 -
재귀 문제는 반복문으로 해결가능 - 메모이제이션 : 파서의 속도 향상, 언어 런타임 (최근 계산 결과 다시 사용할 가능성 있는 문제에 유용)
- 압축 : 인터넷 대역폭 사용가능, 값의 수가 제한된 간단한 데이터 타입에 유용, 실전에서는 배운것보다 더 복잡한 방법 사용
- 암호화(비트조작) : 일반적인 암호화에는 일회용 암호는 부적합