본문 바로가기

알고리즘

부분 수열의 최대합 부분 수열의 최대합을 구하는 알고리즘은 여러 가지가 있으며, 대표적인 알고리즘으로는 Kadane's Algorithm과 분할 정복 알고리즘이 있습니다. 이 두 알고리즘은 각각 다른 시간 복잡도를 가지며, 특정 상황에서 더 효율적일 수 있습니다. 아래에서 각각의 알고리즘을 설명하고, C++ 예제 코드를 제공합니다.1. Kadane's AlgorithmKadane's Algorithm은 선형 시간 복잡도 O(n)으로 부분 수열의 최대합을 구할 수 있는 효율적인 알고리즘입니다. 이 알고리즘은 동적 프로그래밍 접근법을 사용하여 문제를 해결합니다.알고리즘 설명:현재 위치까지의 최대 부분합을 저장하는 currentMax와 전체 배열에서의 최대 부분합을 저장하는 globalMax를 유지합니다.각 원소를 순회하면서, .. 더보기
합병 정렬 (Merge Sort) 합병 정렬 : 합병 정렬은 분할 정복 기법을 사용한 정렬 알고리즘입니다. 리스트를 반복적으로 반으로 나누고, 각 하위 리스트를 정렬한 다음 정렬되 하위 리스트들을 합병하여 접체 리스트를 정렬합니다. - 합병 정렬은 항상 O(nlogn)의 시간 복잡도를 가집니다. - 합병 정렬은 추가적인 메모리 공간을 필요로 하며, 일반적으로 O(n)의 공간 복잡도를 가집니다. - 합병 정렬 은 불안정 정렬입니다. 동일한 값의 원소들이 입력 순서와 다르게 배치될 수 있습니다. 오름차순 예시 코드 더보기
삽입 정렬 (Insertion Sort) 삽입 정렬 : 삽입 정렬은 리스트를 순회하면서 각 원소를 적절한 위치에 삽입하여 정렬된 부분 리스트를 점진적으로 확장하는 방식으로 작동합니다. - 시간 복잡도        Best   : O(n)        Worst : O(n^2)  - 삽입 정렬은 추가적인 메모리를 거의 사용하지 않기 때문에 제자리 정렬(In Place Sort, O(1)의 공간 복잡도)입니다.  - 삽입 정렬은 입력 순서를 보장하는 안정 정렬(Stable Sort)입니다. 오름차순 예시 struct Num{ int idx; int num; Num(int idx, int num) : idx(idx), num(num) {};};void AscendingInsertionSort(vector& arr){ for (int i = 1; i.. 더보기
선택 정렬 (Selection Sort) 선택 정렬 : 선택 정렬은 0번 인덱스부터 n - 2의 인덱스에 대하여 해당 인덱스에 들어가야 할 원소를 선택하는 알고리즘입니다. 리스트에서 가장 작은(또는 가장 큰) 원소를 찾아 첫 번째 원소와 교환하고, 그 다음 두 번째로 작은 원소를 찾아 두 번째 원소와 교환하는 과정을 n - 1번 반복합니다. n - 1번인 이유는 마지막에 남은 원소는 마지막이 제자리이기 때문! - 선택 정렬은 O(n^2)의 시간 복잡도를 가집니다. - 선택 정렬은 불안정 정렬입니다. 동일한 값의 원소들이 입력 순서와 다르게 배치될 수 있습니다. - 선택 정렬은 추가적인 메모리를 거의 사용하지 않기 때문에 제자리 정렬(In Place Sort, O(1)의 공간 복잡도)입니다. 오름차순 예시소스 코드struct Num{ int id.. 더보기
버블 정렬 (Bubble Sort) 버블 정렬 : 버블 정렬(Bubble Sort)은 리스트를 여러 번 순회하면서 인접한 두 원소를 비교하고, 그 순서가 잘못되었으면 서로 교환하는 것입니다. 이렇게 하면 리스트의 가장 큰 값이 점점 뒤로 이동하며 마치 거품이 수면 위로 올라오는 것처럼 보이기 때문에 "버블 정렬"이라고 불립니다. - 버블 정렬은 O(n^2)의 시간 복잡도를 가져 길이가 길어질수록 비효율적인 알고리즘입니다. - 버블 정렬은 동일한 값들에 대해서 입력 순서를 보장하기 때문에 안정 정렬(Stable sort)입니다. - 버블 정렬은 주어진 리스트 외에 추가적인 메모리를 거의 사용하지 않기 때문에 제자리 정렬(공간 복잡도 O(1))입니다. 오름 차순 예시// 오름차순 정렬void AscendingBubbleSort(vector& .. 더보기
Counting Sort CountingSort - 계수 정렬양의 정수로 이루어진 배열을 정렬할 때 사용하는 정렬 알고리즘배열에 들어있는 값들을 세어서, 정렬하는 방식.ex )     key - value 방식arr = {5, 2, 3, 6, 7, 3, 4, 6, 9, 10}countingArr = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} ← size == arr에 들어있는 최대값 + 1arr의 첫번째 원소는 5 → countingArr[5]++;arr의 두번째 원소는 2 → countingArr[2]++;……arr의 마지막 원소는 10 → countingArr[10]++;countingArr = {0, 0, 1, 2, 1, 1, 2, 1, 0, 1, 1}              ↑ 반대로 유추해보면 .. 더보기

티스토리툴바