알고리즘별 요약 정리

방학기간 동안 알고리즘을 공부하면서 알고리즘별로 배웠던 내용을 정리하면 좋을 거 같아 글을 쓰게 되었다. 내용은 바킹독님의 강의를 토대로 정리하였으며 추후 내용이 추가될 예정이다.

✍️ 배열

메모리 상에 원소를 연속하게 배치한 자료구조

• 임의의 위치에 원소를 확인/변경 = O(1)
• 원소를 끝에 추가 = O(1)
• 마지막 원소를 제거 = O(1)
• 임의의 위치에 원소를 추가/임의의 위치의 원소 제거 = O(N)

✍️ 연결 리스트

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

• K번째 원소를 확인/변경하기 위해 O(K)가 필요함
• 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

연결 리스트의 종류

• 단일 연결 리스트 - 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트
• 이중 연결 리스트 - 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있는 리스트, STL에 연결 리스트가 있음
• 원형 연결 리스트 - 끝이 처음과 연결되어 있는 리스트

✍️ 스택

한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 상단의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

스택이 비어있는데 top을 호출하거나 pop을 호출하면 런타임 에러가 발생함에 주의하자.

✍️ 큐

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

스택과는 다르게 큐를 배열로 구현하면 삭제가 발생할 때마다 앞쪽에 쓸모없는 공간이 계속 생기게 된다. 이 문제를 해결하는 방법은 큐의 원소가 들어갈 배열을 원형으로 만드는 것이다. 마지막 index에서 다음 index로 갈 때 0번지로 다시 오도록 하면 되는데 이러한 큐를 원형 큐(Circular Queue)라고 부른다.

큐가 비어있는데 front, back, pop을 호출하면 런타임 에러가 발생함에 주의하자.

✍️ 덱

양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로는 불가능하지만 STL deque에서는 인덱스로 원소에 접근할 수 있다.

앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque을 사용하는 게 효율적이지만 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고싶을 땐 STL deque말고 STL vector를 쓰면 된다.

✍️ BFS

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복

자주 실수하는 점들을 짚어보면,

• 시작점에 방문했다는 표시를 남기지 않는다.
• 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다.
• 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.

✍️ DFS

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김
2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택이 빌 때까지 2번을 반복

Flood Fill은 BFS와 DFS 중에서 어느 것을 써도 상관없지만 거리 측정은 BFS만 할 수 있으니 DFS를 쓸 일이 없다. 그래프와 트리라는 자료구조를 배울 때 DFS가 필요하다.

✍️ 재귀

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

재귀 함수의 조건? 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base condition), 모든 입력은 base condition으로 수렴해야 함

재귀에 대한 정보

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 념겨줄지 명확하게 정해야 함
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄
• 한 함수가 자기 자신을 여러번 호출하게 되면 비효율적일 수 있음
• 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨

재귀로 풀어야 하는 문제라면 다음 3가지 Step을 기억하자.

1. 함수의 정의
2. base condition
3. 재귀식

✍️ 백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

보통 재귀적으로 구현이 된다.

✍️ 시뮬레이션

BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진 문제 상황을 구현하면 되는데 이때 구현이 빡세게 필요한 것들을 통틀어서 시뮬레이션 유형의 문제라고 한다.

✍️ 정렬

🔍 Bubble Sort

앞에서부터 인접한 두 원소를 보면서 앞의 원소가 뒤의 원소보다 클 경우 자리를 바꾸는 것을 반복하여 정렬한다.
시간복잡도는 O(N^2)이다.

🔍 Merge Sort

재귀적으로 수열을 나눠 정렬한 후 합치는 정렬이다.
시간복잡도는 O(NlgN)이다.
우선 순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬이 Stable Sort라고 하는데 Merge Sort가 이에 속한다.

🔍 Quick Sort

이름에서도 알 수 있듯이 일반적으로는 Quick Sort가 거의 모든 정렬 알고리즘보다 빨라서 각종 라이브러리의 정렬은 대부분 Quick Sort를 바탕으로 만들어졌다.
하지만, 기억해야할 점은 코딩테스트에서 STL을 못 쓰고 직접 정렬을 구현해야 한다면 Quick Sort는 절대 쓰면 안된다는 것이다.
Merge Sort처럼 재귀적으로 구현되는 정렬인데 매 단계마다 pivot이라고 이름 붙은 원소 하나를 제자리로 보내는 작업을 반복한다.
평균적으로 시간복잡도는 O(NlgN)이지만 최악의 경우 O(N^2)이다. 이러한 이유로 직접 정렬을 구현해야 한다면 Quick Sort를 절대 쓰면 안된다는 것이다.

🔍 Counting Sort

미리 큰 테이블을 만들어두고 수에 대응되는 원소의 값을 1 증가시켜서 정렬한다.
하지만 만약 수의 범위가 0에서 999,999,999 까지라고 하면 크기가 10억인 배열이 필요하므로 수의 범위가 어느 정도 한정적일 때에만 쓸 수 있다. 수의 범위가 대략 1000만 이하일 때에는 쓸 수 있다고 생각하면 된다.

🔍 Radix Sort

자릿수를 이용해서 정렬을 수행하는 알고리즘으로 Counting Sort를 응용한 알고리즘이라고 생각할 수 있다.
각 수들의 1의 자리만 보고 정렬을 하고, 그 후에는 10의 자리만 보고 정렬, 그 후에는 100의 자리, ... 이렇게 정렬을 수행한다.

Bubble Sort, Merge Sort, Quick Sort는 원소들끼리 크기를 비교하므로 Comparison Sort이고 Counting Sort, Radix Sort는 Non-comparison Sort이다.

✍️ 다이나믹 프로그래밍

여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

쉽게 설명하면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘을 말한다.

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

✍️ 그리디

지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
= 관찰을 통해 탐색 범위를 줄이는 알고리즘

이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.
3. 구현해서 문제를 통과한다.

현실적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
3. 믿음을 가지고 구현해서 문제를 통과한다.

절망적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 잘못된 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
3. 믿음을 가지고 구현했는데 계속 틀린다.

코딩테스트에서의 추천 전략

• 그리디 풀이를 100% 확신한다 -> 짜서 제출해보고 틀리면 빠르게 손절
• 100% 확신이 없다 -> 일단은 넘어가고 나중에 시작

✍️ 이분탐색

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

STL을 쓰지 않고 구현을 한다면 다음을 주의해야 한다.
주의사항
1. 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 한다.
2. 무한 루프에 빠지지 않게 mid 값을 정해야 한다.

중복 제거를 수행해주는 STL인 unique라는 함수가 있다. 우선 unique는 정렬된 배열에서 실행을 시켜야 하고, 중복이 제거된 원소들을 앞으로 모아준다. 뒤쪽에는 쓰레기 값들이 들어가고 쓰레기 값이 시작되는 구간을 return하는데 vector의 erase를 이용해서 뒤쪽을 날리면 된다.

vector<int> uni;
:
sort(uni.begin(), uni.end());
uni.erase(unique(uni.begin(), uni.end()), uni.end());

🔍 Parametric Search

조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

이분탐색을 수행할 변수를 가지고 함수를 세웠을 때 그 함수가 감소함수거나 증가함수여야 한다.