* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.
재귀호출로 피보나치 수 구하기
0 -> 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13...
맨 처음 : 0 / 두번쨰는 1 -> 그 다음부터는 앞 두 수를 더한 값
자바로 구현하면 아래와 같다.
public class 피보나치수 {
public static int fibonacci(int n){
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else{
return fibonacci(n-1) + fibonacci(n-2);
}
}
public static void main(String[] args) {
for(int n = 0; n <= 8; n++){
System.out.print(fibonacci(n) + " ");
}
}
}
맨 처음 : 0
다음은 1
그 이후는 앞 두 수를 더한 값 <-
이니까 이걸 그냥 짠 것이다...
0 1 1 2 3 5 8 13 21 <- 이렇게 나온다.
이걸 재귀 말고 동적 계획법(DP)으로도 짤 수 있는데,
분할한 문제의 답을 기억해 두고, 이를 재사용함으로써 같은 문제를 여러 번 푸는 낭비를 방지한다는 프로그래밍 기법이다.
public class 동적피보나치수 {
public static int[] fibonacciNumbers = new int[100];
public static int fibonacci(int n){
for(int i = 0; i<= n; i++){
if(i == 0){
fibonacciNumbers[i] = 0;
}else if(i == 1){
fibonacciNumbers[i] = 1;
}else{
fibonacciNumbers[i] = fibonacciNumbers[i-1] + fibonacciNumbers[i-2];
}
}
return fibonacciNumbers[n];
}
public static void main(String[] args) {
for(int n = 0; n <= 8; n++){
System.out.print(fibonacci(n) + " ");
}
}
}
결과는 이러하다.
0 1 1 2 3 5 8 13 21
이것은 재귀보다 루프가 더 효율적인 것!
근데 또 이거를 조합해서도 짤 수 있다.
initFibonacciNumbers 함수는 피보나치 수를 기억한 배열 fibonacciNumbers의 요소값을 모두 -1로 초기화한다.
-1은 피보나치 수가 구해지지 않았음을 나타낸다. (무조건 0보다 크니까!)
public class 혼합피보나치수 {
public static int[] fibonacciNumbers = new int[100];
public static void initFibonacciNumbers(){
for(int i = 0; i < fibonacciNumbers.length; i++){
fibonacciNumbers[i] = -1;
}
}
public static int fibonacci(int n){
System.out.println("피보나치 " + n +" 이 호출되었습니다.");
if(fibonacciNumbers[n] == -1){
if(n == 0){
fibonacciNumbers[n] = 0;
}else if(n == 1){
fibonacciNumbers[n] = 1;
}else{
fibonacciNumbers[n] = fibonacci(n-1) + fibonacci(n-2);
}
}
return fibonacciNumbers[n];
}
public static void main(String[] args) {
initFibonacciNumbers();
System.out.println(fibonacci(5));
}
}
피보나치 5 이 호출되었습니다.
피보나치 4 이 호출되었습니다.
피보나치 3 이 호출되었습니다.
피보나치 2 이 호출되었습니다.
피보나치 1 이 호출되었습니다.
피보나치 0 이 호출되었습니다.
피보나치 1 이 호출되었습니다.
피보나치 2 이 호출되었습니다.
피보나치 3 이 호출되었습니다.
5
재귀만 쓰면 15번이지만, 이렇게 조건을 추가하면 9번 호출된다.
배낭 문제는
배낭에 담을 수 있는 최대 무게가 정해져 있고, 무게의 가치가 표시된 물건이 여러 개 있을 때,
배낭의 최대 무게를 넘지 않도록 물건을 선택하여 배낭에 담으면서,
물건 가치의 합이 최대가 되는 조합을 구한다.
동적 계획법으로 배낭 문제(지수 시간 알고리즘)을 풀면 효율적으로 해결할 수 있다.
public class 배낭 {
//예제가 c가 기본이라 전역변수를 많이 쓴다...
public static final int KNAP_MAX = 6; //배낭 최대 무게
public static final int ITEM_NUM = 5; //물건 종류
public static char [] name = {'A', 'B', 'C', 'D', 'E'}; //물건 이름
public static int [] weight = {1, 2, 3, 4, 5}; //물건 무게
public static int [] value = {100, 300, 350, 500, 650}; //물건 가치
public static int [][] maxValue = new int[ITEM_NUM][KNAP_MAX+1]; //물건을 넣을지 판단한 직후의 최대 가치
public static int [] lastItem = new int[KNAP_MAX + 1]; //마지막에 넣은 물건
//item 번째 물건을 넣을지 판단한 직후 배낭의 내용을 표시하는 메소드
public static void showKnap(int item){
int knap; //0~6kg의 배낭
System.out.println(name[item] + "의 " + weight[item] + "kg " + value[item] + "원");
for(knap = 0; knap <= KNAP_MAX; knap++){
System.out.println(maxValue[item][knap]+"원");
}
for(knap = 0; knap <= KNAP_MAX; knap++){
if(lastItem[knap] != -1){
System.out.println(name[lastItem[knap]]+"를 넣음");
}else{
System.out.println("없음");
}
}
}
public static void main(String[] args) {
int item; //물건 번호
int knap; //0~6kg 배낭
int selVal; //임시로 물건을 선택한 경우의 가치 합계
int totalWeight; //중량 합계
item = 0;
for(knap=0; knap <= KNAP_MAX; knap++){
if(weight[item] <= knap){ //최대 무게 이하면 선택
maxValue[item][knap] = value[item];
lastItem[knap] = item;
}else{
//최대 무게 이하가 아니면 선택 안함
maxValue[0][knap] = 0;
lastItem[knap] = -1;
}
}
showKnap(item);
for(item = 1; item< ITEM_NUM; item++){
//1번째~ITEM_NUM-1까지 고려
for(knap = 0; knap<=KNAP_MAX; knap++){
if(weight[item] <= knap){
selVal = maxValue[item-1][knap-weight[item]] + value[item];
//선택한 경우 가치를 구해봄
if(selVal > maxValue[item-1][knap]){
maxValue[item][knap] = selVal;
lastItem[knap] = item;
}else{
maxValue[item][knap] = maxValue[item-1][knap];
}
}else{
maxValue[item][knap] = maxValue[item-1][knap];
}
}
showKnap(item);
}
//현재 배낭에 들어 있는 물건을 조사해서 정답 표시
System.out.println("배낭 물건 조사");
totalWeight = 0;
for(knap = KNAP_MAX; knap > 0; knap -= weight[item]){
item = lastItem[knap];
System.out.println(knap+"kg의 배낭에 마지막으로 넣은 물건 : " + name[item]);
totalWeight += weight[item];
System.out.println(name[item] + "의 " + weight[item] + "kg " + value[item] + "원 이다.");
System.out.println(knap+"kg - " + weight[item] + "kg = " + (knap-weight[item]) + "kg 이다.");
}
System.out.println("정답");
System.out.println("무게 합 " + totalWeight);
System.out.println("가치 최대 값 : " + maxValue[ITEM_NUM-1][KNAP_MAX]);
}
}
이런 식으로 짜는데,
정답
무게 합 6
가치 최대 값 : 800
배낭의 최대 무게, 물건 종류, 명칭, 무게, 가치를 정의한 필드와
item 번쨰 물건을 넣을지 판단한 직후 배낭의 내용을 표시하는 showKnap 함수,
main 문에서는 배낭에 들어 있는 물건을 조사하여 정답을 표시한다.
분할한 부분 문제의 정답은 maxValue[][]에 저장한다.
배낭 각각에 마지막으로 넣은 물건은 lastItem[]에 저장한다.
메인문에서 0번째 물건을 넣는 처리를 따로 구성한 이유는 1kg(100원)가치인 물건인 A를 배낭마다 넣는 처리이기 때문이다.
showKnap은 반복처리 안 해도 되는 곳이라 루프문 밖에서 실행한다.
다중 반복문으로 물건 하나씩 늘리면서 최대값 구하고 maxValue[][]에 저장하는 것은
최대 무게 이하인지를 고려하는 분기문을 쓴다.
이거를 가치가 큰 것부터 물건을 고르는 방식으로도 짤 수 있는데, 이걸 탐욕 알고리즘이라고 한다.
public class 배낭2 {
public static void main(String[] args) {
int KNAP_MAX = 6; //배낭 최대 무게
int ITEM_NUM = 5; //물건 종류
int totalWeight = 0; //무게 합계
int totalValue = 0; //가치 합계
char [] name = {'E', 'D', 'C', 'B', 'A'};
int [] weight = {5, 4, 3, 2, 1};
int [] value = {650, 500, 350, 300, 100};
for(int i = 0; i < ITEM_NUM; i++){
if(totalWeight + weight[i] <= KNAP_MAX){
System.out.println(name[i] + " 물건");
totalWeight += weight[i];
totalValue += value[i];
}else{
break;
}
}
System.out.println(totalWeight + " : 무게 합");
System.out.println(totalValue + " : 원");
}
}
사실 원하는 정답은 아닌데...
E 물건
5 : 무게 합
650 : 원
하지만 빨랐죠.... 같은 느낌으로... (-.-)
댓글
댓글 쓰기