💡병합 정렬(Merge sort) - 병합 정렬은 분할 정복방법을 사용하여 리스트를 정렬하는 알고리즘입니다. i) 병합 정렬 과정 - 리스트를 반으로 나눕니다. - 각각을 재귀적으로 정렬합니다. - 두 리스트를 다시 하나의 리스트로 합칩니다. 이때 두 리스트는 이미 정렬되어 있는 형태입니다. ii) 병합 정렬 특징 병합 정렬은 안정적인 정렬 알고리즘입니다. 안정적인 정렬 알고리즘이란, 같은 값의 원소가 여러 개 존재할 경우, 입력 배열에서의 순서가 유지되는 정렬 알고리즘을 말합니다. 병합 정렬은 분할 정복 알고리즘을 사용합니다. 이는 문제를 작은 문제로 분할하여 해결하는 방법으로, 재귀적인 호출을 이용하여 문제를 해결합니다. 병합 정렬의 시간 복잡도는 평균적으로 O(nlogn)입니다. 이는 입력 크기가 ..

정렬 알고리즘 이란 - 원소들을 일정한 순서대로 열거하는 알고리즘입니다. - 대표적인 알고리즘에는 아래와 같이 존재합니다. - 병합 정렬, 힙 정렬, 퀵 정렬의 경우 다음 포스팅에서 확인하시면 될 것 같습니다. 삽입 정렬 (Insertion sort) 선택 정렬 (Selection sort) 버블 정렬 (Bubble sort) 병합 정렬 (Merge sort) 힙 정렬 (Heap sort) 퀵 정렬 (Quick sort) 💡삽입 정렬 - 삽입 정렬은 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입 하는 방법입니다. - 선택정렬처럼 동작을 직관적으로 이해하기 쉽지만, 선택정렬보다는 구현 난이도가 높고 실행시간 면에서 더 효율적입니다. i) 삽입 정렬 과정 1) 삽입정렬은 이미 정렬된 영역( ..

퀵 정렬 - 퀵 정렬은 대표적인 분할 정복 알고리즘 중 하나로 평균적으로 가장 빠른 실행 시간을 가지는 정렬 알고리즘 입니다. - 퀵 정렬은 unstable한 알고리즘으로 호출될 때마다 새로운 리스트를 생성하며 리턴하기 때문에 기본적으로는 not-in-place 정렬이기도 하다. - 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. Unstable 퀵 정렬은 unstable한 알고리즘으로 unstable한 알고리즘이란, 정렬 후 같은 값들의 순서가 원래의 순서와 다를 수 있는 것을 말합니다. 예를 들어, [3, 1, 3, 4, 2]와 같은 배열을 퀵 정렬로 정렬하면 [1,2,3,3,4]와 같이 3이 중복되서 나타나..

재귀함수란 - 재귀함수란, 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. 즉, 함수의 정의에서 함수 자신을 참조하는 것입니다. - 재귀함수는 보통 문제를 작은 부분 문제로 분할하여 해결할 수 있을 때 사용됩니다. 이때, 재귀함수는 각각의 부분 문제를 해결하는 데에도 같은 함수를 호출하게 됩니다. - 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)과 피보나치수열(Fibonacci) 입니다. 재귀함수의 장단점 장점 - 코드가 간결하고 이해하기가 쉽다. - 반복문을 사용하지 않아도 동일한 결과를 얻을 수 있다. 단점 - 함수를 호출할 때마다 스택 메모리에 쌓이기 때문에, 메모리를 많이 사용한다. - 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다. - 반복문을 사..

복잡도에 대해서 1. 크게 시간 복잡도(Time Complexity)와 공간 복잡도로 나눌 수 있다. 2. 알고리즘의 성능 평가 및 효율성을 나타내는 척도이다. 3. 동일한 기능을 수행하는 알고리즘이 있을때 복잡도가 낮을수록 좋은 알고리즘이라 말한다. 1. 시간 복잡도 - 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수의 총량을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 즉, 입력 크기가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가량을 나타내는 것입니다. 시간 복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악..