◈ Coding Test/알고리즘(Algorithm)🎡

[알고리즘] 병합 정렬/합병 정렬(Merge Sort) [존 폰 노이만의 정렬 알고리즘]

- 병합 정렬/합병 정렬(Merge Sort)이란? 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합하는 방식. 병합된 부분 안은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다. 이 그림에서 분할 정복으로 일정하게 정렬이 이뤄지는 병합 정렬의 특징을 잘 파악할 수 있다. [38, 27, 43, 3, 9, 82, 10]인 입력값은 [38, 27, 43, 3]과 [9, 82, 10] 로 두 부분으로 분할, 다시 [38, 27], [43, 3], [9, 82], [10]로 네 부분으로 분할 등의 방식으로 각각 더 이상 쪼갤 수 없을 때까지 계속해서 분할한 후, 분할이 끝나면 정렬하면서 정복해 나간다.

[알고리즘] 삽입 정렬(Insertion Sort) [값을 적절한 위치에 끼워넣는 정렬 알고리즘]

- 삽입 정렬(Insertion Sort)이란? k번째 원소를 1부터 k－1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식 → 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식적으로 사용하는 대표적인 알고리즘 ex) 카드 게임을 할 때나 번호대로 도서를 정리할 때 사용

[알고리즘] 선택 정렬(Selection Sort) [어떤 원소를 넣을지 선택하는 정렬 알고리즘]

- 선택 정렬(Selection Sort)이란? 1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째, …해서 (n－1) 번 반복한다. 어떻게 정렬이 되어 있든 일관성 있게 n(n－1)​／2에 비례하는 시간이 걸린다. → 인간이 사용하는 정렬 방식을 가장 많이 닮았다. (버블 정렬보다 두 배 정도 빠르다.) - 파생형 : 이중 선택 정렬(Double Selection Sort) 선택 정렬의 파생형으로, 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고 최댓값은 끝과 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식 → 선택 정렬에 칵테일 정렬 방식을 도입

[알고리즘] 버블 정렬(Bubble Sort) [값을 비교하여 뒤에서부터 정렬하는 정렬 알고리즘]

- 버블 정렬(Bubble Sort)이란? 버블 정렬은 1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n－1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n－2번째와 n－1번째까지, ... 해서 최대 n(n－1)／2 번 정렬한다. → 한 번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여 버블 정렬이다. - 버블 정렬의 효율성? 거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. → 만들기가 쉽고 직관적일 뿐이지 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식 - 버블 정렬의 파생형 1. 칵테일 정렬(cocktail sort) 셰이커 정렬(shaker sort)라고도 한..

[알고리즘] 정렬 알고리즘(Sorting algorithm)이란? [정렬 알고리즘의 정의, 이진탐색(Binary Search)]

- 정렬 알고리즘(Sorting algorithm)이란? 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘 - 정렬 알고리즘의 결과 조건 출력은 비 내림차순(각각의 원소가 전 순서 원소에 비해 이전의 원소보다 작지 않은 순서)이다. 출력은 입력을 재배열하여 만든 순열이다. - 왜 사용하는가? 컴퓨터 분야에서 사용하는 데이터의 경우, 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 많아 얼마나 효율적으로 정렬하느냐가 문제의 핵심이다. 데이터를 정렬해야 하는 이유는 탐색을 위해서! → 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다. - 이진 탐색(Binary Search) 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누..