foxibu

위상 정렬 (Topological Sort)

위상 정렬이란 유향 그래프에서 정해진 순서를 위배하지 않도록 나열하는 것입니다. 예를 들면 전략 게임에서의 빌드 오더나 선수강과목을 예로 들 수 있습니다. 전략 게임의 빌드 오더에서 A를 짓지 않으면 B를 지을 수 없고, B를 짓지…

2024-05-173분

#알고리즘 #그래프

퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고, 해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보내고 다시 왼쪽 파티션 구간에 한하여…

2024-05-163분

분할 정복 (Divide & Conquer)

분할정복(Divide and Conquer)은 말 그대로 문제를 분할한 다음, 분할한 문제들 (sub-problems)을 해결하고, 그 결과를 합쳐서 원래의 문제를 해결하는 것입니다. 분할정복의 대표적인 예로는 합병 정렬, 고속…

2024-05-143분

BFS (Breadth-First Search, 너비 우선 탐색)

너비 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점들을 발견하면 그 간선을 통해 방문하지 않은 정점들을 자료구조 큐에 넣습니다.…

2024-05-133분

#알고리즘 #그래프

Hashing (해싱)

해싱은 임의의 길이의 데이터(키, Key)를 고정된 길이의 데이터(해시값, Hash value)로 변환해 작은 크기의 해시 테이블로 대응(Mapping)시켜 식별하는 하나의 기법입니다. 해시 테이블은 M개의 버킷으로 이루어져…

2024-05-093분

힙 (Heap)

힙 heap 은 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 트리형 자료구조입니다. 힙은 완전이진트리 형식을 따르며 모든 부모 노드의 값이 자식 노드들의 값과 일정한 대소 관계를 가지게 되는 규칙을 가지고 있습니다.

2024-05-083분

Tree (트리)

트리는 자식과 부모의 관계로 이루어진 계층적인 구조입니다. 필요에 따라 다양한 종류로 나뉘게 되는데 이번에는 제일 간단한 트리인 이진 트리에 대해서 설명하려고 합니다. 먼저 이진 트리에서 사용하는 용어들을 정리해보면 다음과…

2024-05-077분

Stack(스택)

스택은 선형 구조이며, 마지막으로 삽입된 값이 가장 먼저 나오는 LIFO(Last in First Out)으로 되어 있습니다. 이 때 삽입하는 과정을 push라고 하며 값을 빼내는 과정을 pop이라고 합니다. 예를 들면 a, b,…

2024-05-062분

Queue (큐)

큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다. 예를 들면 a, b, c…

2024-05-054분

List(연결리스트)

연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다. 연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인…

2024-05-032분

DFS (Depth-First Search, 깊이 우선 탐색)

깊이 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동하는 것입니다. 이…

2024-05-022분

#알고리즘 #그래프

Graph (그래프)

그래프란 어떤 상태 혹은 객체 간의 관계를 나타내는 자료구조입니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성됩니다. 정점이란 어떠한 상태 혹은 객체를 나타냅니다. 간선은 그러한 정점 간의 관계, 그중에서도 연결성을…

2024-05-024분

#자료구조 #그래프

Binary Search (이진 탐색)

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 시간복잡도 O(log N) 만에 찾아내는 탐색하는 방법입니다. 오름차순으로 정렬된 사이즈가 N인 배열 D에서 원하는 값 k(k = 11)를 찾는 방법은 다음과…

2024-04-303분

에라토스테네스의 체 (Sieve of Eratosthenes)

에라토스테네스의 체는 특정 범위의 수들이 소수(Prime)인지 아닌지를 판별하는 알고리즘입니다. 예를 들어 1부터 50까지 수 중에서 소수를 구하고자 한다면 다음과 같은 배열이 필요합니다. 1 2 3 4 5 6 7 8 9 10 11…

2024-04-295분

버블정렬 (Bubble Sort)

거품정렬(Bubble Sort)은 인접한 원소들의 대소관계를 비교하여 일정한 대소관계를 만족하지 않을 시, 인접한 원소를 교환하는 방법으로 진행되는 정렬입니다. 다음은 버블 정렬을 쉽게 시각화 한 내용입니다. 더보기 먼저 4와 2를…

2024-04-262분

삽입 정렬(Insertion Sort)

삽입정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈 후, 원소를 순차적으로 탐색하면서 해당 원소를 정렬이 된 부분에 끼워 넣는 정렬입니다. 맨 처음 원소 1 를 정렬되었다고 가정한 후, 정렬되지 않은 다음

2024-04-251분

선택 정렬 (Selection Sort)

선택 정렬은 매 차례마다 정렬되지 않은 원소들을 모두 확인하여 각 인덱스에 맞는 원소를 선택하여 해당 인덱스의 원소와 교환해주는 정렬입니다. 매 차례마다 남은 원소들을 모두 확인하기 때문에 시간 복잡도는 최악의 연산 횟수나 평균…

2024-04-232분