CS 학습 노트 - 알고리즘 코딩 테스트

@JHSHIN·2023년 4월 29일

CS 알고리즘 코딩테스트

📚 ‘이것이 취업을 위한 코딩테스트다 with 파이썬’ 도서를 학습하고 정리한 문서입니다.

시간 복잡도

파이썬 기준 - 1초에 2000만 번의 연산을 수행한다고 가정하면 크게 무리가 없음
시간 제한과 데이터의 개수를 확인한 후 풀이할 알고리즘의 시간 복잡도 예측

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법
탐욕적으로 문제에 접근했을 때 최적의 해를 찾을 수 있다는 보장이 있어야 함
문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 기준을 제시 → 정렬 알고리즘과 자주 짝을 이뤄 출제됨
e.g., 다익스트라 알고리즘

구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 완전 탐색
  - 모든 경우의 수를 다 계산하는 해결 방법
- 시뮬레이션
  - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법

탐색

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸
e.g., DFS, BFS
- 이것을 이해하기 위해 스택과 큐를 먼저 이해해야 함

자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조
스택 - LIFO 구조
- 파이썬 리스트로 구현
- append()와 pop() 메서드를 이용
큐 - FIFO 구조
- 파이썬 collections 모듈의 deque()로 구현
- append()와 popleft() 메서드를 이용

DFS

깊이 우선 탐색이라고도 부르며, 그래프에서 최대한 멀리 있는 노드를 우선적으로 탐색하는 알고리즘
스택 자료구조로 동작, 재귀 함수 이용
그래프는 노드와 간선으로 표현되며, 인접 행렬 방식과 인접 리스트 방식으로 구현
- 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  - 연결 노드에 접근시 속도 측면에서 유리
- 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식
  - 연결 노드에 접근시 메모리 측면에서 유리
동작 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리
3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
4. 2~3번의 과정을 반복

BFS

너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
큐 자료구조로 동작, 큐 자료구조 이용
동작 과정
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 반복

💡 Tip: 2차원 배열에서의 탐색 문제를 만나면, 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다.

정렬

데이터를 특정한 기준에 따라서 순서대로 나열하는 것
선택 정렬: 가장 작은 데이터를 선택해 앞에서부터 바꾸는 방법
- $O(n^2)$ , 데이터의 상태와 상관없이 모든 원소를 비교하고 Swap
삽입 정렬
- $O(n^2)$ , 데이터가 거의 정렬된 최선의 경우 $O(n)$
퀵 정렬: 피벗보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 평균적으로 $O(NlogN)$ , 데이터가 이미 정렬된 최악의 경우 $O(n^2)$
계수 정렬: 모든 데이터가 양의 정수일 때만 사용할 수 있는 매우 빠른 정렬 방법
- 데이터의 개수 N, 데이터의 최댓값 K일 때, 최악의 경우에도 $O(N+K)$ 를 보장

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
$O(N)$

이진 탐색

중간점을 기준으로 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
배열 내부의 데이터가 정렬되어 있어야만 사용이 가능
$O(logN)$

파라메트릭 서치

최적화 문제를 결정 문제(YES or NO)로 바꾸어 해결하는 기법
‘원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제’에 주로 이용
최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁힐 수 있다.

다이나믹 프로그래밍(동적 계획법)

큰 문제를 작게 나누고, 같은 문제라면 한 번만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
점화식을 세워 풀이
메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시킴
활용 조건
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션 vs 다이나믹 프로그래밍
- 메모이제이션(탑다운 방식) : 한 번 구한 결과를 메모리 공간에 저장해두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 (캐싱), 재귀 함수 이용
- 다이나믹 프로그래밍(바텀업 방식) : 전형적인 DP의 형태로, 반복문을 이용하는 방식. 결과 저장용 리스트는 DP 테이블이라고 부름

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘, “길 찾기” 문제라고도 불림
알고리즘 유형에는 다양한 종류가 있고, 상황에 맞는 알고리즘이 이미 정립되어 있음
다익스트라 최단 경로 알고리즘 : 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발해 다른 노드로 가는 최단 경로를 구해주는 알고리즘으로, “음의 간선”이 없어야 동작함.
- 그리디 알고리즘으로 분류되는데, 매번 ‘가장 비용이 적은 노드(아래 4번 과정)’를 선택해서 임의의 과정을 반복하기 때문이다.
1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화함(무한으로 초기화)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3 ~ 4번을 반복
- 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트(최단 거리 테이블)에 저장하며 리스트를 계속 갱신함
- 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인하며 나중에 더 짧은 경로를 찾으면 수정하는 방식
개선된 다익스트라 알고리즘 : 최단 거리가 가장 짧은 노드를 “우선순위 큐”를 이용해 더욱 빨리 찾는 방법, $O(ElogV)$
- 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 추출하는 자료구조로, 주로 힙 자료구조(최소 힙 or 최대 힙)를 사용해 구현함. 파이썬에서 PriorityQueue 혹은 heapq를 이용하고, 일반적으로 heapq가 더욱 빠르게 동작하며 기본적으로 최소 힙 구조로 이루어짐.
- 힙 : 완전 이진 트리의 일종으로, 부모 노드의 값이 자식 노드의 값보다 항상 큰 느슨한 정렬 상태를 유지함
- 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용 → ‘최단 거리가 가장 짧은 노드’를 선택하는 과정이 우선순위 큐를 이용함으로써 제거됨
플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘, $O(N^3)$ , 노드 개수만큼의 단계를 반복해 점화식에 맞게 2차원 리스트를 갱신함 ⇒ 노드의 개수가 적을 때 이용할 수 있음
- 2차원 리스트(인접 행렬)에 최단 거리 정보를 저장함
- 다이나믹 프로그래밍 방법을 이용
  - $Dab = min(Dab, Dak + Dkb)$
  - A에서 B로 가는 최소 비용 vs A에서 K를 거쳐 B로 가는 비용 중 작은 값으로 갱신

기타 그래프 이론 - 서로소 집합

서로소 집합 : 공통 원소가 없는 두 집합
서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조, union과 find의 2가지 연산으로 조작할 수 있음, 트리를 이용해서 집합을 표현

union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

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

find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

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

서로소 집합 계산 알고리즘
1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
  1. A와 B의 루트 노드를 각각 찾아서 A의 루트 노트를 B의 부모 노드로 설정
2. 모든 union 연산을 처리할 때까지 반복
서로소 집합을 활용한 사이클 판별
- 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있음 (방향 그래프는 dfs 이용)
- 각 간선을 확인하며 두 노드의 루트 노드를 확인
  - 루트 노드가 다르다면 두 노드 union
  - 루트 노드가 서로 같다면 사이클이 발생한 것

기타 그래프 이론 - 신장 트리

하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 → 트리의 성립 조건이기도 하므로 신장 트리라 부름
크루스칼 알고리즘 : N개의 도시 존재, 두 도시 사이에 도로를 놓아 전체 도시가 연결될 수 있도록 도로를 설치할 한다. 모든 도시를 연결할 때 최소 비용으로 연결하려면? → 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 ‘최소 신장 트리 알고리즘’이라고 함
대표적인 최종 신장 트리 알고리즘 = 크루스칼 알고리즘
그리디 알고리즘으로 분류됨
모든 간선에 대해 정렬을 수행한 뒤 가장 거리가 짧은 간선부터 집합에 포함하고 사이클을 발생시킬 수 있는 간선은 포함하지 않음
1. 간선 데이터를 비용에 따라 오름차순 정렬함
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
  1. 사이클 발생하지 않으면 포함
  2. 발생하면 포함 X
3. 모든 간선에 대해 2번을 반복
최종적으로 간선의 개수는 ‘노드 개수 - 1개’가 됨

기타 그래프 이론 - 위상 정렬

정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례로 수행해야 할 때 사용할 수 있는 알고리즘
방향 그래프의 모든 노드를 ‘방향성에 거스르지 않도록 순서대로 나열’하는 것
특정한 노드로 들어오는 간선의 개수인 ‘진입차수’를 알아야 함
1. 진입차수가 0인 노드를 큐에 넣음
2. 큐가 빌 때까지
  1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
  2. 새로 진입차수가 0이 된 노드를 큐에 넣음