새싹프로그래머의 이야기

파이썬 알고리즘 강의를 듣던 중 generator가 메모리 효율성에 큰 영향을 미친다는 얘기를 듣고 한번 정리해보고자 합니다.

generator란?

간단하게 말하자면, 데이터에 순차적으로 접근할 수 있는 객체인 iterator를 반환해주는 함수 입니다.

그렇다면 generator를 어떻게 활용할까요?

generator 활용법

제너레이터 활용법은 크게 두가지 입니다.

• yield 와 next()의 활용
• () 의 활용

1. yield와 next()를 활용한 코드

def func(l:list):
    for i in l:
        yield i +10


nums = func([1,2,3,4,5])

print(func(nums))   #<generator object func at 0x7fe75008f580>
print(next(nums))   #11
print(next(nums))   #12
print(next(nums))   #13
print(next(nums))   #14
print(next(nums))   #15

첫번째 print() 구문을 보시면 yield 구문을 활용하여 generator가 생성되신 것을 확인하실 수 있습니다.

def func(l:list):
    for i in l:
        yield i +10


nums = func([1,2,3,4,5])

print(func(nums))   #<generator object func at 0x7fe75008f580>

for i in nums:
    print(i)

위와 같이 반복문을 활용할 수도 있는데요. 결과는 위 코드와 같은 결과를 보입니다.

2. ()를 활용한 코드

nums = (i + 10 for i in range(1,6))

print(nums) # <generator object <genexpr> at 0x7fc340036190>

for i in nums:
    print(i)

이렇듯 구문을 ()로 감싸주게 되면 generator가 생성되는 것을 확인 하실 수 있습니다.

generator의 동작 방법은 알아보았습니다.

근데 이러한 동작 방법이 어떻게 메모리 효율성에 영향을 미치는 것일까요?

generator가 memory 효율성에 미치는 영향

Python 주로 데이터를 다룰 때 활용하는 언어입니다(데이터 수집, 인공지능 등). 데이터에서 유의미한 결과를 얻기 위해서는 정말 방대한 데이터를 활용할텐데요. 큰 양의 데이터를 한번에 담게 되면 메모리 부족 현상이 발생하여 프로그램이 갑자기 중단되는 등의 문제가 발생할 수 있습니다.

이때 generator는 개발자에게 엄청난 도움을 주게 됩니다.

generator는 모든 값의 순서를 기억한 상태로 동작하기 전까지 메모리를 할당하지 않기 때문입니다.

그렇기에 generator를 활용하게 되면 데이터를 한번에 적재하지 않아도 되기 때문에 메모리 소비를 줄일 수 있습니다. 즉, 한번에 적재하고 활용하는 방식 보다 훨씬 안정적인 방법이라고 할 수 있습니다.

또한 필요할 때 마다 호출하여 사용하는 지연 평가 방식이 가능하기 때문에 메모리를 효율적으로 사용할 수 있습니다.

[풀이 방법]

• 시간을 다루는 문제이므로, 'HH:MM' 형태로 주어진 시간을 분 단위로 통일하여 활용한다.
• 이전 사람의 종료 시간과 현재 사람의 시작시간을 비교하여, 종료시간 + 10분(청소 시간) 보다 시작시간이 뒤에 있을 경우 기존의 방을 배정하고 아닐 경우 새로운 방을 배정한다.

[풀이 코드]

import heapq


def solution(book_time):
    answer = 0
    heap = []
    bt = [(int(s[:2]) * 60 + int(s[3:]), int(e[:2]) * 60 + int(e[3:])) for s, e in book_time]
    bt.sort()

    for s, e in bt:
        if not heap:
            heapq.heappush(heap, e + 10)
            continue

        if heap[0] <= s:
            heapq.heappop(heap)
        else:
            answer += 1

        heapq.heappush(heap, e + 10)

    return answer + 1

선택정렬(selection sort)

선택정렬(selection sort)는 가장 작은 값부터 뽑아내어 정렬하는 방법입니다. 

시간복잡도는 $O(N^2)$ 입니다.

init_list = [5, 12, 22, 35, 64, 53,72]
res_list = []

while init_list:
    res_list.append(min(init_list))
    init_list.pop(init_list.index(min(init_list)))

print(res_list)

삽입정렬(Insertion sort)

삽입정렬(Insertion sort)는 원소의 값이 들어갈 위치를 찾아 삽입해주는 방식입니다.

시간 복잡도는 최선일 경우 $O(N)$ , 최악의 경우 $O(N^2)$이 걸리는 방법입니다.

init_list = [5, 12, 22, 35, 64, 53,72]
res_list = []

def find_insertion_index(lst: list,val:int):
    for i in range(len(lst)):
        if lst[i] > val:
            return i
    return len(lst)

for i in init_list:
    res_list.insert(find_insertion_index(res_list,i),i)
print(res_list)

병합정렬(merge sort)

병합정렬(merge sort)는 원소들을 분할 한 후, 하나 하나 정렬하여 병합하는 방식입니다.

시간 복잡도는 최선/최악 모두 $O(N logN)$을 보여주는 상당히 빠른 정렬 방식입니다.

init_list = [5, 12, 22, 35, 64, 53,72]

def merge_sort(input_list: list):
    length = len(input_list)
    res = []

    if length == 1:
        return input_list

    mid = length // 2

    arr1 = merge_sort(input_list[:mid])
    arr2 = merge_sort(input_list[mid:])

    while arr1 and arr2:
        if arr1[0] < arr2[0]:
            res.append(arr1.pop(0))
        else:
            res.append(arr2.pop(0))

    while arr1:
        res.append(arr1.pop(0))
    while arr2:
        res.append(arr2.pop(0))

    return res

print(merge_sort(init_list))

퀵정렬(quick sort)

퀵정렬은 pivot, 분할과정복 방식을 활용하여 정렬하는 방식입니다.

pivot을 기준으로 pivot보다 작은 값과 큰 값으로 분할하고, 이 분할된 원소들을 정렬하며 병합하는 방식입니다.

시간복잡도는 최선과 평균의 경우 $O(NlogN)$, 최악의 경우 $O(N^2)$ 입니다.

init_list = [5, 12, 22, 35, 64, 53,72]

def quick_sort(array: list):
    if len(array) <= 1:
        return array
    pivot = array[0]
    low_list = []
    high_list = []
    for i in array[1:]:
        if i < pivot:
            low_list.append(i)
        else:
            high_list.append(i)

    return quick_sort(low_list) + [pivot] + quick_sort(high_list)


print(quick_sort(init_list))

*해당 글은 '제주코딩베이스캠프'님의 강의를 듣고 작성 되었습니다.

C언어를 사용할 때는 malloc() 함수와 free()함수를 통해 메모리를 직접 할당/해제를 해주었습니다. 

그런데 Python을 사용할 때는 별도로 메모리를 관리하지 않더라구요.

문득 왜일까? 라는 생각이 들어서 알아보고 정리를 해보려고 합니다.

Python의 메모리 관리

파이썬은 Garbage Collector가 메모리를 관리해줍니다. C언어와 달리 사람이 메모리를 직접 할당/해제 하는 것이 아니라 언어 자체에서 직접 관리해주는 방식인데요. 

가장 많이 활용하는 방식은 Reference Counting 이라는 방식입니다.

Reference Counting 이란?

Reference Counting 방식이란, 객체를 얼마나 참조하는지를 통해 메모리를 관리하는 방식입니다.

Python은 객체를 생성하면 Heap 메모리에 객체를 생성하는데요. 

예를 들어, 다음과 같은 코드가 있을 때 s라는 변수가 객체를 참조하는 것을 counting 하여 메모리를 관리합니다.

s = 'hello world'

위와 같은 코드를 작성하면 다음과 같이 변수가 객체를 참조하게 됩니다.

'hello world'라는 객체를 s에 할당했을 때, Garbage Collector는 'hello world'라는 객체의 reference counting을 1 증가시키고 메모리에 할당합니다.

반대로 s라는 변수가 다른 객체를 참조하게 되었을 때는 reference counting이 0이 될 것이고 Garbage Collector는 이를 통해 메모리를 해제하게 됩니다.

직접 확인해보면 다음과 같습니다.

s가 호출된 함수가 종료되면 reference counting은 0이 되어 메모리는 해제되게 됩니다.

Garbage Collector의 장점 및 단점

사람이 직접 관리하지 않아도 메모리 관리가 되기 때문에 편하지만, 장점만 존재하는 것은 아닙니다.

Garbage Collector의 장점이라 함은 다음과 같습니다.

• reference counting이 0 이 될 때마다 메모리를 해제해주기 때문에 실시간 작업이 가능하다.
• 위와 같은 이유로 메모리 관리가 간편하며 즉시 메모리에서 해제가 가능하다.

반면 단점 또한 존재합니다.

• Object 마다 reference counting을 수행해주어야 하기 때문에 관리 비용이 많이 듭니다.
• Object의 reference count가 0이 될 경우, 연쇄적인 Garbage Collecting이 발생할 수 있습니다.
• 사람이 직접 할당/해제를 하지 않기 때문에 세밀한 메모리 관리가 어렵다.

https://leetcode.com/problems/minimum-absolute-difference-in-bst/

문제: 트리의 노드의 중에서 두 노드의 차가 제일 작은 값을 구하는 문제

풀이 코드:

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        tree = []

        def getVal(root: Optional[TreeNode]):
            tree.append(root.val)
            if root.left != None:
                getVal(root.left)
            if root.right != None:
                getVal(root.right)

        getVal(root)

        tree = sorted(tree)

        return min(tree[i + 1] - tree[i] for i in range(len(tree) - 1)) 

777번: https://leetcode.com/problems/swap-adjacent-in-lr-string/

2337번: https://leetcode.com/problems/move-pieces-to-obtain-a-string/

문제: 'L' 과 'R' 이 포함된 두 문자열이 주어졌을 때, 문제에서 목표로 주어진 문자열을 만들 수 있는지 여부를 판별하는 문제

문제 설명:

두 문제 모두, 'L' 이라는 문자는 왼쪽으로만 이동 가능하며, 'R'이라는 문자는 오른쪽으로만 이동 가능하도록 되어있습니다.

이때 각 문자는 서로를 넘어갈 수 없습니다.

예를 들면, '_L_RR' 이라는 문자가 주어졌을 때, 'L__RR'은 만들 수 있지만 '__RLR'은 만들 수 없습니다.

풀이 코드:

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        if start.replace('_', '') != target.replace('_', ''):
            return False

        startL = [i for i in range(len(start)) if start[i] == 'L']
        startR = [i for i in range(len(start)) if start[i] == 'R']
        endL = [i for i in range(len(target)) if target[i] == 'L']
        endR = [i for i in range(len(target)) if target[i] == 'R']

        for i, j in zip(startL, endL):
            if i < j:
                return False

        for i, j in zip(startR, endR):
            if i > j:
                return False
        return True

풀이의 핵심은 두가지 입니다.

• 'L'과  'R'의 순서는 바뀔 수 없음
• 목표 문자열에서 기존 문자열 대비 'L'의 위치는 오른쪽에 존재할 수 없으며, 반대로 'R' 의 위치 또한 왼쪽에 존재 할 수 없다는 것입니다.

if start.replace('_', '') != target.replace('_', ''):
    return False

공백에 해당하는 문자열을 없앤 후, 두 문자열을 비교하여 순서를 확인합니다.

startL = [i for i in range(len(start)) if start[i] == 'L']
startR = [i for i in range(len(start)) if start[i] == 'R']
endL = [i for i in range(len(target)) if target[i] == 'L']
endR = [i for i in range(len(target)) if target[i] == 'R']

for i, j in zip(startL, endL):
    if i < j:
        return False

for i, j in zip(startR, endR):
    if i > j:
        return False

위 코드를 통해, 'L'과 'R'의 위치 변화를 판별합니다.

*풀이는 Discuss에서 투표를 많이 받은 풀이를 참조하였습니다.

https://leetcode.com/problems/watering-plants/

문제: 들고 다닐 수 있는 물의 양과 각 식물에 필요한 물의 양이 주어질 때, 모든 식물에 물을 주기 위해 이동해야하는 거리를 구하는 문제.

문제 설명:

우물은 index가 -1에 해당하는 위치에 있다고 가정을 하며, 각 식물이 필요로 하는 물의 양은 1차원 배열로 주어지고 한번에 들고 다닐 수 있는 물의 양은 int형으로 주어집니다.

위 예시를 한번 보면, 총 4개의 식물에 물을 주어야하며 들고 다닐 수 있는 물의 용량은 5입니다.

index가 0에 해당하는 식물에 도달하여 물을 주면, 이동 거리는 1이 되며 남은 물의 용량은 3이 됩니다.

index가 1에 해당하는 식물에 도달하여 물을 주면, 이동거리는 2가 되며 남은 물의 용량은 1이 됩니다.

이때, 다음 식물은 3만큼의 물의 양이 필요한데 현재 가지고 있는 물의 양은 1이므로 우물에 다녀와야 합니다.

따라서, 2칸 뒤로 이동해 물을 채운 후 다음 식물에 해당하는 위치로 이동해 물을 주어야 합니다.

이 과정을 반복하여 모든 식물에 물을 주는데 필요한 거리를 구하는 문제 입니다.

풀이 코드:

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        now = -1
        steps = 0
        cap = capacity
        for i in range(len(plants)):
            steps += (i - now)
            cap -= plants[i]
            now = i
            if i != len(plants) - 1 and cap < plants[i + 1]:
                steps += (i + 1) * 2
                cap = capacity

        return steps

문제에서는 위의 예시에서 index = 1 인 위치에서 물을 채워오는 거리를 2칸 뒤로 간 후, 다음 위치인 index = 2인 위치로 3칸 앞으로 이동하는 계산 방식을 사용했습니다.

하지만 저는 우물에 들려 물을 채운 후 index = 2인 위치로 향할 때, index = 1인 위치에서 index = -1 로 왕복을 한 후 앞으로 1칸 전진하는 계산 방식을 사용했습니다.

https://leetcode.com/problems/add-two-numbers/

문제: 수를 역순으로 구성한 두 개의 linked-list가 존재할 때, 각 linked-list의 자리 수를 더한 결과 값을 구하는 문제

문제 설명:

문제에서 주어진 예시를 보면 다음과 같습니다.

342 는  2 -> 4 -> 3 으로 구성되며, 465는 5 -> 6 -> 4로 구성됩니다.

각 자리 수의 합을 구하면 807로 7 -> 0 -> 8로 구성된 linked-list를 반환하면 됩니다.

문제 코드:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        number1 = 0
        ten1 = 1
        number2 = 0
        ten2 = 1

        while True:
            number1 += (l1.val * ten1)
            if l1.next == None:
                break
            l1 = l1.next
            ten1 *= 10
        while True:
            number2 += (l2.val * ten2)
            if l2.next == None:
                break
            l2 = l2.next
            ten2 *= 10

        linked_list = None

        for i in list(str(number1 + number2)):
            cur = ListNode()
            cur.val, cur.next = i, linked_list
            linked_list = cur
        return linked_list

저 같은 경우, 각 linked-list의 값을 10진수로 변환한 후 더한 값을 구해 다시 liked-list를 구성하는 방식을 사용했습니다.

다른 풀이 코드를 보다 linked-list 자체로 풀이를 진행한 깔끔한 코드가 있어 소개해보고자 합니다.

그 코드는 다음과 같습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        val = 0
        head = ListNode()
        linked_list = head
        while l1 or l2 or val:

            if l1:
                val += l1.val
                l1 = l1.next
            if l2:
                val += l2.val
                l2 = l2.next

            linked_list.next = ListNode(val % 10)
            linked_list = linked_list.next
            val //= 10

        return head.next

linked-list에서 10진수로의 변환을 하지 않고 문제를 푼 코드입니다.

제 코드의 경우, Runtime은 151ms이고 메모리는 14.1MB를 사용했습니다.

제가 추가로 올려드린 코드의 경우 Runtime은 120ms이고 메모리는 13.8MB를 사용했습니다.

시간과 공간 활용도 모두 linked-list 자체를 활용하여 연산하는 것이 더 좋다는 것을 알 수 있습니다.

https://leetcode.com/problems/defuse-the-bomb/

문제: 문제에서 주어진 조건에 따라, 배열 원소의 합을 반환하는 문제

문제 설명:

정수가 담긴 배열과 k라는 값이 주어집니다.

다음과 같이 총 3가지 조건에 따라 문제를 풀이하는 방법이 달라집니다. 

• k > 0 일 경우, 배열의 i번째 값은 i번째 이후 k개의 원소의 합으로 대체됩니다.

예를 들어, [5, 7, 1, 4] 이라는 배열과 k = 3 이라는 값이 주어질 경우, 0번째는 7+1+4 (==12) 로 대체되고 1번째 값은 1+4+5(==10)으로 대체됩니다.

따라서 최종 반환되는 배열은 [12, 10, 16, 13] 이 됩니다.

• k < 0 일 경우, 배열의 i번째 값은 i번째 이전 k개의 원소의 합으로 대체됩니다.

예를 들어, [2, 4, 9, 3] 이라는 배열과 k = -2 라는 값이 주어질 경우, 0번째는 3+9 (==12)로 대체 되고 1번째 값은 2+3 (==5)로 대체됩니다.

따라서 최종 반환되는 배열은 [12, 5, 6, 13] 이 됩니다.

• 마지막으로 k = 0 일 경우, 배열의 모든 원소는 0이 되어 반환됩니다.

풀이 코드:

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        length = len(code)
        lst = []
        if k > 0:
            for i in range(length):
                s = 0
                for j in range(1, k + 1):
                    s += code[(i + j) % length]
                lst.append(s)

        elif k < 0:
            for i in range(length):
                s = 0
                for j in range(1, abs(k) + 1):
                    s += code[i + (-1 * j)]
                lst.append(s)
        else:
            return [0] * length
        return lst

https://leetcode.com/problems/unique-number-of-occurrences/

문제: 숫자로 이루어진 배열에서 각 원소의 갯수가 중복되는지 판별하는 문제

문제 설명:

문제에서 주어진 예시로 설명을 해보겠습니다.

예제 1번을 보면, [1, 2, 2, 1, 1, 3] 이라는 배열이 있습니다.

원소 1은 3개, 원소 2는 2개, 원소 3은 1개로 각 원소의 갯수가 중복되지 않으므로 True를 반환해줍니다.

예제 2번을 보면, 원소 1과 2가 둘다 1로 원소의 갯수가 중복이 되므로 False를 반환해줍니다.

저는 이 문제를 파이썬의 Counter 함수를 통해서 풀었는데, Counter 함수를 사용하게 되면 다음과 같은 결과가 나옵니다

from collections import Counter
arr= [1,2,2,1,1,3]
print(Counter(arr))

# 출력한 결과
# Counter({1: 3, 2: 2, 3: 1})

Counter를 쓰면 key-value 쌍으로 counter 형의 데이터가 만들어집니다.

이를 바탕으로, value 값들을 통해 중복된 값이 있는지 여부를 판별해주었습니다.

풀이 코드:

from collections import Counter
from collections import deque


class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        cntarr = Counter(arr)
        counterval = deque(cntarr.values())

        while counterval:
            v = counterval.pop()
            if v in counterval:
                return False
        return True