머리도 아둔한데 늦바람이 들어 새로운 것들을 배우다보면 남들은 다들 뛰고 날고 있는데 나는 엉금엉금 기어다니는 기분이 들어 서글퍼지곤 한다. 하지만 어쩌겠나. 귀여운 물개 사진을 보며 마음을 추스를 수밖에.


✰✰ 아래 내용들은 <Hello Coding 그림으로 개념을 이해하는 알고리즘>과 <파이썬 자료구조와 알고리즘> 등 내용을 정리한 것임을 밝힙니다. 만약 문제가 있을 시 연락 바랍니다. ✰✰
배열 | array

자료구조를 공부하다보면 배열(array)도 나오고 리스트(list)도 나온다. 두 개념은 꽤 헷갈리는데 헷갈림을 좋아하는 사람은 아무도 없다. 배열과 리스트를 알아보자.

만약 여러 개의 원소를 저장해야 한다면, 배열과 리스트라는 두 가지 방법 중 하나를 사용해야 한다. 두 가지는 각각 장단점이 있다. 두 방식의 차이점을 알아야 경우에 맞게 선택해 사용할 수 있다.

배열을 먼저 살펴보자.

배열은 데이터를 메모리에 차례대로 붙여서 저장한다. 하나씩 쭉 붙여서 데이터를 저장하다가 다른 데이터에 이미 할당된 메모리 공간을 만나면, 컴퓨터는 배열을 통째로 저장할 수 있는 다른 메모리 공간을 요청해 배열을 그 자리로 옮긴다. 이때 작업 소요 시간이 소요되는데, 이를 방지하기 위해 미리 충분히 많은 메모리 공간을 요청하는 방법이 있다. 전체 배열을 옮기지 않아도 계속 배열을 추가할 수 있게끔 하는 것이다. 이 방법의 문제는 추가할 데이터가 생기지 않을 때 미리 할당된 메모리가 낭비된다는 것이다. 또 만약 데이터 크기가 미리 할당한 메모리 공간보다 커지면 결국 또 메모리 공간을 옮겨야 한다.

파이썬에서는 배열이 따로 데이터 타입으로 존재하지 않는다. 리스트를 사용한다. 파이썬 리스트는 다른 프로그래밍 언어에서 말하는 배열보다는 좀 더 융통성 있는 자료구조이다.



리스트 | list

연결 리스트(linked lists)를 살펴보자. 연결 리스트는 데이터 원소들을 순서대로 늘어놓는다는 점에서 선형 배열(linear array)와 비슷하지만, 늘어놓는 방식에서 두 가지 큰 차이가 있다. 선형 배열이 "번호가 붙여진 칸에 원소들을 채워넣는" 방식이라면, 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식이다.

연결 리스트는 원소(데이터)를 메모리 어느 곳에나 둘 수 있다. 각 원소에는 목록의 다음 원소에 대한 주소가 저장돼 있다. 여러 가지 임의의 메모리 주소들이 하나의 목록으로 연결돼 있는 것이다.


출처 : learnsteps


각 데이터 아이템 하나하나를 노드라고 부른다. 노드 안에는 데이터와 다음 노드를 가리키는 링크가 달려 있다. 노드 안 데이터는 문자열, 레코드, 또 다른 연결 리스트 등 서로 다른 구조로 이루어질 수 있다.

첫 노드를 Head라고 하고 가장 끝 노드를 Tail이라고 한다. Head와 Tail, 해당 연결 리스트에 몇 개의 노드가 있는 지 등 정보와 해당 리스트에 가해질 수 있는 연산들을 묶어 기록해두면 이 리스트에 대한 추상적 자료구조(Abstract Data Structure)를 구할 수 있다.

먼저 노드라는 클래스의 생성자를 만들어보자.

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None


다음으로 비어 있는 연결 리스트를 LinkedList라는 이름의 클래스를 정의해 만들자.

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None











이제 LinkedLIst라는 데이터 구조, 그리고 Node라는 데이터 구조에 연산을 가해 연결 리스트 속성을 갖도록 프로그래밍을 해보자.




class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    # 특정 원소 참조 함수
    def getAt(self, pos):
        if pos <= 0 or pos > self.nodeCount:
            return None
        i = 1 # index 1부터 시작 
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr



연결 리스트의 단점은 리스트의 마지막 원소를 바로 볼 수 없다는 것이다. 마지막 원소에 접근하기 위해서는 1번 원소에서부터 시작해 다음 원소의 참조(주소)를 얻는 방식을 거쳐야 한다. 이를 순차 접근 (sequential access)라고 한다.



이 점에 있어 배열은 모든 원소의 주소를 알고 있어 편리하다. 배열은 임의 접근(random access)가 가능하기 때문이다. 또한 연결 리스트 안에 노드가 몇 개인지 기억해두는 게 좋다. Head, Tail, 노드 갯수 등을 기록하고 해당 리스트에 가해질 수 있는 연산들을 넣으면 이 연결 리스트의 추상적 자료 구조가 된다.







원소를 배열이나 리스트의 중앙에 삽입해야 하는 상황이라면 어떤 방법이 더 편할까? 리스트다. 배열은 다음에 오는 모든 원소의 위치를 바꿔야 해 이 경우 적합하지 않다.



리스트에서 원소를 삽입(.insert( , ))하거나 삭제(.del( , ))할 때 걸리는 시간은 리스트의 길이에 비례(선형 시간, O(n))한다. 반면 원소를 덧붙이거나 (.append( )) 혹은 끝에서 하나를 꺼낼 때(.pop( ))는 리스트 길이와 관계 없이 빠르게 실행된다. 이때 필요한 실행 시간은 O(1)으로 상수 시간이라고 한다.



배열과 리스트 중 '임의의 원소에 접근이 가능한' 배열이 더 많이 사용된다.











재귀 | recursion


재귀는 한 마디로 우아하다. 하지만 프로그래머가 멍청해 재귀 함수를 만들 때 실수를 한다면 실수가 무한 반복되니 멍청함을 관리해야 한다.



모든 재귀 함수는




    

  • 기본 단계 : 함수가 자기 자신을 호출하는 부분
    • 

  • 재귀 단계 : 자기 자신을 다시 호출하지 않는 부분. 즉 무한 반복으로 빠지지 않게 하는 부분.
    • 











1
2
3
4
5
6
7


def countdown(i):
    print(i)
    if i <= 1: # base case
        return
    
    else :  # reculsive case
        countdown(i-1)














재귀 알고리즘의 효율










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


# Recursive version
def sum(n):
    if n <= 1:
        return n
    else:
        return n + sum(n+1)


# Iterative version 
def sum(n):
    s = 0
    while n >= 0:
        s += n
        n -= 1
    return s









코드 출처 : 프로그래머스 





위 코드는 같은 기능을 재귀 알고리즘과 while을 사용한 비-재귀 알고리즘으로 구현한 것이다.

두 경우 모두 실행에는 O(n) 이 걸린다. 효율성은 어떨까? 효율성 측면에서는 Iterative version이 더 우수하다. 재귀적 방법은 효율성에 있어 한계를 가진다는 것을 기억해두자.







스택 | stack



컴퓨터는 호출 스택(call stack)을 사용한다. 스택에는 push와 pop이라는 두 가지 연산이 있다.










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def greet(name):
    print("hello, " + name + "!")
    greet2(name)
    print("getting ready to say bye...")
    bye()

def greet2(name):
    print("how are you, " + name + "?")

def bye():
    print("ok bye!")

print(greet("maggie"))












output :



hello, maggie!

how are you, maggie?

getting ready to say bye...

ok bye!

None



위와 같이 여러 개의 함수를 호출하며 함수에 사용되는 변수를 저장하는 스택을 호출 스택이라고 한다.  스택은 편리하지만, 호출 스택은 너무 커져서 메모리를 엄청 소비할 수도 있다는 단점이 있다. 함수 호출을 할 때마다 메모리를 사용하기 때문이다. 이게 싫다면 1) 재귀 대신 반복문 사용 2) 꼬리 재귀 (tail recursion) 방법을 사용하 수 있다.



재귀 함수에서 호출 스택을 사용한 예시를 보자.










1
2
3
4
5
6
7


def factorial(x):
    if x == 1:
        return 1
    else:
        return x * factorial(x-1)

print(factorial(3))

















알고리즘 | algorithm



알고리즘은 9세기 이슬람 수학자 알콰리즈미의 이름에서 유래한 용어다. 특정한 상황에서 바라는 결과를 내도록 정의된 규칙과 절차의 집합을 뜻한다.



코딩의 핵심은 좋은 알고리즘을 구현하는 것이다. 좋은 알고리즘은 목적한 일을 정확하고! 빠르게! 수행할 수 있는 알고리즘이다. 즉 좋은 알고리즘인지 분석하려면 정확성, 실행 시간(복잡도), 사용하는 공간의 양, 단순성 및 명료성, 최적화 (다른 알고리즘에 비해 성능이 더 낫다는 것을 증명할 수 있는가?)을 살피면 된다.



알고리즘은 다음 두 가지로 평가한다.



1) 시간 복잡도(Time Complexity)로 나타내는 수행 시간 : 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계



2) 공간 복잡도(Space Complexity)로 평가하는 공간 복잡 : 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계



시간 복잡도를 더 자세히 알아본다.



시간 복잡도는 다음 두 가지를 중요시 한다.



- 평균 시간 복잡도(Average Time Complexity) : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균



- 최악 시간 복잡도(Worse-case Time Complextiy) : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간





빅오 표기법 | Big O notation 



알고리즘의 시간 복잡도를 표현하는 방법으로, 점근 표기법(asymptotic notation)의 하나이다. 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타내며, 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현한다.  빅오 표기법은 속도를 시간 단위로 세지 않는다. 빅오 표기법은 1/2과 같은 상수항은 무시한다.



입력의 크기가 n일 때,



O(logn)은 입력의 크기의 로그에 비례하는 시간이 소요된다는 의미이다.

O(n)은 입력의 크기에 비례하는 시간이 소요된다는 의미이다.



빅오 표기법에서 계수(상수)는 그다지 중요하지 않다.





많이 사용하는 빅오 실행 시간을 빠른 것부터 써보면






    

  • O(log n), 로그 시간 - 예) 이진 탐색
    • 

  • O(n), tjsgud tlrks - 예) 단순 탐색
    • 

  • O(n * log n)         - 예) 퀵 정렬 등 빠른 정렬 알고리즘
    • 

  • O(n^) :                - 예) 선택 정렬 등 느린 정렬 알고리즘 
    • 

  • O(n!) :                 - 예) 정말 느린 알고리즘 
    • 











Official Big-O Cheat Sheet Poster. source : REDBUBBLE
















출처 : bigocheatsheet


















출처 : bigocheatsheet










출처 : bigocheatsheet







알고리즘 단계에는 for문과 if문, 함수 호출이 있다. 산술식과 논리식(not, and, or)도 사용한다.



우리가 필요로 하는 알고리즘은 대부분 이미 구현돼 있다. 가져다 쓰면 된다. 하지만 알고리즘을 스스로 제대로 이해하고 있지 않다면 그 안일함의 대가를 언젠가는 치르게 될 것이다. 여러 알고리즘들의 차이를 이해하고, 각 알고리즘의 장단점을 이해해야 한다. 그래야 상황에 맞춰 퀵 정렬을 사용할지 병합 정렬을 사용할지 판단할 수 있다.







탐색 | search



탐색은 여러 원소로 이뤄진 데이터에서 특정 원소를 찾는 작업이다. 탐색은 기본적으로 두 가지 종류가 있다.



1) 선형 탐색 (linear search) 혹은 순차 탐색(sequential search)



순차적으로 모든 요소들을 탐색하는 방법. 배열의 길이에 비례해 시간이 걸린다. 빅오 표기법으로 나타내면  average, wort-case 모두 O(n)이다.




def linear_search(L, x):
    i = 0
    while i < len(L) and L[i] != x:
        i += 1
    if i < len(L):
        return i
    else:
        return -1



코드 출처 : 프로그래머스





2) 이진 탐색



아래에서 자세히 설명





이진 탐색 | binary_search 



이진 탐색은 리스트의 원소들이 정렬돼 있어야만 사용할 수 있다. 정렬된 배열 내에서 지정된 입력값의 위치(키)를 찾는 방법이다. 이진 탐색 알고리즘은 각 단계에서 입력값과 배열 중간 요소를 비교해 입력값과 중간 요소가 일치하면 배열의 위치를 반환한다. 입력값이 중간 요소보다 작으면, 중간 요소의 왼쪽 하위 배열에서 탐색 과정을 반복한다. 입력값이 중간 요소보다 크면 중간 요소의 오른쪽 하위 배열에서 탐색 과정을 반복한다. 이진 탐색을 재귀적으로 사용하면 이진 트리 문제를 해결할 수 있다.



이진 탐색을 사용하면 최악의 경우를 가정해도 log n개 숫자만 확인하면 답을 확인할 수 있다. O(long)




def binary_search(list, item):
    low = 0
    high = len(list) - 1 # low, high는 전체 리스트 중에서 어떤 부분을 탐색해야 할 지 알려줌

    while low <= high:  # 만약 탐색 범위를 하나로 줄이지 못했으면 계속 실행
        mid = (low + high) // 2 # 가운데 숫자를 확인
        guess = list[mid]

        if guess == item: # 아이템을 찾는다
            return mid

        elif guess > item: # 추측한 숫자가 너무 크면
            high = mid - 1
        else:            # 추측한 숫자가 너무 작으면
            low = mid + 1
            
    return None # 아이템이 리스트에 없음

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))
print(binary_search(my_list, -1))





output : 1, None



이진 탐색은 무식하게 하는 선형 탐색에 비해 실행 시간을 절약할 수 있다. 선형 탐색을 사용하면 100개 원소가 들어 있는 리스트에서 원소 하나를 찾을 때 100번 추측해야 한다. 즉 추측해야 할 최대 횟수는 len(list)이다. 이를 선형 시간(linear time) 이라고 한다. 빅오 표기법 표기하면 O(n)이다.



반면 이진 탐색은 실행하는 데 로그 시간(logarithmic time)이 걸린다. 빅오 표기법으로 쓰면 O(log n).



파이썬에는 이진 탐색을 할 수 있는 bisect 모듈이 내장돼 있다.




from bisect import bisect
l = [0, 3, 4, 5]
bisect(l, 5)  

# 빈 리스트 혹은 값이 없는 예외의 경우
print(bisect(l, -1))
print(bisect(l, 1))
print(bisect(l, 7))
print(bisect([], 1))



bisect(l, 5)의 출력값은 입력값 5의 리스트 위치(인덱스 + 1)인 4이다.

6~9번 코드의 output은



0

1

4

0















정렬 알고리즘  (위키백과에서 보기)



정렬 알고리즘 ( sorting algorithm)은 원소들을 번호순이나 사전 순서 등 정해진 기준에 따라 순서대로 열거하는 알고리즘이다. 데이터의 정규화 등에 유용하게 쓰인다.



파이썬은 sorted( ) 라는 정렬 내장 함수가 있다. sorted( ) 는 정렬된 새로운 리스트를 만든다.

반면, sort( ) 는 해당 리스트를 정렬한다. 새로운 리스트가 만들어지는 게 아니라는 것을 주의하자. 원소를 크기가 큰 순서부터 작은 순서대로 즉, 내림차순으로 정렬하고 싶다면 reverse=True 파람을 지정해주면 된다.









삽입 정렬 | insertion sort



선택 정렬은 배열에서 항목을 한 번에 한 번씩 제 위치에 정렬하는 방식으로, 간단하지만, 그닥 빠른 정렬 알고리즘은 아니다. 장점은 입력 데이터의 배열을 저장하는 메모리 외에 추가 메모리가 필요하지 않다는 것이다.



삽입 정렬 알고리즘은 이차 시간 알고리즘의 한 예이다.



Best case : 주어진 배열이 이미 정렬돼 있는 상태라면, O(n)

Worse case : 주어진 배열이 역순으로 정렬대 있는 경우에는, O(n^)



삽입 정렬은 반목문을 사용한다. 예제 코드로 알아보자.









선택 정렬 | selection sort 



선택 정렬은 깔끔하지만, 느린 정렬 알고리즘이다. 먼저 리스트에서 가장 작거나 큰 항목을 찾아 첫 번째 항목과 위치를 바꾸고, 그다음 항목을 찾아서 두 번째 항목과 위치를 바꾼다. 이 과정을 리스트 끝에 도달할 때까지 반복한다. 리스트가 이미 정렬돼 있어도 시간 복잡도는 O(n^)다.



def selection_sort(seq):
    length = len(seq)
    for i in range(length-1):
        min_j = i
        for j in range(i+1, length):
            if seq[min_j] > seq[j]:
                min_j = j
        seq[i], seq[min_j] = seq[min_j], seq[i]
    return seq

def test_selection_sort():
    seq = [11, 3, 28, 43, 9, 4]

    assert(selection_sort(seq) == sorted(seq))
    print("테스트 통과!")

if __name__ == "__main__":
    test_selection_sort()















분할 정복 | divide-and-conquer



분할 정복 전략은 유명한 재귀적 알고리즘 중 하나다. 문제를 더 작은 조각으로 나눠서 접근한다.



분할 정복 전략은 두 단계를 거친다.



1) 기본 단계를 해결한다. 가능한 한 간단한 문제여야만 한다.

2) 문제가 기본 단계가 될 때까지 나누거나 작게 만든다.



만약 리스트에서 분할 정복을 적용한다면 기본 단계는 원소가 없는 빈 배열이거나 하나의 원소만 가진 배열이다.



코드로 분할 정복 예시를 보자.




def sum(arr):
    total = 0
    for x in arr:
        total += x
    return total





상황 : 2, 4, 6 이라는 숫자 배열이 있다. 이 배열의 숫자들의 총합을 구하려 한다.



이 부분 이해가 잘 안 되지만 일단 넘어간다.



if you want to study further ) study Euclid's algorithm



병합 정렬 알고리즘이 분할 정복 알고리즘의 한 예다.





병합 정렬 | merge sort



병합 정렬 알고리즘의 시간 복잡도는 O(n logn)으로, 보다 낮은(나은) 복잡도를 가진다.

입력 패턴에 따라 정렬 속도에 차이가 있지만, 정렬 문제에 대해 O(n logn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없다는 것이 증명돼 있다.



병합 정렬은 정렬할 데이터를 반씩 나누어 각각을 정렬시킨다. O(logn)

이제 정렬된 데이터를 두 묶음씩 한데 합친다. O(n)













퀵 정렬 | quick sort



퀵 정렬은 분할 정복 전략을 사용하는 정렬 알고리즘이다.

퀵 정렬은 우선 기준 원소(pivot)를 하나 선택하는 것에서부터 시작한다. 기준 원소를 고르고, 모든 원소를 기준 원소보다 작은 원소와 큰 원소로 분류한다. 이를 분할(partitioning)이라고 한다.



이제




    

  • 기준 원소보다 작은 숫자들로 이뤄진 하위 배열(sub-array)
    • 

  • 기준 원소
    • 

  • 기준 원소보다 큰 숫자들로 이뤄진 하위 배열
    • 




가 있는데 하위 배열 두 개는 정렬돼 있지 않다. 이들을 정렬하기 위해서는 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다. 퀵 정렬 특징은 선택한 기준 원소에 따라 처리 속도가 달라진다는 것이다. 달리 말하면 퀵 정렬의 성능은 피벗 값을 잘 선택하는 것에 달려있다.



리스트의 중앙값(median)을 피벗으로 선택하는 것은 이미 정렬된 리스트에서 가장 적합한 선택이다. 정렬되지 않은 리스트에서도 괜찮은 선택이다.



퀵 정렬은 평균 O(n log n) 실행 시간을 갖고 최악의 경우 O(n^)이 될 수도 있다. 







퀵 정렬 코드 예시.














 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def quicksort(array):
    if len(array) < 2:
        return array # 기본 단계 : 원소의 개수가 0이나 1이면, 이미 정렬돼 있는 상태
    else:
        pivot = array[0] # 재귀 단계
        less = [i for i in array[1:] if i <= pivot] # 기준 원소보다 작거나 같은 모든 원소로 이뤄진 하위 배열
        greater = [i for i in array[1:] if i > pivot] # 기준 원소보다 큰 모든 원소로 이뤄진 하위 배열
        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))












output : [2, 3, 5, 10]







해시 함수 | hash function



해시 함수는 문자열(str)을 받아 숫자를 반환하는 함수다. 기술적으로 말하자면, 해시 함수는 문자열에 대해 숫자를 할당(mapping)한다.



해시 함수와 배열을 합치면 해시 테이블(hash table) 자료구조를 얻을 수 있다. 해시 테이블은 자료구조 그 자체에 더해 해시 함수라는 추가적인 논리구조를 가진다. 직접 메모리를 할당하는 배열, 리스트와 달리 해시 테이블은 해시 함수를 사용해 더 똑똑하게 어디에 원소를 저장할지 결정한다.



해시 테이블의 또 다른 이름은 해시 맵, 맵, 딕셔너리, 연관 배열(associative arrays)이다.



파이썬의 해시 테이블은 매우 익숙한 딕셔너리다. 딕셔너리를 떠올리면 쉽게 알 수 있듯, 해시 테이블은 key와 value를 가진다. 그리고 각 키는 해시 함수를 계산할 수 있다.



관련 포스팅 : 딕셔너리, .get( )



해시 테이블 (파이썬에서는 딕셔너리)의 장점은 다음과 같다.




class Node:
    def __init__(self, item):
        self.data = item
        self.next = None


    

  • 어떤 것과 다른 것 사이의 관계를 모형화할 수 있다.
    • 

  • 중복을 막을 수 있다. 
    • 

  • 서버에게 작업을 시키지 않고 자료를 캐싱할 수 있다. 
    • 








좋은 해시 함수는 충돌을 최소화한다. 충돌을 피하기 위해서는 낮은 사용률(load factor)이 필요하다. 해시 테이블의 사용률은 '(해피 테이블에 있는 항목의 수) / (해시 테이블에 있는 공간의 수)'로 계산한다.



좋은 해시 함수는 배열에 값을 고루 분포시킨 함수고, 나쁜 해시 함수는 값들이 뭉쳐져 있어 충돌이 자주 발생한다.





해시 테이블의 조회, 삽입, 삭제의 시간 복잡도는 O(1)이다. 상수 시간이라고도 한다. 즉 해시 테이블의 크기에 상관 없이 항상 똑같은 시간이 걸린다.



그래프 | graph



그래프는 연결의 집합을 모형화한 것으로, 정점(node 혹은 vertex)들이 간선(edge 또는 arc)으로 연결된 추상 네트워크다. 즉 그래프는 노드와 간선의 집합으로 정의되며 이를 수식으로 표현하면 G = (V, E) 와 같다. 정점은 여러 개의 다른 정점과 바로 이어질 수 있고 바로 이어진 정점을 이웃(neighbor)이라고 한다.



그래프는 방향이 있는 그래프(directed graph, 유향 그래프)와 방향이 없는 그래프(undirected graph, 무향 그래프)가 있다.  유향 그래프의 경우 순서가 있으므로 말단(leaf) 노드가 존재한다.



너비 우선 탐색 



너비 우선 탐색은 그래프를 대상으로 하는 탐색 알고리즘이다. 주로



유형 1 : 정점 A에서 정점 B로 가는 경로가 존재하는가?

유형 2 : 정점 A에서 정점 B로 가는 최단 경로는 무엇인가?



와 같은 질문에 대답하는 데 사용된다.