본문 바로가기
  • 저희는 평생 개발할 운명이걸랑요

Tech.log/알고리즘8

[Stable Sort(안정 정렬) vs Unstable Sort(불안정 정렬)] 2021.05.10 - [Tech.log/알고리즘] - [정렬 방법] 정렬을 잘 모른다면, 해당 글을 먼저 참고하자. Stable Sort(안정 정렬) 동일한 정렬 기준을 가진 것은 정렬을 한 후에 위치가 동일하다. ex)5 9 3’ 7 2 3 => 2 3’ 3 5 7 9 Bubble Sort(버블 정렬)Insertion Sort(삽입 정렬)Merge Sort(합병 정렬) Unstable Sort(불안정 정렬) 동일한 정렬 기준을 가진 것은 정렬을 한 후에 위치가 동일하지 않을 수 있다. ex)5 9 3’ 7 2 3 => 2 3 3’ 5 7 9 Selection Sort(선택 정렬)Quick Sort(퀵 정렬)Heap Sort(힙 정렬) UnStable한 이유 Selection Sort(선택 정렬) ex.. 2021. 5. 29.
[꼬리 재귀(Tail Recursion)] 재귀 하나의 함수에서 자신을 호출하여 작업을 수행하는 방식으로 문제를 푼다. 함수는 호추할때 함수의 입력값,리턴값,돌아갈 위치 값들을 스택에 저장한다. 재귀 함수를 사용하면 함수가 끝나지 않은 채 함수를 계속해서 호출함으로 스택에 메모리가 쌓이게 되고 오버 플로우가 발생한다. 이러한 단점을 보완하기 위해 꼬리재귀를 사용한다! 꼬리재귀란 ? 재귀호출이 끝난 후, 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태이다. 함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로 처리하여 재사용 가능하다. //일반 재귀 예시 int Factorial(int n) { if (n == 1) return 1; return n * Factorial(n-1); } //꼬리재귀 예시 int Factor.. 2021. 5. 18.
[BigO표기법이란] 알고리즘의 수행 시간을 표현 하는 방법은 상한을 나타내는 빅오(Big-O), 평균을 나타내는 빅오메가(big-Ω), 하한을 나태나는 빅세타(big-Θ)가 있는데 그중 우리는 빅오(Big-O) 를 사용한다. Big-O는 증가율을 나태기 때문에 데이터의 입력이 충분이 큰 것으로 가정하고 사소한 부분들을 무시합니다. 따라서, 상수항이나 영향력이 없는 항은 무시하고 수행되는 연산(곱셈,덧셈 등)의 수를 계산하여 수행 시간을 나타낸다. BigO표기법은 기본적으로 최악의 경우의 복잡도 를 기준으로 측정한다. 해당 코드를 살펴 보자 for(int i=0; i 2021. 5. 11.
[정렬 방법] 정렬 알고리즘은 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다. 대표적으로 버블소트, 힙소트, 머지소트, 퀵소트, 선택 소트,삽입소트,기수 정렬이 있다. 선택 정렬(selection Sort) 현재 값을 기준으로 뒤에 값들을 비교해서 뒷 값이 더 작으면 Swap하는 방식(오름차순 기준) . void selectionSort(int *list, const int n) { int i, j, indexMin, temp; for (i = 0; i < n - 1; i++) { indexMin = i; for (j = i + 1; j < n; j++) { if (list[j] < list[indexMin]) { indexMin = j; } } temp = list[indexMin]; list[index.. 2021. 5. 10.

티스토리툴바