1. 재귀함수(Recursive Function)
- 함수 안에서 자기 자신을 다시 호출하는 기법
- 함수 호출이 반복되다가 기저조건이 만족되면 호출을 중단하고 결과를 반한환다
재귀함수의 종료 조건
- 재귀 함수를 풀이에 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다
- 종료조건을 명시하지 않을 시에는 함수가 무한히 호출된다
def recursive_fun():
print('재귀함수 호출')
recursive_fun()
recursive_fun()
[출력]
재귀함수 호출
재귀함수 호출
재귀함수 호출
재귀함수 호출
재귀함수 호출
재귀함수 호출
재귀함수 호출
재귀함수 호출
재귀함수 호출
...
...
...
재귀함수의 구성
- 기저 조건(종료조건)
- 재귀 호출을 중단하는 조건
- 코드가 무한 루프에 빠지지 않도록 방지하며, 일반전으로 간단한 케이스에 해당
- 재귀 단계
- 함수가 자신을 호출하며 더 작은 부분으로 나누는 과정
팩토리얼 예제
팩토리얼의 정의는 n! = n x (n - 1) x (n - 2) x (n - 3) ... x 1 입니다. 위의 식과 같이 n이 1이 아닌 5라면 5!은 5 x 4! 을 호출하게 됩니다. 문제는 컴퓨터에는 ! 의 개념이 없습니다. 따라서 4! 은 다시 4 x 3! 으로 쪼개지게 됩니다. 이러한 부분에서 팩토리얼은 자신을 호출하는 형태가 반복되기 때문에 순환 알고리즘의 특성을 띕니다.
import sys
n = int(sys.stdin.readline().strip())
def factorial(n):
if n <= 1: # 기저 조건
return 1
else: # 재귀 단계
return n * factorial(n - 1)
print(factorial(n))
피보나치 수열 예제
- 이전 두 합으로 이루어지는 수열
- 종료조건 : n <= 1
- 재귀단계 : f(n) = f(n-1) + f(n-2)
def f(n):
if n <= 1: # 기저 조건
return n
else:
return f(n-1) + f(n-2) # 재귀 단계
유클리드 호제법 (Greatest Common Divisor) 예제
- 두 개의 자연수에 대한 최대공약수를 구하는 알고리즘
- 종료조건 : a % b == 0
- 재귀단계 : gcd(b, a % b)
두 자연수 A, B에 대하여 A % B의 결과를 R이라고 정의하자. 이때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다
| 단계 | A | B | R |
| 1 | 192 | 162 | 30 |
| 2 | 162 | 30 | 12 |
| 3 | 30 | 12 | 6 |
| 4 | 12 | 6 | 0 |
def gcd(a, b):
if a % b == 0: # 기저 조건
return b
else:
return gcd(b, a % b) # 재귀 단계
print(gcd(192, 162))
[출력]
6
재귀함수 문제풀이
- 백준 1914 하노이탑
https://www.acmicpc.net/problem/1914
- 백준 2947 나무조각
https://www.acmicpc.net/problem/2947
정리
이렇게 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결히 사용할 수 있습니당
하지만 모든 재귀함수가 반복문보다 유리한 것은 아니므로 필요성에 따라 알고리즘을 적절히 활용하도록 해요☺️
02. 정렬
01. 버블정렬
- 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(0, len(array) - i):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
print(array)
⌛버블정렬의 시간복잡도 / 공간복잡도
[시간복잡도]
- n개의 배열 사이클이 n-1, n-2 .. 상태로 반복되므로 O(n²
- 현재 리스트의 데이터가 거의 정렬된 상태라면 매우 빠르게 동작되므로 O(n)
[공간복잡도]
O(n)
02. 선택정렬
- 가장 작은 요소를 위치를 변수에 저장하고 맨 앞 데이터와 swap을 반복
- 버블에 비해 싸이클마다 1번의 swap만 일어난다는 점에서 효율적
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # swap
print(array)🔎 만약 배열이 [5, 3, 1, 4, 2] 라고 치자. 연산횟수를 세어보자
1 cycle 배열 전체를 검사하며 최소값 1 찾기, 5와 교환 (연산횟수 4번)
> [1, 3, 5, 4, 2]
2 cycle 최소값 2찾기, 3과 교환 (연산횟수 3번)
> [1 | 2, 5, 4, 3]
3 cycle 최소값 3찾기, 5와 교환 (연산횟수 2번)
> [1, 2 | 3, 4, 5]
4 cycle 최소값 4찾기, 비교 후 정렬 완료 (연산횟수 1번)
> [1, 2, 3 | 4, 5]
⌛선택정렬의 시간복잡도 / 공간복잡도
[시간복잡도]
- 선택정렬은 N번 만큼 가장 작은 수를 찾아서 앞으로 보냄
- N + (N - 1) + (N - 2) + ... + 2 + 1 => => O(n²)
[공간복잡도]
- 하나의 배열에서만 진행되므로 O(n)이다.
03. 삽입정렬
- 현재 위치에서 그 이하의 배열들을 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘
- 선택 정렬에 비해 구현 난이도가 높지만, 효율적임
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
else:
break
print(array)
⌛삽입정렬의 시간복잡도 / 공간복잡도
[시간복잡도]
- 선택 정렬과 마찬가지고 반복문이 두번 중첩되어 사용되므로 O(n²)
- 현재 리스트의 데이터가 거의 정렬된 상태라면 매우 빠르게 동작되므로 O(n)
[공간복잡도]
O(n)
04. 합병 정렬
- 함수가 호출될 때마다 재귀적으로 함수를 호출하고 정렬된 부분을 두 개씩 병합하면서 정렬하는 방법
- 큰 데이터셋을 정렬할 때 유용
# task 1. 절반씩 나눈다
>before : array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
>after : Left [7, 5, 9, 0, 3] Right [1, 6, 2, 4, 8]
# task 2. 원소가 하나 남을때까지 쪼갠다
> [7] [5] [9] [0] [3] [1] [6] [2] [4] [8]
# task 3. 나눈 부분을 차례대로 각각 정렬한다
# 임시공간에 리스트를 비교 후 병합
>before [7] [5] [9] [0] [3] [1] [6] [2] [4] [8]
ㅁㅁ
[5 7] [0 9] [3]
ㅁㅁㅁㅁ
[0 5 7 9] [3]
ㅁㅁㅁㅁㅁ
[0 3 5 7 9] [1 2 4 6 8]
>after [0 1 2 3 4 5 6 7 8 9]def merge_sort(arr):
# 배열의 길이가 1 이하이면 이미 정렬된 상태이므로 바로 반환
if len(arr) <= 1:
return arr
# 배열을 두 부분으로 나눈다
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# 재귀적으로 왼쪽과 오른쪽을 정렬
left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)
# 두 정렬된 배열을 병합
return merge(left_sorted, right_sorted)
def merge(left, right):
sorted_arr = []
i = j = 0
# 두 배열을 비교하여 작은 값을 차례대로 sorted_arr에 넣음
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
# 나머지 요소들을 그대로 추가
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
sorted_array = merge_sort(array)
print(sorted_array)
05. 퀵 정렬
- 피벗(기준 데이터)를 설정하고, 피벗보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
# 동작과정
1. 리스트의 한 요소 피벗을 선택(처음 or 중간 or 마지막)
2. 피벗을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽
3. 피벗을 제외한 왼쪽리스트와 오른쪽 리스트는 1,2번을 반복
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(arr):
# 배열이 비었거나 길이가 1이면 이미 정렬된 상태
if len(arr) <= 1:
return arr
# 피벗 선택 (여기서는 배열의 첫번째 원소를 피벗으로 선택)
pivot = arr[0]
another = arr[1:]
# 피벗을 기준으로 왼쪽에는 피벗보다 작은 값, 오른쪽에는 큰 값들이 오도록 배열을 나눈다
left = [x for x in another if x <= pivot]
right = [x for x in another if x > pivot]
# 재귀적으로 왼쪽과 오른쪽을 정렬하고, 피벗을 중간에 추가
return quick_sort(left) + [pivot] + quick_sort(right)
sorted_array = quick_sort(array)
print(sorted_array)
정리
[정렬 종류별 장단점]
[정렬종류 별 시간, 공간 복잡도]
| 정렬 종류 | 평균 | Best | Worst | 공간 복잡도 |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | O(n) |
| 버블 정렬 | O(n²) | O(n) | O(n²) | O(1) |
| 삽입 정렬 | O(n²) | O(n) | O(n²) | O(1) |
| 합병 정렬 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n²) | O(log n) |
'Tech > Algorithm' 카테고리의 다른 글
| 백준 1149 rgb 거리 [python] (0) | 2025.04.07 |
|---|---|
| 백준 1914 하노이 탑 [python] (0) | 2025.03.23 |
| 백준 2947번 나무조각 [python] (0) | 2025.03.21 |