🟢 학습 방향: Part 2~3 내용을 집중 학습합니다.

📋 주요 목차

Part 2. 주요 알고리즘 이론과 실전 문제

• Chapter 3. 그리디
  
• Chapter 4. 구현
  
• Chapter 5. DFS/BFS
  
• Chapter 6. 정렬
  
• Chapter 7. 이진 탐색
  
• Chapter 8. 다이나믹 프로그래밍
  
• Chapter 9. 최단 경로
  
• Chapter 10. 그래프 이론
  

Part 3. 알고리즘 유형별 기출문제

• Chapter 11. 그리디 문제
  
• Chapter 12. 구현 문제
  
• Chapter 13. DFS/BFS 문제
  
• Chapter 14. 정렬 문제
  
• Chapter 15. 이진 탐색 문제
  
• Chapter 16. 다이나믹 프로그래밍 문제
  
• Chapter 17. 최단 경로 문제
  
• Chapter 18. 그래프 이론 문제
  
• Chapter 19. 2020년 상반기 삼성전자 기출문제
  

🪴 학습 요약 및 소감

Chapter 3. 그리디

그리디 알고리즘은 이름과 같이 탐욕적으로 문제를 푼다. 현재 상황에서 가장 좋은 것만 고르는 방법이다. 문제를 보고 어떤 규칙을 따라야 가장 좋은 선택일지 아이디어를 찾아야 한다.
예를 들어, 거스름돈 문제에서 '가장 큰 화폐 단위부터' 돈을 거슬러 준다. 어떤 N이 1이 되도록 1을 빼거나 K로 나누는 과정을 반복하는 경우에, '최대한 많이 나누는 것'이 빠르게 수를 감소시킬 방법임을 인지해야 한다. 이러한 아이디어를 바탕으로, 가능한 케이스를 나누어 코드를 작성한다.

(2025.08.10)

Chapter 4. 구현

구현에서는 '완전 탐색'과 '시뮬레이션' 유형을 다룬다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 유형이다.
완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다. 일반적으로 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.
시뮬레이션 문제는 길고 문제를 바르게 이해하여 소스코드로 옮기는 과정이 중요하다. 특히 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 좋다.

(2025.08.16)

Chapter 5. DFS/BFS

탐색은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. DFS와 BFS는 스택과 큐 자료구조, 재귀 함수를 바탕으로 한다. 스택은 후입선출, 큐는 선입선출 구조이다. 재귀 함수는 자기 자신을 다시 호출하는 함수를 의미한다. 깊이 우선 탐색(Depth-First Search, DFS)은 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
그래프는 두 가지 방식으로 표현할 수 있다. 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이고, 인접 리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. 인정 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 반면에 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 인접 리스트 방식은 두 노드가 연결되어 있는지에 대한 정보를 얻으려면 데이터를 하나씩 확인해야 해서 속도가 느리다.
관행적으로 번호가 낮은 노드 순서부터 처리하도록 구현하는 편이다.

DFS 동작 과정

1. 탐색 시작 노드를 스택에 삽입 & 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 스택에 삽입 & 방문 처리 OR 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

BFS 동작 과정

1. 탐색 시작 노드를 큐에 삽입 & 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 & 방문 처리
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

(2025.08.18)

Chapter 6. 정렬

정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 정렬은 다음 장에서 다루는 이진 탐색의 전처리 과정이기도 하다. 다양한 정렬 알고리즘 중에서 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 다룬다.

선택 정렬

무작위 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.

• 시간 복잡도: $N-1$번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 연산 횟수는 $N + (N-1) + (N-2) + ... + 2$이고, 근사치로 $N * (N+1) / 2$ 번의 연산을 수행한다고 가정할 수 있다. 이는 $(N^2 + N) / 2$ 로 표현할 수 있고 시간 복잡도는 O($N^2$)이 된다.

삽입 정렬

특정한 데이터를 적절한 위치에 삽입하기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다. 특히 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 삽입 정렬은 두 번째 데이터부터 시작한다. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

• 시간 복잡도: 삽입 정렬은 반복문이 2번 중첩되어 시간 복잡도가 $O(N^2)$이다. 단, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하여, 최선의 경우 $O(N)$의 시간 복잡도를 가진다.

퀵 정렬

퀵 정렬은 정렬 알고리즘 중 가장 많이 사용된다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 교환하기 위한 기준을 '피벗(Pivot)'이라고 표현한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬을 구분한다.
이 책에서는 대표적인 분할 방식인 호어 분할(Hoare Partition)을 소개한다. 먼저 리스트의 첫 번째 데이터를 피벗으로 설정한다. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이를 반복하다 보면 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈리는 경우가 있다. 이 경우에는 작은 데이터와 피벗의 위치를 서로 변경한다. 피벗이 이동한 상태에서 왼쪽 리스트의 데이터는 모두 피벗보다 작고, 오른쪽 리스트의 데이터는 모두 피벗보다 크다는 특징이 있다. 이 작업을 분할이라고 한다. 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.

• 시간 복잡도: 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면? 데이터의 개수가 $N$개일 때 높이는 약 $log N$이라고 판단할 수 있다. 퀵 정렬은 평균적으로 시간 복잡도가 $O(NlogN)$이지만 최악의 경우 시간 복잡도가 $O(N^2)$이다. 퀵 정렬은 다른 정렬들과 달리, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.

계수 정렬

계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 예를 들어, 데이터 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 $O(N+K)$를 보장한다. 단, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. (일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다.)
인덱스가 데이터의 모든 범위를 포함할 수 있는 리스트를 선언한다. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다. 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. 이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체이다. 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.

• 시간 복잡도: 데이터의 개수는 N, 데이터 중 최대값의 크기는 K일 때, 시간 복잡도는 $O(N+K)$이다. 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행하기 때문이다.
• 공간 복잡도: 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어, 데이터가 0과 999,999, 단 2개만 존재하더라도 리스트의 크기가 100만 개가 되도록 선언해야 한다. 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 계수 정렬의 공간 복잡도는 $O(N+K)$이다.

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식으로 만들어졌다.

• 시간 복잡도: 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 $O(NlogN)$을 보장한다.

(2025.08.19)

Chapter 7. 이진 탐색

순차 탐색

순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.

이진 탐색

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

• 이진 탐색의 시간 복잡도: 이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다. 단계마다 2로 나누는 것과 동일하므로 연산 횟수는 $log_2N$에 비례한다고 볼 수 있다. 빅오 표기법에 따라 $O(logN)$으로 표현한다. 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다.
  

이진 탐색 트리

이진 탐색 트리는 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 부모 노드보다 왼쪽 자식 노드가 작고, 부모 노드보다 오른쪽 자식 노드가 커야 한다. 루트 노드부터 방문하며, 루트 노드와 찾는 원소값을 비교하여 한쪽 서브 트리에 대해서만 탐색을 수행하면 된다. 이를 반복하여 원하는 원소값을 찾는다.

빠르게 입력받기

입력 데이터의 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다. sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다. 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출하여 공백 문자를 제거해야 한다.

(2025.08.19)

Chapter 8. 다이나믹 프로그래밍

최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터로 해결하기 어려운 문제이다. 따라서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이 필요하다. 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법이며, 동적 계획법으로 표현하기도 한다. 구체적으로는 탑다운, 보텀업, 메모이제이션 기법이 사용된다.
피보나치 수열의 점화식 $a_n = a_{n-1} + a_{n-2},\ a_1 = 1,\ a_2 = 1$을 단순히 재귀 함수로 구현하면 문제가 발생한다. f(n) 함수에서 n이 커질수록 수행 시간이 기하급수적으로 늘어난다. $O(2^N)$의 지수 시간이 소요된다. 또한, 이미 한 번 계산한 함수를 호출할 때마다 다시 계산하는 비효율적인 특징이 있다. 이러한 문제는 다이나믹 프로그래밍을 통해 해결할 수 있고, 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
   

메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 캐싱이라고도 한다. 피보나치 수열에 메모이제이션 기법을 적용하면, 99번째 피보나치 수를 구하는 경우에도 빠르게 정답을 도출할 수 있다. 재귀적으로 수행을 하다가, 이미 계산한 적이 있는 값은 리스트에서 바로 가져오기 때문이다. f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)을 푸는 데 사용되는 방식으로 이어지므로, 다이나믹 프로그래밍을 적용하면 시간 복잡도는 $O(N)$으로 감소한다.

• Top-Down: 큰 문제를 해결하기 위해 작은 문제를 호출
  E.g. 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드 작성
• Bottom-Up: 작은 문제부터 차근차근 답을 도출
  E.g. 단순 반복문
  
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부른다. 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.
  

(2025.08.20)

Chapter 9. 최단 경로

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등이 존재한다. 보통 그래프를 이용해 표현한다. 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 3가지가 대표적이다.

다익스트라(Dikstra) 최단 경로 알고리즘

그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 음의 간선이 없어야 정상적으로 동작한다. 매번 '가장 비용이 적은 노드'를 선택해서 아래 과정을 반복하므로 그리디 알고리즘으로 분류된다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다. (최단 거리를 무한으로 초기화)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3번과 4번을 반복한다.
   

• '간단한 다익스트라 알고리즘'의 시간 복잡도: V는 노드의 개수일 때, $O(V^2)$이다. $O(V)$번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문이다.
  

노드의 개수가 10,000개를 넘어가는 문제라면 '개선된 다익스트라 알고리즘'을 이용해야 한다. 매번 최단 거리 테이블을 모든 원소를 앞에서부터 하나씩 탐색해야 했는데, 이를 선형적으로 찾는 것이 아니라 더욱더 빠르게 찾는다. 특정 노드까지의 최단 거리에 대한 정보를 힙 자료구조에 담아서 처리하므로, 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾는다. 이때 선형 로그 시간이 아닌 로그 시간이 걸린다.
힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다. 우선순위 큐 라이브러리의 PriorityQueue 또는 heapq를 사용할 수 있다.

• '개선된 다익스트라 알고리즘'의 시간 복잡도: 최악의 경우에도 시간 복잡도 $O(ElogV)$를 보장한다. V는 노드의 개수이고, E는 간선의 개수이다.

플로이드 워셜(Floyd-Warshall) 알고리즘

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다. 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행하며, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. 노드의 개수가 N일 때, N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍에 해당한다. 3중 반복문을 이용하여 점화식 $D_{ab} = min(D_{ab},\ D_{ak} + D_{kb})$에 따라 최단 거리 테이블을 갱신하면 된다.

• 시간 복잡도: 노드의 개수가 N개일 때 N번의 단계를 수행하며, 단계마다 $O(N^2)$의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 총시간 복잡도는 $O(N^3)$이다.

(2025.08.20)

Chapter 10. 그래프 이론

코딩 테스트에서 출제 비중이 낮은 편이지만 제대로 알아야 하는 알고리즘을 다룬다. '서로 다른 객체가 연결되어 있다'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘은 앞서 배운 큐 자료구조 혹은 스택 자료구조를 활용해야 구현할 수 있다.

서로소 집합

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이고, find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1-1. A와 B의 루트 노드 A', B'를 각각 찾는다.
   1-2. A'를 B'의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다).
   
2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.
   

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
   1-1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
   1-2. 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
   
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.
   

신장 트리 & 크루스칼 알고리즘

신장 트리(Spanning Tree)는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 크루스칼 알고리즘은 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때 사용된다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   2-2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
   
3. 모든 간선에 대하여 2번의 과정을 반복한다.

• 크루스칼 알고리즘의 시간 복잡도: 간선의 개수가 E개일 때, $O(ElogE)$의 시간 복잡도를 가진다. E개의 간선을 정렬하는 작업에서 시간이 가장 오래 걸리기 때문이다.

위상 정렬

위상 정렬(Topology sort)은 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 진입차수는 특정한 노드로 '들어오는' 간선의 개수를 의미한다.

1. 진입차수가 0인 노드는 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
   

• 위상 정렬의 시간 복잡도: 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해야 하므로, $O(V+E)$의 시간 복잡도를 가진다.

(2025.08.20)

Chapter 11. 그리디 문제

Chapter 12. 구현 문제

Chapter 13. DFS/BFS 문제

Chapter 14. 정렬 문제

Chapter 15. 이진 탐색 문제

Chapter 16. 다이나믹 프로그래밍 문제

Chapter 17. 최단 경로 문제

Chapter 18. 그래프 이론 문제

Chapter 19. 2020년 상반기 삼성전자 기출문제