동적 계획법(Dynamic Programming)
- 작은 문제를 먼저 해결하고, 그 결과를 저장하여 반복 계산을 줄이는 최적화 기법
- 주로 최적 부분 구조를 지는 중복된 하위 문제들을 분할 정복으로 풀이하는 문제 해결에 사용된다.
- 이미 계산한 값을 저장하여 다시 계산하지 않게 해주는 메모이제이션과 작은 문제부터 해결하여 테이블을 채워가는 타블레이션의 특징이 있다.
재귀
- 알고리즘 자신을 사용하여 정의된 알고리즘을 재귀적이라고 한다.(비재귀적 or 반복적 알고리즘과 대조된다.)
- 계단에 비유해보면, 계단 끝까지 내려간 뒤에, 다시 올라오는 느낌으로, 우선 종료 조건까지 계속 재귀하고 종료 조건부터 하나씩 올라오면서 계산해 나가는 것이다.
재귀의 요소
- 재귀 케이스: 차후의 재귀 호출은 작아진 부문제들을 대상으로 이뤄진다.
- 베이스 케이스: 부문제들이 충분히 작아지면, 알고리즘은 재귀를 사용하지 않고 이들을 직접 해결한다.(종료 조건을 나타내는 경우이다.)
- 재귀 함수의 활용 예시
- 웹 크롤링 시에도 재귀 함수가 사용 될 수 있다. 주로 해당 페이지의 구조를 알 수 없거나, 복수가 글을 쓰는 공간을 Scrapping해야 할 경우 주로 사용한다.
- 파일 시스템을 탐색을 할 때도, 사용할 수 있다. 이런 계층적인 구조에서는 반복문(선형적 방식)보다는 재귀적 방식으로 사용하는 것이 더 좋다.
- 반복문을 사용하려면 깊이를 정해야하고, 계층 구조를 처리하기 힘들기 때문이다.
재귀 함수의 작동 원리
- 보류된 재귀 호출(시작했지만 완료하지 않고 대기 중인 호출들)을 위한 변수들에 관련된 저장/복구는 컴퓨터에 의해 자동적으로 수행한다.
- 즉, 더 이상 재귀가 필요하지 않을 때까지 재귀 함수의 계산을 보류한 상태로 넘어가고, 조건에 충족했을 때, 그 부분부터 계산하여 반환해 나간다.
재귀 함수의 기본 규칙
- 베이스 케이스: 베이스 케이스를 항상 가져야 하며, 이 부분은 재귀 없이 해결 가능한 종료 조건이다.
- 진행 방향: 재귀적으로 해결되어야 할 경우, 재귀 호출은 항상 베이스 케이스를 향하는 방향으로 진행된다.
- 정상 작동 가정: 모든 재귀 호출이 제대로 작동한다고 가정한다.
- 적절한 사용 꼭 필요할 때만 사용: 저장/복구 때문에 성능 저하
재귀 함수의 장, 단점
- 장점
- 변수를 여럿 만들 필요가 없다. → 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 할 수 있다.
- while문이나 for문 같은 반복문을 사용하지 않아도 되기에 코드가 간결해진다. 즉, 가독성이 좋다.
- 단점
- 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야한다. 이를 통해 반복문보다 더 많은 메모리를 사용하게 되고, 속도가 저하된다.
- 함수 호출 → 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.
- 이와 같은 단점을 해결하기 위한 것이 꼬리 재귀이다.
- 꼬리 재귀는 재귀 호출이 끝나는 시점에서 아무 일도 하지 않고 바로 결과를 반환하도록 하는 방법으로 함수의 상태 유지 및 추가 연산을 하지 않기에 스택 오버 플로우를 해결할 수 있다.
- stack overflow란 stack 영역의 메모리가 지정된 범위를 넘어갈 때 발생하는 오류이다.
응용 문제
- 하노이의 탑
- 하노이의 탑 문제를 해결하기 위하여 어떻게 움직여야 하는지를 출력
// 수도 코드
Alg rHanoi(n, from, aux, to)
input integer n, peg from, aux, to
output move sequence
if (n = 1) {base case}
write(“move from”, from, “to”, to)
return
rHanoi(n– 1, from, to, aux) {recursion}
write(“move from”, from, “to”, to)
rHanoi(n– 1, aux, from, to) {recursion}
// c 코드
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#pragma warning(disable:4996)
void hanoi(int n, char a, char b, char c) {
if (n == 1) {
printf("%c %c\n", a, c);
return;
}
hanoi(n - 1, a, c, b);
printf("%c %c\n", a, c);
hanoi(n - 1, b, a, c);
}
int main() {
int n;
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
- 유클리드 호제법
- 2개의 수의 최대 공약수를 반환
// 수도 코드
Alg gcd(a, b)
input integer a, b
output gcd(a, b)
if (b == 0) {base case}
retrun a
gcd(b, a % b) {recursion}
// c 코드
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#pragma warning(disable:4996)
int gcd(int n, int m) {
if (m == 0) {
return n;
}
return gcd(m, n % m);
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
printf("%d", gcd(n, m));
return 0;
}
PREVIOUS[자료구조] 스택(Stack)과 큐(Queue)