퀵 정렬이란?퀵 정렬이란 분할 정복(Divide and Conquer) 방법을 사용하여 구현된 정렬 알고리즘을 의미한다. JAVA의 Arrays.sort()도 내부적으로 피벗을 하나가 아닌 두 개 사용하여 배열을 세 부분으로 나눈 Dual-Pivot QuickSort를 사용한다. 퀵 정렬은 분할 알고리즘을 무엇으로 사용하느냐, 그리고 피봇 설정을 무엇으로 하느냐에 따라 효율이 크게 달라진다. 분할 방법은 Hoare(호어), Lomuto(로무토) 방법이 존재하고, Pivot 설정은 랜덤 피봇, 중앙값 피봇, 이중 피봇, 하이브리드 피봇 등 다양한 방식이 있지만 가장 단순한 형태는 인덱스를 배열의 한 부분으로 고정시킨 고정값 피봇이다.(보통 첫 번째 값, 마지막 값, 혹은 가운데 인덱스를 고정) [이것이 코..

삽입 정렬이란?삽입 정렬은 숫자 카드를 정렬하는 방법과 유사하다. 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교해 삽입할 위치를 지정한 후, 원소를 뒤(오른쪽)로 옮기고 지정된 자리에 자료를 삽입한다. 삽입 정렬 장점과 단점삽입 정렬 장점구현이 쉽고, 이해하기 쉽다.적은 데이터나 거의 정렬된 데이터에 대해 효율적이다.삽입 정렬 단점데이터의 양이 많아질수록 비효율적이다.최악의 경우 시간 복잡도가 O(n²)이다. 시간 복잡도알고리즘BestAvgWorstRun-time(정수 60,000개) 단위: sec삽입정렬O(n)O(n²)O(n²)7.438선택정렬O(n²)O(n²)O(n²)10.842버블정렬O(n²)O(n²)O(n²)22.894셸 정렬O(n)O(n¹·⁵)O(n²)0.056퀵 정렬O(nlogn)O(..

선택 정렬이란?선택 정렬은 정렬되지 않은 데이터들에 대해 `가장 작은 데이터를 찾아` 가장 앞의 데이터와 교환해나가는 방식이다. 최솟값의 자리를 변수에 저장해놓고 그 자리의 값과 나머지 값들을 비교하며 최종 최솟값을 찾는 반복문이 끝나면 그때 스왑해준다. 선택 정렬 장점과 단점장점구현이 쉽다.내림차순으로 정렬되어있는 요소를 오름차순으로 재정렬할 때 효율이 좋다.비교 횟수는 많지만, 실제로 교환하는 횟수는 적다. 교환이 많이 일어나는 자료상태라면 효율적이다.(버블정렬과 비교했을 때, 똑같은 O(n2) 의 시간복잡도를 갖지만, 시간을 측정해보면 버블정렬보다 시간이 짧게 소요됨.)단점서로 떨어져 있는 요소를 교환하기 때문에 안정적이지 않다.(중복된 값이 2개 있을 때 요소의 순서가 바뀔 수 있음.)이미 정렬된..

버블 정렬이란?버블 정렬은 원소를 비교하는 과정에서 연탄 나르기와 비슷하다. 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하는 정렬 알고리즘이다. 시간 복잡도가 O(n²)로 상당히 느리지만, 소스코드가 직관적이고 구현이 매우 간단하다는 장점이 있다. 버블 정렬 장점과 단점버블 정렬 장점구현이 매우 간단하고, 소스코드가 직관적이다.정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. ➡ 제자리 정렬(in-place sorting)버블 정렬 단점시간복잡도가 최악, 최선, 평균 모두 O(n²)으로, 굉장히 비효율적이다.정렬 돼있지 않은 원소가 정렬 됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다. 시간 복잡도알고리즘Bes..

DFS(Depth-First-Search)란?그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을 마친 후, 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 또한 DFS는 그래프 완전 탐색(모든 노드를 방문)이며, 주로 스택(Stack) 자료구조를 사용하거나 재귀 호출을 통해 구현된다. DFS 장점과 단점DFS 장점현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적음목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음DFS 단점해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있음얻어진 해가 최단 경로가 된다는 보장이 없음 그래프 표현 방법우선 탐색하기 전 연결의 정보인 그래프를 표현부터 해야할 것이다. 그래프를 표현하는 방법에는 인접 행렬과,..

카데인 알고리즘이란?카데인 알고리즘(Kadane’s Algorithm)은 연속된 부분 배열의 최대 합을 찾을 때 사용된다. 주로 배열이나 리스트에서 연속된 원소들의 합이 최대가 되는 부분 배열을 효율적으로 찾는 경우에 유용하다. 예를 들어, 주어진 배열의 각 원소가 양수, 음수, 또는 0일 때 그 배열에서 연속적인 부분 배열의 최대 합을 구하고자 할 때 카데인 알고리즘을 사용하면 O(n)의 시간 복잡도로 문제를 해결하며, 동적 계획법(Dynamic Programming) 접근법을 사용한다. 이 알고리즘은 매 반복마다 현재 부분 합과 최대 부분 합을 갱신해 가며 최적의 해답을 찾아가는 방식이다. 카데인 알고리즘의 원리카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 각 요소를 순차적으로 탐색..