Algorithm

Algorithm Theory

Python

1. Array

1-1. 슬라이싱 [::k]와 [:k] 차이

1-2. 리스트에서 중복 제거

1-3. 2차원 배열에서 중복 제거

1-4. 리스트에서 최댓값/최솟값 찾기

2. heapq 사용법 (최소 힙 기반)

코테 대비 Python 주요 자료구조와 내장 함수들 정리 (수정판)

C++

string

vector

pair

map (정렬 맵, 중복 키 불가)

set (정렬 집합, 중복 불가)

queue (FIFO)

deque (양쪽 입출, 임의 접근)

코테 대비 C++/Python/SQL 주요 자료구조와 내장 함수들 정리

Dijkstra Algorithm

개요

다익스트라 알고리즘 (Dijkstra Algorithm)은 그래프에서 하나의 시작점에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 비음수 가중치가 있는 그래프에서 최단 경로를 찾을 때 사용되며, 우선순위 큐를 활용하여 효율적으로 탐색할 수 있다.

다익스트라 알고리즘

Dijkstra Algorithm

Priority Queue (우선순위 큐)

개요

우선순위 큐(Priority Queue)란 우선순위 큐(Priority Queue)란 큐(Queue) 자료구조의 일종으로, 각 요소에 우선순위가 부여되어 우선순위가 높은 요소가 먼저 처리되는 구조를 말한다.

일반 Queue와의 차이점

Priority Queue (feat. Heap)

Binary Search (이진 탐색)

개요

이진 탐색(Binary Search)는 절반씩 나누어 가면서 찾아가는 알고리즘이다.

탐색이란?

원하는 데이터를 찾는 작업을 탐색이라고 한다.

Binary Search (feat. Binary Search Tree)

Dynamic Programming (동적 계획법, DP)

개요

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위해 작은 하위 문제로 나누고, 그 결과를 저장하여 동일한 하위 문제를 반복 계산하지 않는 방법이다. DP는 주로 최적화 문제에서 사용되며, 효율적인 알고리즘 설계를 위해 중요한 도구이다.

동적 계획법(DP)의 이해

Basics of Dynamic Programming

Topological Sorting (위상정렬)

개요

위상 정렬(Topological Sorting)은 방향성을 가지며 순환이 없는 그래프(Directed Acyclic Graph, DAG)의 노드들을 특정 순서로 정렬하는 알고리즘이다. DAG 구조에서 위상 정렬은 주로 작업 스케줄링, 의존성 관리 등에 활용된다.

위상 정렬이란?

Topological Sorting

Breadth First Search (너비 우선 탐색)

개요

BFS(Breadth First Search, 너비 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서부터 가까운 정점들을 먼저 탐색한 후, 차례대로 거리가 먼 정점들을 탐색하는 방식이다. BFS는 너비를 우선적으로 탐색하기 때문에, 최단 경로를 구할 때 유용하며 주로 큐(Queue)를 사용하여 구현된다.

BFS는 다음과 같은 문제에서 주로 사용된다:

•

최단 경로 탐색 (무가중치 그래프에서)

Graph - Breadth First Search

Depth First Search (깊이 우선 탐색)

개요

깊이 우선 탐색(DFS, Depth First Search)은 그래프 탐색 알고리즘 중 하나로, 한 노드를 시작으로 연결된 노드를 따라 최대한 깊이 탐색한 후, 더 이상 갈 수 없으면 다시 돌아와 다른 경로를 탐색하는 방식이다.

그래프의 탐색

Graph - Depth First Search

Graph Algorithm (그래프 알고리즘)

개요

그래프 (Graph)는 정점(Vertex or Node)나 간선(Edge)로 구성되는 자료구조로, 객체 간의 관계를 표현한다. 방향성 여부에 따라 유향 그래프와 무향 그래프로 구분되며, 인접 리스트 또는 인접 행렬로 구현된다.

그래프 (Graph) 란?

Introduction to Graph Algorithm

정렬 알고리즘 비교

개요

•

정말 바쁘게 달려온 정렬 알고리즘 정리… 이제 마지막 장을 남겨 두고 있다.

•

정렬 알고리즘들을 한 눈에 비교하는 시리즈. 반드시 알아야하는 주요한 사항들도 한 번 같이 정리해보도록 한다.

정렬 알고리즘 비교 표

Comparison of Sorting Algorithm (feat. External Sort)

Quick Sort (쾌속 정렬)

개요

쾌속 정렬 (Quick Sort)는 피벗 (Pivot) 을 선택하여 분할 정복으로 정렬하는 빠른 알고리즘으로, 메모리를 따로 사용하지 않는다는 장점이 있다. 시간 복잡도는

O(nlogn)

이나 최악의 경우

O(n^2)

이 되기도 한다.

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

맞다. 바로 이전에 포스팅된 합병 정렬에서 다룬 내용이다.

Sorting Algorithm - Quick Sort (쾌속 정렬)

Merge Sort (합병 정렬)

개요

합병 정렬 (Merge Sort)란 배열을 반으로 나누고 각각을 정렬한 후 합치는 분할 정복 알고리즘으로, 시간 복잡도는 O(n log n)입니다.

•

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

왜 “합병”인가?

Sorting Algorithm - Merge Sort (합병 정렬)

쉘 정렬 (Shell Sort)

개요

쉘 정렬 (Shell Sort) 은 삽입 정렬을 개선한 버전으로, 배열을 일정 간격(gap)으로 나눈 후 부분 배열을 삽입 정렬하고, 그 간격을 점차 줄여가며 배열을 정렬하는 알고리즘임. 일반적으로

O(n\sqrt{n})

의 시간 복잡도를 가짐. (h에 따라 다르며, 불안정 정렬임)

쉘 정렬이란?

Sorting Algorithm - Shell Sort (쉘 정렬)

Insertion Sort (삽입 정렬)

개요

삽입 정렬 (Insertion Sort) 란 배열의 각 요소를 앞에서부터 차례대로 적절한 위치에 삽입하여 정렬하는 알고리즘으로, 시간 복잡도는 O(n²)이다.

삽입을 어떻게 하는가?

Sorting Algorithm - Insertion Sort (삽입 정렬)

버블 정렬 (Bubble Sort)

개요

버블 정렬(Bubble Sort) 은 인접한 요소들을 반복적으로 비교 및 교환하여 배열을 정렬하는 알고리즘으로, 시간 복잡도는 O(n²)입니다.

왜 ‘버블’ 인가?

Sorting Algorithm - Bubble Sort (버블 정렬)

선택 정렬 (Selection Sort)

개요

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

선택 정렬: 배열에서 가장 작은 값을 선택해 앞에서부터 순서대로 정렬하는 방식이며, 시간 복잡도는 O(n²)이다.

Sorting Algorithm - Selection Sort (선택 정렬)

Big-O Notation (빅오 표기법)

개요

Big-O 표기법이란 “알고리즘의 성능을 입력 크기에 따라 최악의 성능을 나타내는 수학적 표기법” 이다.

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

Big-O Notation

이번 시리즈를 쓰는 이유

카이스트 면접을 탈락했을 때, 내 자신에게 실망했던 적이 있다. 바로 이 빅오 노테이션을 설명하지 못했던 것이다..

몰랐던 것은 아니다. 알고리즘에서 계산하는 법은 당연히 안다. 다만 한 줄로 설명이 안됐다.

대체 어떻게 이걸 못할 수가 있는가…? 나도 내 자신에게 정말 실망했었다.

심지어 대학교 1학년 때 나는 자료구조와 알고리즘을 A+ 받았다. 공부할 때 정말 열심히 했었고, 자신도 있었는데, 막상 오랜만에 누군가가 물어보니 설명을 못했다.

Introduction to From the Bottom - Algorithm Series