[파이썬(Python)] 자료 구조와 알고리즘(1)

자료 구조와 알고리즘(1)

• 이 포스팅은 Python Cookbook의 내용을 요약하여 작성되었습니다.
• 지적, 질문은 언제나 환영합니다.

 

1.1 시퀀스를 개별 변수로 나누기

---

모든 시퀀스(혹은 이터레이팅 가능한 것)는 할당문을 통해서 개별 변수로 나눌 수 있다. 단, 변수의 개수가 시퀀스에 일치해야 한다. 그렇지 않으면 에러가 발생한다. 시퀀스를 개별 변수로 나누는 것을 언패킹(unpacking)이라고 하는데, 이는 순환 가능한 모든 객체(튜플, 리스트, 문자열, 파일, iterator, generator 등)에 적용할 수 있다. 다만 특정 값을 제외하는 방법은 따로 없다. 만약 어떤 값은 버리고 싶다면, 그 값에 해당하는 변수 이름을 버리는 것으로 이해할 수 있도록 붙여 주는 수밖에 없다. 책에서는 _(언더바) 혹은 ign(ignored)를 추천한다.

 

>>> p = (4, 5)
>>> x, y = p
>>> x
4
>>> y
5

 

1.2 임의 순환체의 요소 나누기

---

순환체를 언패킹할 때 요소가 아주 많이 포함되어 있다고 가정해 보자. 일일히 변수를 적으려면 무척 귀찮을 것이다. 아니면 반복문을 작성해야 한다. 하지만 파이썬에는 더 간단한 방법이 있다. "별 표현식"을 사용하는 것이다. "*"이 붙은 변수는 여러 요소를 가질 수 있는 변수라고 생각하면 된다. 별 표현식의 위치는 어디든 상관없다.

 

>>> record = ('Dev', 'dev@gmail.com', '123-456-789', '02-999-9999')
>>> nickname, email, phone_number = record
>>> name
'Dev'
>>> email
'dev@gmail.com'
>>> phone_number
['123-456-789', '02-999-9999']

 

이는 길이를 알 수 없는 순환체에서 편리하게 쓰일 수 있다.

 

records = [
    ('foo', 1, 2),
    ('bar', 'hi'),
    ('foo', 3, 4),
]

def do_foo(x, y):
    print('foo', x, y)

def do_bar(s):
    print('bar', s)

for tag, *args in records:
    if tag == 'foo':
        do_foo(*args)
    elif tag == 'bar':
        do_bar(*args)

 

1.3 마지막 N개 아이템 유지

---

순환이나 프로세싱 중 마지막 N개의 요소를 얻고 싶다면 collections.deque를 사용할 수 있다. 다음의 코드는 여러 줄에 대해서 간단한 텍스트 매칭을 수행하고 처음으로 발견한 N라인을 찾는다. deque(maxlen=N)은 고정 크기 큐를 생성한다. 큐가 꽉 찬 상태에서 삽입이 이루어지면 가장 먼저 삽입된 아이템이 자동으로 삭제된다. 최대 크기를 지정하지 않으면 제약 없이 양쪽에 아이템을 넣거나 뺄 수 있다.

 

from collections import deque

def search(lines, pattern, history=5):
    previous_lines = deque(maxlen=history)
    for line in lines:
        if pattern in line:
            yield line, previous_lines
        previous_lines.append(line)

# 파일 사용 예

if __name__ == '__main__':
    with open('file.txt') as f:
        for line, prevlines in search(f, 'python', 5):
            for pline in prevlines:
                print(pline, end='')
            print(line, end='')
            print('-'*20)

 

1.4 N 아이템의 최대 혹은 최소값 찾기

---

컬렉션 내부에서 가장 크거나 작은 N개의 아이템을 찾을 때, heapq 모듈의 nlargest()와 nsmallest()를 사용할 수 있다. 이들은 내부적으로는 데이터를 힙(min heap)으로 정렬시켜 놓는 리스트로 변환한다.

 

import heapq

nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # prints [-4, 1, 2]

# 두 함수 모두 좀 더 복잡한 구조에 사용하기 쉽도록 키 파라미터를 받는다.
portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]

cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

 

1.5 우선순위 큐 구현

---

주어진 우선 순위에 따라 아이템을 정렬하는 큐를 구현하고 항상 우선 순위가 가장 높은 아이템부터 삭제되도록 만들어야 한다. heapq 모듈을 이용해 구현할 수 있다. index 변수는 우선 순위가 동일한 아이템의 순서를 정할 때 사용된다. 우선 순위는 같을 수 있어도 index는 같을 수 없기 때문이다.

 

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

 

이를 사용하는 예제는 다음과 같다.

 

>>> class Item:
...    def __init__(self, name):
...        self.name = name
...    def __repr__(self):
...        return 'Item({!r})'.format(self.name) # repr() shows quotes: {!r}
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
>>> Item('bar')
>>> q.pop()
>>> Item('spam')
>>> q.pop()
>>> Item('foo')
>>> q.pop()
>>> Item('grok')
>>>