알고리즘

Insertion vs Merge vs Heap vs Quick

상명대학교 컴퓨터과학과 동아리 파느쎄 스터디할때 찍어놨던 유물

상명대학교 컴퓨터과학과 동아리 파느쎄 스터디할때 찍어놨던 유물

DFS (깊이우선탐색)

모든 노드를 방문할때 이방법을 선택

  • 최대한 깊이 내려간 뒤 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
  • 다른 노드로 넘어가기 전에 해당 깊이를 완벽하게 탐색
  • 경로의 특징을 저장해야 하는 문제에서 유리
  • 스택 혹은 재귀함수 이용
DFS 
1
2
3
4
5
6
7
8
9

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = '')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

BFS (너비우선탐색)

두 노드 사이의 최단 거리를 찾을 때 사용

  • 최대한 넓게 이동한 다음, 더이상 넓게 갈 수 없을때 아래로 이동
  • 미로찾기처럼 최단거리를 구해야하는 경우 유리
  • 아래 예시는 큐를 사용
BFS 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
	queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑아 출력
        v = deque.popleft()
        print(v, end = ' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

GREEDY (탐욕법)

최적의 해를 찾을 수 있을 때 사용

  • 시간복잡도에서 우위를 차지할 수 있음
  • 가장 큰 순서대로, 가장 작은 순서대로, 평균값부터 접근한다고 문제에서 주어졌을 때
  • 최적의 해 (아이디어)가 생각나지 않으면 DP나 Graph로 풀어야한다

BINARY SEARCH (이분탐색)

리스트를 절반씩 나누어가며 탐색하는 알고리즘, 낮은 시간복잡도

  • 순차 탐색으로는 O(N)의 시간 복잡도라면, 이분 탐색은 O(log N)이다.
  • 리스트의 중간값 mid 의 값이 key보다 작으면 좌측은 탐색할 필요가 없으므로 left = mid + 1이된다
  • left > right 라면 리스트에 원하는 데이터가 없다
  • mid의 값이 key와 같으면 key값을 찾았기 때문에 answer = mid 탐색을 종료한다.
이분탐색 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(target, data):
    left, right = 0, len(data) - 1
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid -1
    return None

이분탐색 재귀 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search_recursion(target, start, end, data):
    if left > right:
        return None
    mid = (left + right) // 2
    if data[mid] == target:
        return mid
    elif data[mid] > target:
        right = mid - 1
    else:
        left = mid + 1
    return binary_search_recursion(target, left, right, data)

DIJSTRA (다익스트라)

그래프에서 노드에서 다른 노드까지 최단 경로를 구하는 알고리즘

  1. 출발 노드와 도착 노드를 설정한다.
  2. 최단 거리 테이블을 초기화한다.
  3. 현재 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 택하여 방문 처리한다.
  4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 최단 거리 테이블을 업데이트한다.
  5. 3 ~ 4 의 과정을 반복한다.
  • 최단 거리 테이블은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록. N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.
  • 노드 방문 여부 체크 배열은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 최단 거리 테이블과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.
  • 간선의 개수가 E, 노드의 개수가 V 일때 시간 복잡도는 O(ElogV)
DIJSTRA 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import heapq

def dikjstra(start, distance, graph):
    q = []
    # 시작노드 정보 우선순위 큐에 삽입
    heapq.heappush(q, (0, start))
    # 시작노드->시작노드 거리 기록
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        # 큐에서 뽑아낸 거리가 이미 갱신된 거리보다 클 경우(=방문한 셈) 무시
        if distance[now]<dist:
            continue
        # 큐에서 뽑아낸 노드와 연결된 인접노드들 탐색
        for i in graph[now]:
            # 시작->node거리 + node->node의인접노드 거리
            cost = dist+i[1]
            # cost < 시작->node의인접노드 거리
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))



Python 함수

itertools

순열, 조합 사용시 사용하는 함수

combinations

  • combinations(iterable, r): iterable에서 원소 갯수가 r개인 튜플 리턴 (중복 제거)
combinations(iterable, r) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# combinations
from itertools import combinations
example = [1, 2, 3]
print(list(combinations(example, 1)))
# [(1,), (2,), (3,)]
print(list(combinations(example, 2)))
# [(1, 2), (1, 3), (2, 3)]
print(list(combinations(example, 3)))
# [(1, 2, 3)]
print(list(combinations(example, 4)))
# []

combinations_with_replacement

  • combinations_with_replacement(iterable, r): iterable에서 원소 갯수가 r개인 중복 포함 튜플 리턴
combinations_with_replacement(iterable, r) 
1
2
3
4
5
6
7

# combinations_with_replacement
from itertools import combinations_with_replacement
example = [1, 2]
print(list(combinations_with_replacement(example, 2)))
# [(1, 1), (1, 2), (2, 2)]
print(list(combinations_with_replacement(example, 3)))
# [(1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)]

permutations

  • permutations(iterable, r=None) : iterable에서 원소 갯수가 r개인 순열 튜플 리턴
permutations(iterable, r=None) 
1
2
3
4
5
6
7

# permutation
from itertools import permutations
example = [1, 2, 3]
print(list(permutations(example)))
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
print(list(permutations(example, 2)))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

product

  • product(*iterables, repeat=1) : 여러 iterable의 데카르트곱 튜플 리턴
product(*iterables, repeat=1) 
1
2
3
4
5
6
7
8
9

# product
from itertools import product
number = [1, 2]
alpha = ['a', 'b']
fruit = ['apple', 'banana']
print(list(product(number, alpha)))
# [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]
print(list(product(number, alpha, fruit)))
# [(1, 'a', 'apple'), (1, 'a', 'banana'), (1, 'b', 'apple'), (1, 'b', 'banana'), (2, 'a', 'apple'), (2, 'a', 'banana'), (2, 'b', 'apple'), (2, 'b', 'banana')]

collections

자료형(list, tuple, dict)를 이용할때 확장된 기능을 사용할 수 있는 기본 라이브러리

deque

스택이나 큐를 이용하여 알고리즘 풀때 사용하며 속도가 list 보다 빠르다. 따라서 push, pop을 많이 사용해야하는 문제에서 사용하기 적합하다.

리스트 자료형으로 구현하기 복잡한 것

  • deque.popleft(): 데크의 왼쪽 끝 원소 리턴하면서 데크에서 삭제
  • deque.rotate(num): 데크를 num만큼 이동한다 (양수면 오른쪽, 음수면 왼쪽)

리스트 자료형으로도 구현하기 쉬운 것

  • deque.append(item): item을 데크의 오른쪽 끝에 삽입 (list append)
  • deque.extend(array): 배열을 순회하면서 데크의 오른쪽에 추가 (list extend)
  • deque.extendleft(array): 배열을 순회하면서 데크의 왼쪽에 추가 (list extend)
  • deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입 (list insert)
  • deque.pop(): 데크의 오른쪽 끝 원소 리턴하면서 데크에서 삭제 (list pop)
  • deque.remove(item): item을 데크에서 삭제 (list del)

Counter

  • 리스트가 주어졌을때 중복되지 않는 원소들과 갯수를 딕셔너리 형태로 리턴함
Counter 
1
2
3

from collections import Counter
print(Counter(["a", "b", "c", "a", "b"]))
# Counter({'a': 2, 'b': 2, 'c': 1})

defaultdict

  • 딕셔너리값의 초기값을 지정할 수 있다. 처음 선언할때 어떤 자료형을 사용할 건지 입력받아야한다.
  • keyError 를 우회할 수 있다.
defaultdict 
1
2
3
4
5
6
7
8

from collections import defaultdict
example = defaultdict(list)
print(example['list'])
# []

example = {}
print(example['list'])
# keyError 'list'

sort

sorted() vs sort()

  • sorted(X) " 원본을 변형시키지 않고 정렬된 리스트를 리턴함
  • X.sort() : 원본을 변형시켜줌, 리턴값 없음
  • Params : sort와 sorted 모두 동일한 파라미터를 갖을 수 있다. 파라미터는 key 와 reverse가 있으며 lambda와 함께 사용하요 내림차순, 오름차순, 배열의 몇번째 원소 기준으로 정렬할지 정할 수 있다.
  • 문자는 알파벳순(가나다순), 숫자는 오름차순이 기본
sort 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

example = [1, 4, 3, 2]
print(sorted(example), example)
# [1, 2, 3, 4]  [1, 4, 3, 2]
print(example.sort(), example)
# None          [1, 2, 3, 4]

# reverse 를 이용한 내림차순
print(sorted(example, reverse=True)).
# [4, 3, 2, 1]

# key 를 이용한 2차원 배열(튜플) 정렬
example = [[1, 3], [2, 2], [3, 1]]
# 첫번째 배열 원소를 이용해 정렬
print(sorted(example, key= lambda x : x[0]))
# [[1, 3], [2, 2], [3, 1]]
# 두번째 배열 원소를 이용해 정렬
print(sorted(example, key= lambda x : x[1]))
# [[3, 1], [2, 2], [1, 3]]

# key와 reverse를 동시에 이용할 수 도 있다.
print(sorted(example, key= lambda x : x[0], reverse=True))
# [[3, 1], [2, 2], [1, 3]]

zip

iterable한 자료형을 순서대로 묶어서 리턴해준다.

  • 되도록 zip할 자료형의 갯수가 같을때 사용 (같지 않을 경우 최소 길이의 자료형으로 리턴한다.)
  • 자료형은 리스트나 튜플같은 반복 가능한 자료형을 의미한다.
zip 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

print(zip([1, 2, 3], ['a','b','c']))
# <zip object at 0x100a76e48>

print(list(zip([1, 2, 3], ['a','b','c'])))
# [(1, 'a'), (2, 'b'), (3, 'c')]

print(list(zip([1, 2, 3], ['a','b'])))
# [(1, 'a'), (2, 'b')]

# zip을 이용한 for문 예시, List 형태로 변환하지 않아도 됨
example = zip([1, 2, 3], ['a','b','c'])
for number, alpha in example:
    print(number, alpha)
# 1 a
# 2 b
# 3 c

# 딕셔너리 자료형 생성 예시
print({ number:alpha for number, alpha in example })
# {1: 'a', 2: 'b', 3: 'c'}

re

정규식

  • re.sub(pattern, replacement, string) : 정규식 패턴과 일치하는 내용을 replacement로 변경
  • \uAC00-\uD7A30 : 모든 한글 음절(가-힣)
  • a-z : 영어 소문자
  • A-Z : 영어 대문자
  • 0-9 : 숫자
  • \s : 띄어쓰기
re 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import re
example = 'aㄱ1*bㄴ2@'

# 특수문자 제거
print(re.sub(r"[^\uAC00-\uD7A30-9a-zA-Z\s]", "", example))
# a1b2

# 숫자만 가져오기
print(re.sub(r"[^0-9]", "", example))
# 12

# 숫자만 제거
print(re.sub(r"[0-9]", "", example))
# aㄱ*bㄴ@

# 숫자를 `~`로 변경
print(re.sub(r"[0-9]", "~", example))
# aㄱ~*bㄴ~@

최소공배수, 최대공약수

파이썬 math 라이브러리 이용하면 쉽게 구할 수 있다

최소공배수, 최대공약수 
1
2
3
4
5
6
7
8
9

# python 3.9 미만
from math import gcd
gcd(a, b)           # 최대공약수
a * b // gcd(a, b)  # 최소공약수

# python 3.9 이상
from math import gcd, lcm
gcd(a, b) # 최대공약수
lcm(a, b) # 최소공약수

진수

내장 함수 bin을 이용하면 쉽게 구할 수 있음.

최소공배수, 최대공약수 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

a = bin(4)
# a = 'ob100'
b = int(a, 2)
# b = 4

# 혹은 직접 구현할 수도 있음
def makeBin(len):
    result = []
    while len != 0:
        if len % 2 == 1:
            result.append("1")
            len = (len - 1) / 2
        else:
            result.append("0")
            len = len / 2
    return result