순환 (Recursion)
- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
- 정의 자체가 순환적으로 되어 있는 경우에 적합
- 대표적으로 팩토리얼 값 구하기와 피보나치 수열 문제가 있다.
팩토리얼 프로그래밍
- (n-1)! 팩토리얼을 현재 작성중인 함수를 다시 호출하여 계산
int factorial(int n)
{
if (n<=1) return(1); # 순환의 종료조건
else return (n*factorial(n-1)); # 순환 본문
}
- 순환의 종료조건이 순환을 하는 본문보다 반드시 먼저 있어야 한다.
- 반복문 (for문)을 이용해서도 구할 수 있고, 코드의 길이도 큰 차이는 없지만, 가독성이 떨어지고 복잡한 문제는 코드도 길어진다.
< 순환의 비효율성 >
- fibo(3)을 이미 구했지만 다른 fibo값을 구할때 중복적으로 구한다.
- memoization을 사용하는 DP 알고리즘을 이용하여 해결 가능!
그리디 알고리즘
Greedy method : 매 단계 가능한 해들 중 가장 좋은 해를 찾는 기법
= 항상 매 순간마다 최선의 선택을 한다.
동전 거스름돈 문제
- 물건을 사고 거스름 돈을 동전으로만 받아야 하는 상황에서, 가장 적은 수의 동전을 받을 수 있는 방법은 무엇인가?
단, 동전으로는 500원, 100원, 50원, 10원이 사용된다.
-> 500원을 사용할 수 있는 만큼 사용하고, 이후에 100원, 50원, 10원을 사용할 수 있는 만큼 사용한다.
< 동전 거스름돈 문제의 특수한 경우 >
만약 160원 동전이 추가 발행된다면, 그리디 알고리즘이 항상 최소 동전 수를 계산할 수 있을까?
- 그리디 알고리즘: 거스름돈이 200원이라면, 160원 동전 1개와 10원 동전 4개로서 총 5개를 리턴
- 그리디 알고리즘은 항상 최적의 답을 주지는 못함
- 동전의 종류가 서로 약수,배수의 관계라면 그리디 알고리즘은 항상 최적의 해를 구해준다.
부분 배낭 문제
- n개의 물건이 각각 1개씩 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제
- 두개의 문제로 나뉜다.
-> 부분 배낭 문제
- 물건을 부분적으로 담는 것을 허용
- 그리디 알고리즘으로 해결 가능
Greedy method: 단위 무게 당 가장 값나가는 물건을 반복해 배낭에 넣는다.
- 만일 물건을 '통째로' 넣을 수 없으면, 넣을 수 있을 만큼만 부분적으로 배낭에 넣는다.
- 입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C
- 출력: 배낭에 담은 물건 리스트 L과 배낭 속의 물건 가치의 합 V
-> 0-1 배낭 문제
- 부분 배낭 문제의 원형으로 물건을 통째로 배낭에 넣어야 한다.
- DP 알고리즘으로 해결 가능
잘생겼다