알고리즘

정렬

1. 퀵정렬

• 기본적으로 코테에서 많이 사용하는 정렬
• 기본 내장 정렬 함수와 비슷한 속도

2. 계수 정렬

• 특정 조건이 부합될때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
• 데이터의 개수가 N, 최대값이 K 일때 $O(N+K)$ 의 시간 복잡도
• 일반적으로 최대값과 최솟값의 차이가 1,000,000을 넘지 않을 떄 효과적

탐색

1. 순차 탐색

for i in range(n):
	array[i] == target:
		return i + 1

• 1차원 적으로 생각나는 탐색 방법으로 값을 하나씩 차례대로 확인하는 방법
• 시간만 충분하다면 값을 찾을 수 있다는 장점
• 시간 복잡도 : $O(N)$

2. 이진 탐색

# 재귀를 사용한 방법
def binary_search(array, target, start, end):
    if start > end:
        return
    mid = (end + start) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

# 반복문 사용 방법
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

array = [1, 3, 5, 9, 11, 13, 15, 17, 19]
print(binary_search(array, 11, 0, len(array) - 1))

• 반으로 쪼개면서 탐색하는 방법
• 찾으려는 데이타와 중간점 위치에 있는 데이터를 반복적으로 비교해서 찾는 방법
• 이진탐색을 하기 이전에 배열이 정렬되어 있어야 한다.
• 코테에 단골로 나오니까 외위두는걸 추천
• 탐색 범위가 2000만을 넘어가면 이진 탐색으로 접근해보길 권장
• 시간 복잡도 $O(logN)$

DFS

def dfs(graph, i, visited):
	visited[i] = True
	print(i, end = ' ')
	for j in graph[i]:
		if not visited[j]:
			dfs(graph, j, visited)

graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9
dfs(graph, 1, visited)

• 재귀 사용

BFS

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
		v = queue.popleft()
		print(v, end=' ')
		for i in graph[v]:
			if not visited[i]:
				visited[i] = True
				queue.append(i)

graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9
bfs(graph, 1, visited)

• 큐 사용

다이나믹 프로그램

• 항상 사용할 수는 없으며 다음 조건을 만족할 때 사용할 수 있다.
  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 예를 들어서 피보나치 수열이 위의 조건에 만족한다.

메모이제이션(Memoization) 기법

• 한 번 구한 결과를 메모리 공간에 메모해두고 필요시 다시 호출하는 방법
• 값을 저장하는 방법이므로 캐싱이라고도 한다.

# 피보나치 메모이제이션 방법
d = [0] * 100

def fibo(x):
	if x == 1 or x == 2:
		return 1

	if d[x] != 0:
		return d[x]
	d[x] = fibo(x - 1) + fibo(x - 2)
	return d[x]

• 일반적인 재귀 방법과 비교했을 때 속도차이가 매우 크다. x 가 크면 클 수록 그 차이가 매우 커진다.
• 피보나치 수열의 경우 메모이제이션 알고리즘의 시간 복잡도는 $O(N)$ 이다.
• 메모이제이션과 다이나믹 프로그래밍의 개념을 혼용하는 경우가 있는데 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로 다이나믹 프로그래밍과 별도의 개념이다.

탑 다운 / 보텀 업

• 이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스 코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식 이라고 한다.
• 반면 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 한다.
• 탑다운 방식은 하향식, 보텀업 방식은 상향식 이라고도 한다.
• 전형적인 다이나믹 프로그래밍 형태는 보텀업 방식이다.
• 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블 이라고 부른다.

최단 경로

최단 경로

다양한 그래프 알고리즘

다양한 그래프 알고리즘

자료구조

트리

• 대용량 데이터 처리에 적합한 자료구조
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드들 단말 노드라고 한다.
• 트리에서 일부 때어내도 트리 구조이며 이를 서브 트리라고 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

이진 탐색 트리

• 트리 구조에서 가장 간단한 형태
• 이진 탐색이 동작할수 있도록 고안된 자료구조
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

우선순위 큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.
• PriorityQueue 혹은 heapq 를 사용하는데 heapq 가 더 빠르니까 이걸 사용하는걸 권장.
• 첫 번째 원소 기준으로 우선순위를 설정하므로 (물건, 가치) 보다는 (가치, 물건) 과 같은 순서로 설정해야 정상적으로 작동한다.
• 최소 힙 : 값이 가장 낮은 데이터가 먼저 삭제
• 최대 힙 : 값이 가장 높은 데이터가 먼저 삭제
• 최소 힙을 최대 힙처럼 사용하려면 음수 부호( - ) 를 붙였다가 꺼낸 뒤 부호를 빼는 방식으로도 사용한다.
• 우선순위 큐 라이브러리는 최소 힙을 기반으로 한다.

힙

• 우선순위 큐를 구현하기 위하여 사용하는 자료 구조 중 하나.
• 최대 힙
• 최소 힙 : 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로 트리 자료구조에 속한다.

그래프

• 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조
• 구현 방법은 2가지이다.
  • 인접 행렬 : 2차원 배열을 사용하는 방식
  • 인접 리스트 : 리스트를 사용하는 방식

서로소 집합

• 공통 원소가 없는 두 집합
• 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조
• union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
• 서로소 집합 자료구조는 union-find 자료구조라고 불리기도 함
• 트리 자료구조를 이용하여 집합을 표현
• 시간 복잡도 $O(V + M(1 + log_{2-M/V}^V))$, 노트의 개수 V 이고 최대 V - 1 개의 union 연산과 M 개의 find 연산이 가능할 때이다.

# #특성 원소가 속한 집합을 찾기
# def find_parent(parent, x):
#     if parent[x] != x:
#         return find_parent(parent, parent[x])
#     else:
#         return x

# 경로 압축을 통해 시간복잡도를 줄인다.
def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    else:
        return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
parent = [i for i in range(v + 1)]

# union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, 1 + v):
    print(find_parent(parent, i), end=' ')
print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, 1 + v):
    print(parent[i], end=' ')
print()

• 서로소 집합을 이용하여 사이클 판별을 할 수 있다.

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    else:
        return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [i for i in range(v + 1)]

cycle = False
for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)

if cycle:
    print('사이클 발생')
else:
    print('사이클 발생안함')

신장 트리

• 그래프 알고리즘으로 자주 출제되는 유형
• 하나의 그래프가 있을 떄 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미함
• 트리도 성립 조건이다, 그래서 신장 트리라고 부른다.
  

기타

빠르게 입력 받기

import sys

input_data = sys.stdin.readline().rstrip()
print(input_data)

• 데이터 개수가 많으면 input 함수를 사용하면 동작 속도가 느려서 시간 초과 받을 수 있음
• 따라서 위와 같이 하는걸 권장
• rstrip() 을 꼭 해줘야 하는데 안하면 뒤에 개행이 있기 때문이다.

리스트 크기

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

시간 제한, 메모리 제한

• 파이썬 기준 1초에 20,000,000 번의 연산을 한다.
• 시간 제한 1초, 데이터의 개수 1,000,000 개 이면 시간 복잡 $O(NlogN)$ 이내의 알고리즘으로 풀어야한다.
• 실제로 N = 1,000,000 일때 $Nlog_2N$ 은 약 20,000,000 이다.