꾸준히 개발하기

여러 곳에서 두루두루 쓰이는 파이썬의 자료구조에 대해서 정리해보자.

1. 해시

key-value 로 이루어진 데이터를 저장하는 자료구조. 조회가 매우 빠르다!

파이썬에서는 dict() 자료구조로 구현 가능하다.

딕셔너리는 다음과 같은 구조다. { key1: value1, key2:value2, ... }

빈 딕셔너리를 만들 때 {} 기호로 만들어주면 된다.

딕셔너리의 value에 접근하는 방법은 인덱스에 키 값을 적어주면 된다. 새로운 데이터를 추가할 때도 동일하다.

dictionary = {"name":"jibok"}
print(dictionary[name])
dictionary["age"] = 3

딕셔너리의 요소를 삭제할 때는 del 함수를 사용해주면 된다.

del dictionary["age"]

주의할 점은 key는 고유한 값이므로 중복되는 key값이 들어가게 되면 하나를 제외한 나머지 것들은 모두 무시된다. 고유한 key를 조회함으로써 value를 빠르게 가져오는 장점이 사라지는 행위이므로 하지 말자!

또한 key에 들어갈 수 있는 자료구조는 immutable한 요소만 가능하다. 가령 수정이 가능한 리스트는 안되고 수정이 안되는 튜플은 key로 쓸 수 있다. 

딕셔너리에서 제공하는 유용한 함수들은 다음과 같다.

• keys() : 모든 key를 리턴해준다. * dict_keys() 객체 자체를 돌려주는데 for문 등은 사용 가능하다. 만약 리스트로 값을 써야한다면 list(tmpDict.keys()) 로 변환해주자.
• values() : 모든 value를 리턴해준다.
• items() : key-value 쌍을 튜플로 묶은 값을 리턴해준다. 
• clear() : 안의 데이터 모두 지우기 (key, value 모두)
• get(key) : key에 대응되는 value값을 리턴해준다. 인덱스로 접근하는 것과 동일한 기능인데, 차이가 존재한다. 만약 없는 키값으로 접근했을 때 get 함수는 None을 리턴해주고, 인덱스는 에러를 발생시킨다.
• key in _ : 해당 딕셔너리 안에 key가 있는지 True/False값을 리턴해준다.

2. 스택

후입선출(Last In First Out)의 자료구조이다. 파이썬에서 기본적으로 제공해주는 list() 자료구조를 사용하면 된다.

자료구조의 가장 끝에서만 삽입, 삭제가 이루어진다.

• append() : 리스트의 맨 뒤에 삽입
• pop() : 리스트 맨 뒤의 요소를 꺼내어 리턴

* 맨 앞의 요소에 접근해서 빼려는 시도를 하면 O(N)의 시간복잡도를 가진다. 이런 경우 뒤에서 소개하는 deque 자료구조를 써야 시간 효율적이다.

3. 큐

선입선출(First In First Out)의 자료구조이다. 다양하게 구현하나 코딩테스트를 볼 땐 주로 collections 모듈의 deque를 사용하는 편이다.

from collections import deque
queue= deque()

위와 같이 선언하여 사용한다.

4. 덱

맨앞, 맨뒤에서 모두 자료의 삽입,삭제가 이루어질 수 있는 큐이다. collections 모듈의 deque를 사용한다. 하단의 메소드는 모두 O(1)의 시간복잡도를 가진다. 

• append() : 오른쪽 끝에 삽입
• appendleft() : 왼쪽 끝에 삽입
• pop() : 오른쪽 끝 요소를 꺼내어 리턴
• popleft() : 왼쪽 끝 요소를 꺼내어 리턴

from collections import deque

dq= deque()

dq.append(3)
dq.appendleft(2)
dq.pop()
dq.popleft()

5. 힙

최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료구조로 완전 이진트리이다.

자식 노드의 key 값 < 부모 노드의 key 값 : 최대 힙

자식 노드의 key 값 > 부모 노드의 key 값 : 최소 힙

우선순위에 따라 데이터가 정렬되어 있으므로, 가장 우선순위가 높거나/낮은 요소가 루트 노드에 존재한다. heapq 모듈을 사용한다. heapq 모듈은 리스트를 최소 힙처럼 다뤄준다. 따라서 빈 리스트를 선언하여 매번 넘겨줘야 한다.

• heapq.heappush( heap, item ) : heap에 item 삽입
• heapq.heappop( heap ) : heap에서 가장 작은 원소를 꺼내어 리턴

import heapq
hq = []
heapq.heappush(hq, 1)
heapq.heappop(hq)

기본적으로 heapq 모듈은 최소 힙으로 동작한다. 따라서 최대 힙을 구현해줄 때는 item에 '-'를 붙여 간단하게 구현한다.

여기까지 많이 쓰이는 자료구조는 한번 짚고 넘어간다. 문제 딱 보면 무슨 자료구조 써야되는지, 문법은 뭔지 더 이상 헷갈리지는 말자!

소수의 판별: 기본적인 알고리즘 성능 분석

• 2부터 𝑋-1까지의 모든 자연수에 대하여 연산을 수행해야 한다
  • 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X) 

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다
  • 예를 들어 16의 약수는 1, 2, 4, 8, 16이다
  • 이때 2 X 8 = 16은 8 X 2 = 16과 대칭이다
• 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다
  • 예를 들어 16이 2로 나누어떨어진다는 것은 8로도 나누어떨어진다는 것을 의미한다

import math

# 소수 판별 함수
def is_prime_number(x):
	# 1은 소수가 아니므로 예외처리
	if x == 1:
    	return False
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

에라토스테네스의 체

위의 방법은 특정 범위 내의 모든 소수를 구할 때는 비효율적이다. (실제로 백준 4948번을 위의 방식대로 풀면 시간초과가 난다)

효율적으로 소수를 구하기 위해 에라토스테네스는 범위에서 합성수를 모두 지우는 방식을 제안했다.

1. 1 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. ... (반복)

따라서 n까지의 수가 소수인지 아닌지 True, False로 저장해준 뒤 싹 돌리면 된다. 

import math

# 에라토스테네스의 체 방식 사용
def cntPrimeNums(start, end):
    # 1~end까지
    erato = [True] * end

    # 1은 소수가 아니므로 체크
    erato[0] = False

    for i in range(2, int(math.sqrt(end)) + 1):
        if erato[i] == True:
            for i in range(i + i, end, i):
                erato[i] = False
    cnt = 0
    for i in range(start, end):
        if erato[i] == True:
            cnt += 1
    return cnt

위 방법은 특정 범위 내에 소수가 몇개 있는지 체크해주는 코드다. 위의 코드는 start 이상 end 미만의 수를 중 소수를 체크한다! 만약 end까지 포함시키고 싶다면 수를 유의해서 넣어주자. 

n진수 → 10진수

* 결과값은 모두 string

python에서는 기본적으로 int() 라는 함수를 지원한다

int(string, base)

10진수 → n진수

2, 8, 16진수는 bin(), oct(), hex() 함수를 지원한다.

각 결과는 앞에 진법을 표시해서 문자열을 리턴하므로 생략하고 싶다면 [2:]를 붙여주면 되겠다.

물론 직접 코딩해도 된다.

def convert(n, q):
    result = ''

    while n > 0:
        n, mod = divmod(n, q)
        result += str(mod)
	
    # 나머지가 거꾸로 들어가므로 뒤집어줘야 정답
    return result[::-1]

위의 코드에서 divmod를 안쓰면 다음과 같다.

def convert10to2(num, n):
    data = ''
    while True:
        data += str(num % 2)
        num = num // 2
        if (num // 2) == 0:
            data += str(num % 2)
            break
    
    return data[::-1]

 divmod 쓰는 편이 깔끔하긴 하다 ㅎㅎ

DFS(Depth First Search, 깊이 우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수, 즉 그래프의 최대 경로가 정해져 있거나 예측 가능한 경우에 이용한다. 

DFS는 선택한 정점을 저장하기 위한 도구로 큐 대신 스택을 이용한다는 점에서 BFS와 차이를 보인다. 다만 스택을 직접 사용하지 않고, 그 원리를 이용하는 재귀 함수를 통해 구현하는 편이다.

def dfs(start):
	if(visited[start]): 
    	return
    visited[start] = True
    for node in adj[start]:
        if not visited[node]:
            dfs(node)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
start_node = input('시작 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


dfs(start_node)

다음 코드는 백준 11724번 풀이에서 가져와 약간 변형한 코드이다. 다만 보통 재귀 함수를 사용하는 경우 런타임 에러가 나는 경우가 잦아 다음의 코드를 통해 그 횟수를 직접 지정해주는 경우가 많다. 

import sys
sys.setrecursionlimit(10000)

BFS(Breadth First Search, 너비우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. BFS를 이용하여 최단거리, 최소비용과 같이 최솟값과 관련된 문제를 해결할 수 있는데, 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다. DFS는 그래프의 최대 경로(최대 깊이)가 예측할 수 있는 유한한 범위여야만 사용할 수 있지만, BFS는 모든 경로에 대한 동시 탐색이 가능하며 최대 경로를 몰라도 사용할 수 있다. 

from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)

#N:정점개수 M:간선개수
N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
start_node = input('검색을 시작할 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)

bfs(start_node)

백준 11724번 코드 중 일부를 가져와 수정했다. 해당 코드는 정점, 간선의 개수를 입력받고 사용자에게 직접 어떤 정점이 연결되어 있는지 입력받는다.

BFS의 경우 큐를 사용하는 경우가 대부분이다. 방문했던 노드를 체크해야 살펴볼 노드를 큐에 넣을 때 중복이 발생하지 않기 때문이다.

python에서는 큐를 list 타입으로 사용하는 경우가 많은데, 살펴본 노드를 제거할 때, list.pop() 함수를 사용하는 경우 시간 복잡도가 O(N)이라 시간 복잡도 면으로 매우 비효율적이다.

따라서 collections 라이브러리의 deque을 사용하여 시간을 절약하는 편이 좋다. deque는 양 끝에서 접근이 가능하며, append(), extend(), pop(), popleft() 등의 함수를 통해 자료를 넣고 뺄 수 있다. 

동적 계획법(DP)은 어렵거나 큰 문제를 간단하고 작은 여러개의 문제로 나누어 풀고 작은 문제의 답들을 이용하여 원래 문제의 답을 구하는 방식이다.

다음의 특징을 갖고 있다,

1. 최적 부분 구조
: 문제의 정답이 작은 문제에 대해서도 정답이어야 한다. 

2. 부분 문제 반복
: 문제를 여러 개의 작은 문제로 나눌 수 있으며, 나눈 작은 문제들을 전체 문제를 푸는 방법과 같은 방법으로 풀 수 있어야 한다.

DP 문제는 하향식, 상향식 두 가지 방법으로 접근할 수 있다.

하향식 방법의 경우 큰 문제를 풀 수 있는 작은 문제가 될 때까지 나눈 후, 작은 문제들을 풀어 얻은 정답들을 합쳐가며 큰 문제의 답을 구하는 방식으로, 주로 재귀 함수를 이용하여 구현한다.

상향식 방법은 가장 작은 문제부터 시작하여 큰 문제를 풀 수 있을 때까지 차례대로 문제들을 풀어나가는 방식으로 주로 반복문을 이용해 구현한다. 

정렬 알고리즘이란 원소들을 일정한 순서대로 열거하는 알고리즘이다.

자세한 설명에 들어가기 앞서, 해당 내용은 Big-O Complexity에 대한 기본적인 이해가 필요하므로 해당 복잡도에 대한 이미지를 첨부한다. 

알고리즘의 비교

아래에서는 대중적으로 다루는, 시간복잡도가 O(n^2), O(nlogn)인 정렬만 다루려고 한다.

1. 선택 정렬

현재 위치에 들어갈 값을 찾아 정렬하는 방법이다. 현재 위치에 저장될 값의 크기가 작은지/큰지에 따라 최소 선택 정렬(Min-selection sort)와 최대 선택 정렬(Max-selection sort)로 구분할 수 있다.

기본 로직은 아래의 그림과 같다.

1. 정렬되지 않은 인덱스의 맨 앞에서부터 배열 전체 중 가장 작은 값을 찾는다.

2. 가장 작은 값을 찾으면 그 값을 현재 인덱스의 값과 바꿔준다.

3. 다음 인덱스에서 1,2의 과정을 반복해준다.

배열 안의 원소 개수가 N개라고 할때 배열이 어떻게 되어있든지 간에 전체 비교를 진행하므로 시간 복잡도는 O(n^2)이다,

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 정렬 방법이다. 

기본 로직은 아래의 그림과 같다.

1. 삽입 정렬은 두번째 인덱스부터 시작하며, 현재 인덱스는 별도의 변수에 저장한다. 비교 인덱스는 현재 인덱스 -1로 잡는다.

2. 별도로 저장해둔 삽입을 위한 변수와 비교 인덱스의 배열 값을 비교한다.

3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

4. 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.

최악의 경우(역으로 정렬된 경우) 시간복잡도는 O(n^2)

배열이 이미 정렬되어 있는 경우 시간복잡도는 O(n)

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

3. 버블 정렬 (Bubble Sort)

매번 연속된 두개의 인덱스를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 방식이다.

기본 로직은 아래의 그림과 같다.

1. 두번째 인덱스부터 삽입정렬을 시작하여 현재 인덱스 값과 바로 이전의 인덱스값을 비교한다.

2. 만약 이전 인덱스가 더 크면 현재 인덱스와 바꿔준다.

3. 현재 인덱스가 더 크면 교환하지 않고 다음 두 연속된 배열값을 비교한다,

4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

배열의 구조가 어떻든 전체 비교를 진행하므로 시간복잡도는 O(n^2)

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

4. 합병 정렬 (Merge sort)

합병 정렬은 분할 정복(divide and conquer) 방식으로 설계된 방법이다.

* 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해나가는 방식이다.

** 분할은 배열의 크기가 1보다 작거나 같을 때까지 반복한다.

입력으로 하나의 배열을 받고, 이를 두 개의 배열로 계속 쪼개나간 뒤, 합치면서 정렬하여 최종적으로 하나의 정렬된 배열을 출력한다.

기본 로직은 다음과 같다. 

1. 현재 배열을 반으로 쪼갠다. (배열의 시작 위치와 종료 위치를 입력받아 둘을 더한 후 2로 나눈 뒤 그 위치를 기준으로 쪼갠다)

2. 분할한 배열의 크기가 0이나 1일때까지 반복한다.

** 합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.

기본 로직은 다음과 같다.

1. 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정한다.

2. i에는 배열 A의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.

3. A[i], B[j]를 비교한다. 오름차순의 경우 이 중 더 작은 값을 새 배열 C에 저장한다,

  A[i]가 더 큰 경우 A[i]의 값을 배열 C에 저장해주고 i++한다.

4. 이를 i/j가 둘 중 하나라도 각자 배열의 끝에 도달할 떄까지 반복한다.

5. 끝까지 저장을 못한 배열의 값을 순서대로 전부 C에 저장한다.

6. C배열을 원래 배열에 저장해준다.

이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.

합병 과정의 시간복잡도는 전체 배열의 길이에 비례하므로 O(n)

분할 과정의 시간복잡도는 O(logN)이다. 

( * 크기가 N인 배열 분할 시, 한번 분할하면 N/2, N/2 2개. 그 다음 분할시 N/4,N/4,N/4,N/4, 4개 이므로 로그함수) 

따라서 합병 정렬의 시간 복잡도는 O(NlogN)

공간복잡도는 두개의 배열을 사용하므로 O(2N)

5. 퀵 정렬 (Quick Sort)

퀵 정렬 역시 분할 정복을 이용하여 정렬을 수행한다.

기준이 되는 값 pivot을 하나 설정하는데, 이를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬한다. 이를 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된다.

기본 로직은 다음과 같다,

1. pivot으로 잡은 배열의 값 하나를 정한다. (보통 맨 앞/ 맨 뒤/ 중간 값/ 랜덤 값 중 하나)

2. 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장하는 right 변수를 생성한다,

3. right부터 비교를 진행한다. 비교한 배열 값이 pivot보다 크면 right를 하나 감소시키고 비교를 반복한다.

 * pivot보다 작은 값을 찾으면 반복을 중지한다.

4. 그 다음 left부터 비교를 진행한다. 비교한 배열 값이 pivot보다 작으면 leff를 하나 증가시키고 비교를 반복한다. 

* pivot보다 큰 값을 찾으면 반복을 중지한다.

5. left 인덱스 값과 right 인덱스 값을 바꿔준다,

6. 3~5 과정을 left<right일 때까지 반복

7. 위 과정이 끝나면 left값과 pivot 값을 바꿔준다,

8. 맨 왼쪽부터 left-1까지, left+1부터 맨 오른쪽까지 나눠 퀵 정렬을 반복한다.

퀵 정렬은 분할과 동시에 정렬을 진행한다,

퀵 정렬은 배열의 크기만큼 비교를 진행하며, 총 분할 깊이인 logN만큼 진행하므로, 시간복잡도는 O(NlogN)

다만 최악의 경우(배열이 이미 정렬되어 있는경우) 분할이 N만큼 일어나므로, 시간복잡도는 O(n^2)

-> 이를 방지하기 위에 중간값/랜덤값으로 pivot을 정하기도 함

최악의 경우 때문에 합병 정렬보다 느리다고 생각할 수 있지만, 이는 발생하기 쉽지 않은 경우이고 일반적으로 퀵 정렬이 합병 정렬보다 더 빠르다.