카테고리: 알고리즘

페이지당5 10 20

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

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

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

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

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

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

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