파이썬 알고리즘 - 1 작은 문제들

파이썬 알고리즘 첫 번째로

 

다른 재귀적인 함수들을 사용하지 않는

 

간단한 문제 푸는 방법들을 살펴보겠습니다.

 

 

1.1 피보나치 수열 fiboncci sequence

 피보나치 수열은 첫쩨 둘째를 제외하고 그 이전의 두 수를 합한 수들의 열로

 

0, 1, 1, 2, 3, 5, ... 

 

와 같습니다.

 

피보나치 수열의 첫번째 값은 0이되고, 4번째 피보나치 수는 2가 됩니다.

 

n 번째 피보나치 수에 대한 공식으로 다음과 같이 정리할수 있습니다.

 

fib(n) = fib(n-1) + fib(n - 2)

 

1.1.1 첫번째 재귀

# file name : fib1.py

def fib1(n):
    return fib1(n - 1) + fib1(n-2)

if __name__ == "__main__":
    print(fib1(5))

 

이 경우 fib1은 한번 호출되면 끊임없이 무한하게 자기자신을 호출해서 무한 루프에 빠지게 됩니다.

 

 

1.1.2 베이스 케이스 base case 활용

 

여기서 무한 루프, 무한 재귀에 빠지는걸 막으려면 베이스 케이스를 지정해주면 되는데

 

베이스 케이스는 멈출 지점이 됩니다.

 

여기서 n이 0과 1인 경우는 자기 자신을 반환해주면 되므로

# file name : fib1.py

def fib2(n):
    if n < 2 : #base case
        return n
    return fib2(n - 1) + fib2(n - 2) #recursive case

if __name__ == "__main__":
    for i in range(10):
        print(fib2(i))

 

반복문으로 첫번째에서 10번째 피보나치 수들을 출력하면 아래와 같습니다.

 

* 주의사항

여기서 50번째 피보나치 수를 출력하지는 마세요

 

5번째 피보나치 수를 출력하기 위해서 fib2함수가 15번 호출되고

 

10번째 피보나치 수를 출력하는데는 fib함수가 177번 호출됩니다.

 

20번째의 경우 21,891번으로 점점 커지게 됩니다.

 

다음은 fib2 를 약간 수정하여 fib2 함수가 몇번 호출되는치 출력하도록 수정하였습니다.

# file name : fib2_cnt.py

call_cnt = 0

def fib2(n):
    global call_cnt
    call_cnt = call_cnt + 1
    if n < 2 : #base case
        return n
    return fib2(n - 1) + fib2(n - 2) #recursive case

if __name__ == "__main__":
    for i in range(11):
        call_cnt = 0
        print(" i - ",i, " : ", fib2(i), "  - call_cnt : ", call_cnt)

 

 

 

1.1.3 재귀 대신 기억하기

 기억은 계산작업이 끝날때 까지 계산 결과를 저장해놓는 것으로 재귀에서 이전의 결과를 구하기 위해 수많은 계산을 했던것 대신 필요한 값들을 저장해놓고 찾아서 사용하면 됩니다.

 

 이번에는 값을 기억하도록 딕셔너리를 써서 구현해보겠습니다.

 

#file_name : fib3.py

memo = {0:0 , 1:1} #base case

def fib3(n):
    if n not in memo:
        memo[n] = fib3(n - 1) + fib3(n - 2) # memorization
    return memo[n]

if __name__ == "__main__":
    print(fib3(5))
    print(fib3(10))
    print(fib3(50))

 

1.2 단순 압축

 공간 절약은 보통 중요합니다. 데이터가 더 작은 공간을 차지하도록 하는 기술이 압축 compression이고, 이 압축된 데이터를 원래대로 되돌리는것을 압축풀기 decompression이라 합니다.

 

 초기 데이터 압축에서는 데이터 저장소가 사용하는 비트 수을 따라왔는데요.

 

64비트 컴퓨터에서 unsigned integer는 65,535를 초과하는 수를 저장할수 없으며, 이는 매우 비효율적입니다.

 

하지만 16비트 unsigned integer에서는 남는 공간을 다 채울수 있어서

 

unsigned integer를 사용하는 경우 64비트 보다 16비트에서 75%정도 공간낭비를 줄일수 있습니다.

 

 이번에 sys.getsizeof() 함수로 객체가 얼마나 메모리 공간을 차지하고 있는지 확인해 볼것이고

 

DNA에서 유전자를 구성하는 뉴클레오 타이드를 가지고 살펴보겠습니다.

 

뉴클레오 타이드는 A, C, G, T 이 4가지 값 중 하나만 가질수 있는데요

 

 

"ATG" 라는 유니코드 문자열이 있는 경우

 

한 글자에 8비트로 총 24비트 공간을 차지하는 문자열이 됩니다.

 

하지만 뉴클레오 타이드의 경우에 수는 4가지 뿐이므로

 

8비트 대신 2비트로 다음과 같이 비트 문자열에다 저장하면 75%정도 더 절약할수 있겠습니다.

 

즉, 하나의 뉴클레오 타이드를 2비트로 나타낼수 있겠습니다.

00	A
01	C
10	G
11	T

 

이제 압축된 유전자 클래스를 만들어서

 

압축 함수와 압축 해제 함수 등을 구현해서

 

뉴클레오 타이드 문자열을 압축해보고, 압축해제를 해보겠습니다.

 

* 주의사항

_compress()는 언더스코어로 시작하는 함수인데

파이썬에서는 private 함수 같은 제한이 없어서

외부에서 호출하면 안되는 함수들은 앞에 언더스코어 _를 붙여주겠습니다.

 

from sys import getsizeof
# file_name : trivial_compression.py
class CompressedGene:

    def __init__(self, gene):
        self._compress(gene)

    def _compress(self, gene):
        self.bit_string = 1
        for nucleotide in gene.upper():
            #print(nucleotide)
            #print("bit_str : ", bin(self.bit_string))
            # 비트 문자열에 압축한 값을 넣기 전에 기존의 비트문자열을 2번 시프트
            self.bit_string <<= 2
            # 문자 A가 오면 00, C가 오면 01 등으로 비트문자열에 저장
            if nucleotide == "A":
                self.bit_string |= 0b00
            elif nucleotide == "C":
                self.bit_string |= 0b01
            elif nucleotide == "G":
                self.bit_string |= 0b10
            elif nucleotide == "T":
                self.bit_string |= 0b11
            else:
                raise ValueError("Invalid Nucleotide: {}".format(nucleotide))

    def decompress(self):
        gene = ""
        for i in range(0, self.bit_string.bit_length() - 1, 2):
            bits = self.bit_string >> i & 0b11
            if bits == 0b00:
                gene += "A"
            elif bits == 0b01:
                gene += "C"
            elif bits == 0b10:
                gene += "G"
            elif bits == 0b11:
                gene += "T"
            else:
                raise ValueError("Invalid bits:{}".format(bits))
        return gene[::-1] # 문자열을 역순으로 반환

    # CompressGene의 문자열 반환값
    def __str__(self):
        return self.decompress()

if __name__ == "__main__":
    original = "TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATA" * 100
    compressed = CompressedGene(original)
    #print(compressed)
    print("original is {} bytes".format(getsizeof(original)))
    print("compressed is {} bytes".format(getsizeof(compressed.bit_string)))
    print("original and decompressed are the same : {}". format(original == compressed.decompress()))

압축전에 6549 바이트 던 문자열이

 

비트 문자열로 압축후에 1760바이트로 크게 줄었습니다.

 

압축 해제후 둘다 동일한 결과가 나온걸 확인했고

 

압축 해제후 결과를 보려면 주석문만 지워주시면 되겠습니다.