[Algorithm] 재귀
2023. 5. 3. 20:59ㆍComputer Science/알고리즘
✅ 재귀 알고리즘이란?
- 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다.
- 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것이다.
✅ 장점
- 점화식과 종료조건만 구현하면 만들 수 있기 때문에 가시성이 높고, 구현하기 쉽다.
✅ 단점
- 재귀함수의 종료 조건을 잘 설정해주지 않으면 재귀함수를 빠져나오지 못하게 되면서 무한루프에 빠질 수 있다.
- 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용한다.
✅ 해결방법
- 절차 지향적사고를 버리고 귀납적 사고로 접근해야 한다.
✅ 예시 문제
https://www.acmicpc.net/problem/24460
24460번: 특별상이라도 받고 싶어
첫 번째 줄에는 정수 $N$이 주어진다. (단, $N = 2^m$, $0 \le m \le 10$, $m$은 정수) 두 번째 줄부터 $N$개 줄의 $i$번째 줄에는 $i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$개의 추첨
www.acmicpc.net
https://www.acmicpc.net/problem/18222
18222번: 투에-모스 문자열
0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에
www.acmicpc.net
'Computer Science > 알고리즘' 카테고리의 다른 글
| [Algorithm] greedy (0) | 2023.05.03 |
|---|---|
| [알고리즘] 정렬 (0) | 2022.01.26 |