Changyu Lee

Algorithm

Algorithm Theory
Search

Dijkstra Algorithm

개요

다익스트라 알고리즘

다익스트라 알고리즘의 기본 동작 방식은 다음과 같다:
1.
시작 노드 설정: 출발점이 되는 시작 노드를 선택하고, 그 노드에서 다른 노드로 가는 경로를 계산한다. 처음에는 시작 노드에서 자신의 거리를 0으로 설정하고, 다른 모든 노드까지의 거리는 무한대로 초기화한다.
2.
방문하지 않은 노드 중에서 최단 거리를 가진 노드 선택: 시작 노드에서 출발하여 인접한 노드 중 가장 가까운 노드를 선택하고 그 노드를 탐색한다. 아직 방문하지 않은 노드들 중에서 현재까지의 최단 거리가 가장 짧은 노드를 선택한다.
3.
최단 거리 갱신: 선택한 노드의 인접한 노드를 확인하고, 해당 노드를 거쳐 가는 경로가 더 짧으면 그 노드까지의 거리를 갱신한다.
4.
이 과정을 반복: 모든 노드를 탐색할 때까지 위의 과정을 반복하며, 한 번 방문한 노드는 다시 방문하지 않는다. 각 노드를 탐색할 때마다 우선순위 큐를 사용하여 가장 작은 값을 가진 노드를 효율적으로 선택한다.
이 과정이 끝나면, 시작점에서 각 노드까지의 최단 경로가 결정된다.
Dijkstra Algorithm

Priority Queue (우선순위 큐)

개요

일반 Queue와의 차이점

왜 우선순위가 앞에 붙을 것인가? 답은 간단하다.
일반 큐와 우선순위 큐의 가장 큰 차이점은 데이터 처리 순서이다. 일반 큐에서는 가장 먼저 삽입된 데이터가 가장 먼저 처리되지만, 우선순위 큐에서는 우선순위가 높은 데이터가 먼저 처리된다.
•
일반 큐: 선입선출 (FIFO)
•
우선순위 큐: 우선순위에 따라 처리 순서 결정
왜 우선순위가 앞에 붙는가? 그 답은 간단하다. 우선순위 큐는 대기 중인 작업 중에서 더 중요한 작업을 먼저 처리하기 위해 설계되었다. 예를 들어, 병원의 응급실에서 환자를 진료할 때, 더 위급한 환자를 먼저 진료하는 것이 더 중요하다. 이처럼 우선순위 큐는 긴급한 작업을 우선 처리해야 하는 상황에서 매우 효과적이다.

Heap (힙)

Priority Queue (feat. Heap)

Binary Search (이진 탐색)

개요

탐색이란?

원하는 데이터를 찾는 작업을 탐색이라고 한다.
다른 말로, 레코드의 집합에서 주어진 키를 지닌 레코드를 찾는 작업을 탐색이라 하며, 이 때 주어진 키를 목표 키 (Target Key), 또는 탐색 (Search Key)라고 부른다. 물론 탐색 키를 지닌 레코드가 하나 이상일 수도 있고 없을 수도 있다. (주우석, 2015)
보통 이미 정렬된 자료에서 탐색을 진행한다고 가정한다. 실제로는 아마 그렇지 않을 경우가 많겠지만 말이다.
자료구조는 정보를 저장하기 위한 것이지만 결국은 저장된 정보를 탐색해야하는 최종 목적이 있고, 어떻게 탐색하느냐에 따라서 성능이 크게 좌우될 수도 있다.

이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 원하는 값을 찾기 위해 사용되는 효율적인 탐색 알고리즘이다. 탐색 범위를 절반으로 줄여가며, 탐색할 데이터의 중간값과 비교하는 방식으로 진행된다.
이때 시간 복잡도는 O(log⁡⁡n)O(\log⁡n)으로 매우 효율적이다. 다만, 이 때 데이터들이 정렬되있다는 가정을 한다.
Binary Search (feat. Binary Search Tree)

Dynamic Programming (동적 계획법, DP)

개요

동적 계획법(DP)의 이해

•
DP란 무엇인가?
DP는 보통 알고리즘 대회나 문제풀이에서 메모리를 사용하여 복잡한 계산과정을 덜어내는 방식으로 사용된다.
이런 메모리들을 캐시 (Cache) 라고 부르며, 두 번 이상 계산되는 부분 문제를 ‘중복되는 부분 문제’ 라고 부른다.
동적 계획법이 사용되는 제일 유명한 예는 이항 계수이다.
(nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
위 점화식을 풀기 위해서 재귀 호출을 계속 하게 되는데, 계산을 하다보면 중복되는 연산을 계속하게 된다.
이항 계수를 계산하는 과정을 트리 형태로 나타내면 다음과 같다.
Basics of Dynamic Programming

Topological Sorting (위상정렬)

개요

위상 정렬이란?

위상 정렬(Topological Sorting)은 방향성을 가진 순환이 없는 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 순서대로 정렬하는 기법이다. 이때, 정렬된 순서는 노드 간의 의존 관계를 유지해야 한다. 즉, 어떤 작업 A가 작업 B에 의존한다면, 위상 정렬 결과에서는 반드시 작업 A가 작업 B보다 앞에 나와야 한다.
위상 정렬의 본질은 그래프의 각 노드들이 가지는 의존성(간선)을 고려하여 순서를 정하는 것이다. DAG에서 이러한 의존성을 해결하는 유일한 방법이 바로 위상 정렬이다.
•
위상 정렬의 결과는 반드시 유일하지 않다.
주요 개념
다음은 위상정렬의 수도 코드

위상 정렬의 규칙

Topological Sorting

Breadth First Search (너비 우선 탐색)

개요

BFS는 다음과 같은 문제에서 주로 사용된다:
•
최단 경로 탐색 (무가중치 그래프에서)
•
레벨 탐색 (트리 구조에서 각 노드의 깊이를 계산할 때)
•
연결 요소 찾기 (그래프의 모든 연결 요소를 탐색)

너비를 우선 탐색한다는 것의 의미

BFS에서 '너비를 우선 탐색한다'는 것은, 시작 정점으로부터 가까운 정점들을 먼저 탐색하고, 그 다음에 더 먼 정점들을 탐색한다는 의미이다. 이를 위해 BFS는 먼저 시작 정점을 큐에 넣고, 그 정점과 연결된 정점들을 차례대로 큐에 넣으면서 탐색을 진행한다.
BFS는 한 번 방문한 정점을 다시 방문하지 않기 때문에 중복된 경로를 피할 수 있다. 이는 주로 방문 여부를 기록하는 배열(혹은 리스트)을 통해 처리된다.
•
수도 코드
Graph - Breadth First Search

Depth First Search (깊이 우선 탐색)

개요

그래프의 탐색

DFS는 그래프 탐색 방법 중 하나로, 모든 노드를 방문하고자 할 때 사용된다. 그래프에서 노드를 하나 선택하고, 연결된 노드를 따라가며 최대한 깊이 탐색하는 것이 특징이다.

깊이를 우선한다는 것의 의미

깊이 우선 탐색은 한 경로로 최대한 깊이 탐색한 후 더 이상 나아갈 수 없을 때 다른 경로를 찾는다. 이를 재귀적으로 반복하며 그래프의 모든 노드를 방문할 수 있다.

스택과 DFS

Graph - Depth First Search

Graph Algorithm (그래프 알고리즘)

개요

그래프 (Graph) 란?

그래프는 정점(vertex)과 간선(edge)으로 구성된 자료 구조로, 객체 간의 관계를 나타내는 데 사용된다. 다양한 문제에서 개체 간의 연결성을 표현하기 위해 사용되며, 정점은 개체를, 간선은 그 개체들 간의 관계를 의미한다.
Introduction to Graph Algorithm

정렬 알고리즘 비교

개요

•
정말 바쁘게 달려온 정렬 알고리즘 정리… 이제 마지막 장을 남겨 두고 있다.
•
정렬 알고리즘들을 한 눈에 비교하는 시리즈. 반드시 알아야하는 주요한 사항들도 한 번 같이 정리해보도록 한다.

정렬 알고리즘 비교 표

외..외부 정렬?

외부 정렬은 간단하게 생각하면 된다. 메모리 내에서 직접 데이터를 정렬하느냐 마느냐의 여부이다. 다른 알고리즘에 비해서, 안정형이자 배열을 분할하여 정복하는 Merge Sort (합병/병합정렬)은 외부 정렬이 가능하여 큰 데이터를 외부 저장 장치에서 정렬할 때 유용하다고 한다.

다시 표로 돌아와서.

•
주요 차이점:

뭣이 안정한데?

안정성에 대해 잠깐만 더 살펴보도록 하자.
Comparison of Sorting Algorithm (feat. External Sort)

Quick Sort (쾌속 정렬)

개요

근데 분할-정복을 어디서 들어봤는데?

맞다. 바로 이전에 포스팅된 합병 정렬에서 다룬 내용이다.
합병 정렬과 퀵 정렬의 차이점은 순서라고 봐도 무방하다. 분할 후 정복하는 합병 정렬과 달리 정복 후 분할해나가는 퀵정렬이므로, 분할 과정과 정복 과정의 순서가 차이가 있다고 생각해도 무방해보이며, 퀵 정렬은 “Conquer and Divide” 알고리즘의 일부로도 불리곤 한다.

얼마나 빠르길래 “Quick”일까..?

퀵 정렬은 평균 시간 복잡도 O(n log n)을 가지고 있어, 대부분의 경우 매우 빠르게 작동한다. 특히 데이터가 무작위로 분포된 경우에 퀵 정렬은 그 성능을 극대화한다.
퀵 정렬은 대개 병합 정렬(Merge Sort)과 함께 효율적인 정렬 알고리즘으로 많이 비교된다. 병합 정렬과 달리 추가적인 메모리 공간을 거의 사용하지 않으며, 제자리(in-place)에서 정렬을 수행하므로, 메모리 효율이 매우 우수하다.
그러나, 최악의 경우 퀵 정렬의 성능은 O(n2)O(n^2)가 된다. 이 경우는 피벗 선택이 항상 부적절하게 이루어져, 매번 한쪽으로만 데이터를 나누는 경우이다. 이를 방지하기 위해 피벗을 랜덤하게 선택하거나, 중간값을 피벗으로 설정하는 다양한 기법이 사용된다.

쾌속 정렬 작동 원리

Sorting Algorithm - Quick Sort (쾌속 정렬)

Merge Sort (합병 정렬)

개요

•
이름은 합병 정렬이다. 또는 병합 정렬이라고도 불린다. (밑에서 둘을 혼용함)

왜 “합병”인가?

합병 정렬은 기본적으로 재귀호출의 형태를 띈다. 재귀 호출을 하면서 배열을 반으로 분할시키고 이를 정렬한뒤 다시 합쳐서 정렬하는 반복 형태의 방식을 사용한다.
이 과정에서 분할하고, 정복한다는 분할-정복 (Divide and Conquer) 방식이 사용되며,
배열을 합친다는 개념 때문에 합병 (혹은 병학, Merge) 라는 이름이 붙은 알고리즘이다.

합병 정렬 작동 원리

아래는 합병정렬의 수도코드이다.
수도 코드조차 상당히 길지만 아래의 작동 원리를 살펴보면 이해할 수 있을 것이다.
Sorting Algorithm - Merge Sort (합병 정렬)

쉘 정렬 (Shell Sort)

개요

쉘 정렬이란?

쉘 정렬은 삽입 정렬의 문제점을 개선하기 위해 고안되었다.
쉘(Shell)은 껍질 혹은 틀을 의미한다. 이런 의미를 생각했을 때, 쉘 정렬은 큰 틀을 먼저 잡고, 세부적으로 점차 정렬해 들어가는 것이 특징이라고 생각하면 된다.
삽입 정렬은 작은 데이터 집합에 대해 효율적이지만, 큰 데이터 집합에서는 성능이 떨어지는 단점이 있다. 쉘 정렬은 배열을 간격으로 나누어 그 간격 내에서 삽입 정렬을 수행하며, 간격을 줄여 나가면서 점진적으로 전체 배열을 정렬해 나가는 방식이기 때문이다.

쉘 정렬 작동 원리 설명

쉘 정렬의 핵심은 간격(gap)을 설정하고, 그 간격에 따라 배열을 부분적으로 나누어 삽입 정렬을 수행한 후, 간격을 줄여가면서 전체 배열을 점진적으로 정렬하는 것이다. 처음에는 큰 간격을 사용해 배열을 크게 나누어 처리하고, 간격을 좁혀가면서 더 작은 그룹을 정렬해 나간다.
사실 위 애니메이션만 보고는 이해가 힘들다.
Sorting Algorithm - Shell Sort (쉘 정렬)

Insertion Sort (삽입 정렬)

개요

삽입을 어떻게 하는가?

삽입 정렬은 그 이름에서 원리를 이미 알 수 있을 것이다. 하지만 삽입을 어디로 언제 해야하는가는 의문일 것이다.
삽입의 대상은 현재 처리 중인 요소로, 이미 정렬된 부분 배열에서 해당 요소가 들어갈 적절한 위치를 찾아 그 자리에 삽입한다. 삽입 위치를 찾기 위해 현재 요소보다 큰 값을 오른쪽으로 이동시키고 자리를 확보한 후에 요소를 삽입하는 방식이다.

삽입 정렬의 동작 원리

삽입 정렬이 배열 [22, 37, 15, 19, 12]에 적용되는 과정을 단계별로 설명하면 다음과 같다.
1.
첫 번째 요소 22는 이미 정렬된 것으로 간주한다. 따라서 두 번째 요소부터 비교를 시작한다.
Sorting Algorithm - Insertion Sort (삽입 정렬)
Sorting Algorithm - Bubble Sort (버블 정렬)

선택 정렬 (Selection Sort)

개요

지금부터 본격적인 기본 정렬 알고리즘을 공부해보자.

왜 “선택” 인가?

선택 정렬은 정렬 과정에서 하나를 고정하고, 바꿀 대상을 “선택”해서 바꾸는 알고리즘이다.
대부분 이야기하는 선택 정렬은 값이 큰 데이터를 맨 뒤로 보내는 것이 일반적으로 보이며, 오름차순으로 정렬을 하며 가장 큰 값을 찾고, 이를 정렬의 대상이 되는 마지막 데이터를 선택해서 바꾸는 알고리즘이다.
여기서는 반대로, 최소값을 앞으로 먼저 보내는 걸 생각을 하겠다. 0부터 시작하는 반복문을 짜므로 조금 더 편한 방식이라고 생각이 되기 때문이다.

선택 정렬의 동작 과정

Sorting Algorithm - Selection Sort (선택 정렬)

Big-O Notation (빅오 표기법)

개요

프로그램의 성능 측정 방법론

효율적인 프로그램은 어떤 기준을 참고로 삼아야하는가에 대한 기준을 이야기해보고자 한다.
결국 컴퓨터는 연산을 위한 기기로서, 데이터를 처리하는데 있어서 연산 횟수와 문제 상황에 맞는 접근 방식으로 이 연산을 최적화할 필요가 있다.
연산 횟수를 줄이기 위해 메모리, 즉 다른 저장 장소를 사용하는 경우가 있다.
혹은 저장되는 자료를 필요한 만큼만 저장하여 컴퓨터 연산을 줄이거나 혹은 컴퓨터의 저장으로 소모되는 비용들을 줄이는 방법이 요구된다.
가령, 1TB 데이터를 잘 저장해서 필요한 만큼 선별하던 뭘 하던 100GB로만 만들어도 비용은 줄어드니까 말이다.
따라서, 프로그램은 기본적으로 두 가지에 의해서 성능이 측정된다.
•
시간 복잡도 : 알고리즘에 사용되는 연산 횟수
Big-O Notation

이번 시리즈를 쓰는 이유

카이스트 면접을 탈락했을 때, 내 자신에게 실망했던 적이 있다. 바로 이 빅오 노테이션을 설명하지 못했던 것이다..
몰랐던 것은 아니다. 알고리즘에서 계산하는 법은 당연히 안다. 다만 한 줄로 설명이 안됐다.
대체 어떻게 이걸 못할 수가 있는가…? 나도 내 자신에게 정말 실망했었다.
심지어 대학교 1학년 때 나는 자료구조와 알고리즘을 A+ 받았다. 공부할 때 정말 열심히 했었고, 자신도 있었는데, 막상 오랜만에 누군가가 물어보니 설명을 못했다.
서울대와 포스텍 등 대학원을 다시 준비하면서 구술 면접을 대비해야했기도 했고,
적어도 증명해야되지 않는가. 내가 자질이 있다는 것을.
상기의 이유로, 해야만 하니까… 사실 다시 공부를 시작하는 것이다.
이번 시리즈의 목표는 기본적으로 개념을 면접에서 설명할 수 있을 정도로 간결하고, 핵심을 빠르게 전달하는 것을 목표로 정리해보고자 한다.
내게 주어진 시간은 오직 일주일.
Introduction to From the Bottom - Algorithm Series