STUDY/Algorithm
-
[정렬] 기본 정렬(선택, 버블, 삽입), 고급 정렬(병합, 퀵, 힙), 계수정렬STUDY/Algorithm 2021. 3. 14. 22:04
- 기본 정렬 알고리즘 선택 정렬 버블 정렬 삽입 정렬 - 고급 정렬 알고리즘 병합 정렬 퀵 정렬 힙 정렬 - 계수 정렬 기본 정렬 알고리즘(선택, 버블, 삽입 정렬) 1. 선택 정렬(Selection Sort) 선택 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 입력에 민감하지 않은 정렬이다. 또한 선택 정렬은 항상 일정한 시간 복잡도를 가지는 정렬 알고리즘이기도 하다. - 선택 정렬 알고리즘 ① 배열 A[1..n]에서 가장 큰 원소를 찾는다. ② 가장 큰 원소와 끝자리에 있는 A[n]과 자리를 바꾼다. -> 여기서 맨 뒷자리로 옮긴 원소는 자기 자리를 찾은 것이므로 이제 신경쓰지 않아도 된다. ③ 나머지 원소 n-1개에 대해서도 동일한 작업을 반복한다. - 선택 정렬 pesudo code select..
-
[알고리즘]재귀함수STUDY/Algorithm 2021. 3. 11. 11:57
재귀 함수란? 문제 해결을 위해, 원래 범위의 문제를 더 작은 문제로 쪼개 하위문제를 해결함으로써, 문제를 해결해 나가는 방식을 말한다. 재귀 함수를 사용할 때 장점은, 코드가 간결하고, 오류 수정이 용이하다는 것이다. 단점은, 코드를 이해하기 어렵고, 수많은 중복호출이 발생해 저장 공간을 많이 필요하다는 것이다. 예시를 살펴보자. int recursiveSum (int n) { if(n == 1) return 1; return n + recursiveSum(n - 1); } 이 recursiveSum 함수는, 1부터 n까지의 합을 구하는 함수를 재귀 호출을 이용해 구현한 것이다. n = 5일 때, 아래와 같이 동작한다. 모든 재귀함수는 if (n == 1)과 같이, 더이상 쪼개지지 않는, 최소한의 작업..