[Algorithm] 코딩테스트 대비 Cheat Sheet with Python
코딩테스트에 필요한 기본적인 알고리즘 컨셉들에 대해서 빠르게 훑어볼 수 있는 자료를 만들어 보았다.
Table of Contents
- 탐색 알고리즘
- DFS
- BFS - 정렬 알고리즘
- Selection Sort
- Quick Sort - 탐색 알고리즘
- Binary Search - 다이나믹 프로그래밍
- Top down
- Bottom up - 최단경로 알고리즘
- Dijkstra
- Floyd-Warshall
탐색 알고리즘
그래프를 탐색하는 일반적인 방법은 DFS와 BFS가 있다.
그래프에서 모든 노드를 방문하고자할 때는 깊이 우선 탐색, DFS가 좀 더 선호될 수 있다. DFS, BFS 어떤 것이든 상관없기는 하지만, 구현면에서 DFS가 조금 더 간단하다.
두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶을 때는 너비 우선 탐색인 BFS가 일반적으로 더 낫다.
지구상에 존재하는 모든 친구 관계를 그래프로 표현한 뒤 A와 B 사이의 경로를 찾는 경우를 생각해보면 왜 더 나은지 쉽게 생각해볼 수 있다.
그 외 양방향 탐색은 출발지-목적지 사이 최단 경로를 찾을 때 사용될 수 있다.
DFS
- Depth First Search. 깊이 우선 탐색.
- Data Structure: Stack -> 재귀함수로 구현하기 좋음
- Time complexity: O(N)
1. 탐색 시작 노드를 스택에 삽입 후 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
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
- Breadth First Search. 너비 우선 탐색
- Data Structure: Queue (python deque library 활용)
- Time complexity: O(N). but, 일반적으로 DFS보다 수행시간은 더 빠르다.
- 탐색 시작 노드를 큐에 삽입하고 방문처리
- 큐에서 노드를 꺼내 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 한다.
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
# node visited
visited[start] = True
# loop till queue is empty
while queue:
# visted node 'v'
v = queue.popleft()
print(v, end=' ')
# v 노드에 연결된 노드들 투입 -> 방문 안한 노드만 queue에 추가
for i in graph[v]:
if not visited[i]:
queue.append(i)
# print(queue) # queue안에 뭐있나
visited[i] = True정렬 알고리즘
대부분 이미 구현된 내부 정렬 라이브러리를 활용하게되므로, 직접 정렬 알고리즘을 구현할 일은 많지 않겠지만 각 알고리즘의 특징정도는 알아놔야 본인이 작성한 알고리즘의 시간 복잡도를 계산할 수 있을 것이다.
참고로 Python의 sorted 함수는 내부적으로 병합정렬을 사용한다.
Time Complexity: O(N²)
- Bubble Sort(버블정렬): 첫 원소부터 순차로 현재 원소가 그 다음 원소보다 크면 두 원소를 바꿈
- Selection Sort(선택정렬): 배열을 선형 탐색(linear scan)하여 가장 작은 원소를 앞으로 보냄
- Insertion Sort(삽입정렬): 적절한 위치에 삽입(insertion)하는 정렬. 필요할 때만 위치를 바꾸므로 데이터가 정렬되어있을 때는 효율적임.
Time Complexity: O(NlogN) ~ O(N²)
- Quick Sort(퀵정렬): 임의의 기준 대비 큰 수와 작은 수로 나누는 방식
Time Complexity: O(NlogN)
- Merge Sort(병합정렬): 배열을 절반씩 나누어 각각 정렬하고 합해서 다시 정렬
구현이 가장 간단한 선택 정렬과, 가장 보편적으로 사용되는 퀵 정렬 위주로 조금 더 자세히 보자.
Selection Sort
- 선택 정렬 : 가장 기초적인 정렬 알고리즘.
- Time Complexity: O(N²)
가장 작은 데이터를 선택(Selection)해 맨 앞에 있는 데이터와 바꾸고, 그 다음 데이터를 선택해 두번째 데이터와 바꾸고.. 이 과정을 반복한다.
array = [2, 3, 1, 4]for i in range(len(array)):
min_index = i # index of the smallest element
for j in range(i+1, len(array)):
min_index = j
array[i], array[min_index] = array[min_index], array[i] # swap
대부분의 다른 언어에서는 두 원소간 값 변경을 위해서 임시 변수를 만들어야 하지만, 파이썬에서는 간단하게 스와핑 할 수 있다.
array[i], array[min_index] = array[min_index], array[i] # swap특정한 리스트에서 가장 작은 데이터를 찾도록 직접 구현해야하는 경우가 있으므로 선택정렬의 소스에 익숙해지는 것이 좋다.
Quick Sort
- 퀵정렬. 가장 많이 사용되는 알고리즘. 분할정복(Divide and Conquer) 방식.
- Time Complexity : 평균 O(NlogN), 최악 O(N²)
- Space Complexity : O(log N)
퀵 정렬은 임의의 기준 데이터를 설정하고 분할정복(Divide and Conquer) 해가는 방식으로 동작한다.
기준이 되는 수를 정하고 이보다 큰 수와 작은 수를 교환한 후 리스트를 반으로 나눈다.
여기서 사용되는 기준을 피벗(pivot)이라 한다.
array = [2, 3, 1, 4]def quick_sort(array):
#quit if list has one or less elements
if len(array) <= 1:
return array
pivot = array[0] # first element as pivot
tail = array[1:] # list accept pivot left = [x for x in tail if x <= pivot] # left side
right = [x for x in tail if x > pivot] # right side return quick_sort(left_side) + [pivot] + quick_sort(right_side)
탐색 알고리즘
Binary Search
- Time Complexity : O(logN)
이진 탐색은, 배열 내부의 데이터가 정렬되어 있어야 사용 가능하다. 찾으려는 데이터와 중간점(middle) 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
재귀로도 구현이 가능하지만 여기서는 반복문 형태로 구현한 Binary Search만 보면:
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 Noneresult = binary_search(array, target, 0, n - 1)
다이나믹 프로그래밍
메모리 공간을 더 사용해서 연산 속도를 증가시킬 수 있는 방법 중 대표적인 것이 다이나믹 프로그래밍이다.
다이나믹 프로그래밍을 적용할 수 있는 문제는 다음과 같은 조건을 충족해야 한다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
다이나믹 프로그래밍은 기본이 되는 작은 문제를 식으로 쓴 점화식을 그대로 코드로 옮겨서 구현하면 된다. 즉 점화식을 찾아내는 것이 관건이다.
피보나치 수열은 다이나믹 프로그래밍을 만족하는 대표 문제다. 순수하게 재귀함수로 풀어내면 2의 n승이 되어, 100 자리까지도 실제적으로 컴퓨터로 계산할 수 없는 수가 되어 버린다. 이를 다이나믹 프로그래밍으로 O(N) 문제로 풀어낼 수 있다.
피보나치의 점화식: Fn = Fn-1 + Fn-2
- 재귀를 이용하여 큰 문제부터 작은 문제를 해결해나가는 Top-Down 방식, 메모이제이션(Memoization) 방식으로 풀 수 있거나,
# Memoization 초기화
d = [0] * 100
def fibo(x)
# base case
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]- 반복문을 이용하여 작은 문제부터 답을 도출하는 Bottom-Up(보텀업) 방식으로 풀어볼 수 있다.
Bottom-Up 방식의 풀이를 보면:
# initiate DP Table
d = [0] * 100
# both first Fibonacci number and second fibonacci number are 1
d[1] = 1
d[2] = 1
n = 99
# bottom up dynamic programming
for i in range(3, n+1):
d[i] = d[i - 1] + d[i - 2]위 방식에서 사용되는 결과 저장용 리스트를 ‘DP Table(Dynamic Programming Table)’이라고 부른다.
주어진 문제가 다이나믹 프로그래밍 유형인지를 파악하는 것이 중요하다. 완전 탐색 알고리즘으로 먼저 접근해보고, 시간이 매우 오래 걸린다면 다이나믹 프로그래밍으로 적용할 수 있는지 해결하고자 하는 문제들의 중복 여부를 확인해보자.
최단경로 알고리즘
그래프 문제 중 최단경로 알고리즘을 풀어내기 위해서는 다익스트라, 플루이드 워셜 알고리즘 등의 활용이 필요할 수 있다.
이러한 그래프 문제는 상대적으로 더 난이도가 있는 편이며, 이것만으로도 내용이 꽤 되어서 별도로 아래 글에 이어서 정리했다:
[Algorithm] 최단경로 알고리즘 with Python(다익스트라, 플루이드워셜)
코딩테스트와 과제에 대한 단상
요즘은 단순히 알고리즘 테스트보다 훨씬 더 시간과 공을 들여서 풀어야하는 1–3주 짜리 과제를 내는 회사도 점차 늘어가는 것 같다. 특히 데이터 엔지니어링 분야에서는 데이터 파이프라인과 데이터 웨어하우스를 스크래치부터 구축하는 과제를 내는 회사들이 종종 있다. 사실 알고리즘 문제풀이보다 회사 입장이나 지원자 입장에서 서로간에 실력을 깊이있게 평가하고, 깊이있게 보여줄 수 있는 건 과제 형태라고 생각한다. 그럼에도 불구하고 과제를 적용하기 힘든 건, 회사 입장이나 지원자 입장에서 너무 많은 시간을 써야하기 때문이다.
한번은 3주간 걸리는 과제를 해본 경험이 있다. 3주간 주말 내내, 퇴근후 내내 모든 시간을 투입해야 했다. 그런데 사실 그 당시 AWS를 실무에서 써보기 전이라, AWS에 아키텍처도 원없이 구성해보고 아주 재밌게 하긴 했는데(내 돈 한푼 안쓰고!), 만약 2개의 회사를 동시에 진행하는데 둘 다 그런 수준의 과제가 나오면 아마 둘 중 하나는 기권해야만 할것이다. 아니, 사실 회사 프로젝트가 바쁜 시기와만 겹쳐도 하나도 제대로 풀 수 없었을 것이다.
반면 코딩테스트는 일반적으로 한시간~수시간 내외의 시간만을 필요로 하고, 상대적으로 짧은 시간 안에 지원자의 문제해결능력과 알고리즘, 자료구조에 대한 지식을 어느 정도 평가해낼 수 있다.
이런 면에서 코딩테스트는 최고로 효과적이진 않지만 대신 꽤 효율적으로 지원자의 기본적인 문제해결능력을 평가하는 방법이라고 생각한다.
물론 이에 대한 반론도 만만찮다. 특히 경력 개발자의 경우 알고리즘 문제풀이 능력보다 실무 경험이 중요한 것 아니냐는 의문도 나름 타당하다. 이러한 사례 중 재미있는 사례로 Homebrew의 개발자인 Max Hawell이 구글 면접에서 inverting a binary tree 문제를 풀지 못해 떨어진 사례를 들기도 한다.
개인의 의견이 어떻든, 대부분의 기업이 소프트웨어 엔지니어 채용 시 코딩테스트를 보는 이상 우리는 준비를 해야 한다. 종종 보는 유튜브 채널의 운영자분이 코딩테스트 관련 좋은 책(이것이 코딩 테스트다)을 최근 발간하셨고, 책을 보는 김에 요점만 간단히 정리해보았다.
Reference
나동빈, 이것이 코딩테스트다(2020), 한빛미디어
G.L.Mackdowell, Cracking the coding interview(코딩인터뷰 완전분석), 인사이트
