무한리
2020-10-18 17:45:40 작성 2020-10-18 17:46:29 수정됨
9
931

과제좀 도와주세요 ㅠㅠ..


아무리 생각해도 잘 안되네요,,

언어는 아무거나 해도 되는뎅,, 혹시 푸셔보고 힌트라도 알 수 있을까용?


/* 과제내용입니다.

피보나치 수열

 

int fibonacci(int n){
if (n < 2)
return n;
else
return (fibonacci(n - 1) + fibonacci(n - 2));
}

 

피보나치 수열을 계산하기 위한 위 재귀호출은 분할 정복 기법이다. 그러나 이 분할 정복은 다른 분할 정복과는 차이가 있다. 예를 들어, 퀵 정렬이라면 피벗을 중심으로 왼쪽에 대한 정렬과 오른쪽에 대한 정렬은 서로 독립된 문제로서, 부분문제의 해끼리 연관되어 있지 않기 때문에 각각의 부분문제를 별도로 해결해야 한다. 그러나 이 경우는 그렇지 않다. fib(5) = fib(4)+ fib(3)으로 분할할 때, fib(4)fib(3)는 서로 연관된 문제다. fib(3)의 계산 결과를 fib(4) = fib(3) + fib(2) 계산에 재사용할 수 있기 때문이다.

 

 

fib(n)을 재귀호출로 푸는 과정을 트리로 그려보면 높이는 θ(n)이다. 2진 트리를 가정하면 이 경우 노드 수는 (2n+1 - 1)이다. 예를 들어, 높이 2인 정 2진 트리의 노드 수는 23 - 1 = 7이다. 모든 노드에서 피보나치 수열의 값을 계산해야하기 때문에 이 경우 효율은 O(2n)으로서 지수 시간이 걸린다. 그런데 그림의 노드를 보면 동일한 계산이 반복됨을 알 수 있다. 이를 중복 부분문제(Overlapping Subproblem)라고 부른다. 위 재귀호출의 효율이 지수 함수가 된 이유는 중복된 부분문제에 대한 아무런 고려 없이 반복적으로 풀기 때문이다.

 

동적 프로그래밍 기법(Dynamic Programming Method)은 작은 문제의 해를 기억하고 있다가 그것을 큰 문제의 해를 구하는데 재사용하는 기법을 말한다. 주어진 문제를 부분문제로 분할한다는 측면에서 분할 정복 기법과 동적 프로그래밍 기법과 매우 유사하다. 그러나 분할 정복과는 달리 동적 프로그래밍에는 재사용이라는 개념이 존재한다. , 반드시 부분문제에 대한 해를 기록해 놓고 또, 반드시 그것을 그보다 큰 문제를 해결하는데 활용한다. 메모를 한다는 뜻에서 부분문제의 해를 기록해 놓는 작업을 메모이제이션(Memoization)이라 부른다.

 

for (i = 0; i <= n; i++) // 이미 계산되어 있는지 여부를 done 배열에 저장
done[i] = false; // 모두 계산되지 않은 것으로 초기화
memo[0] = 0; done[0] = true; // 첫 항의 피보나치 값 저장, 계산된 것으로
memo[1] = 1; done[1] = true; // 둘째 항의 피보나치 값 저장, 계산된 것으로

int fibonacci(int n){
if (done[n] == true) // 이미 계산되어 있으면
return memo[n]; // 그것을 재사용
else { // 아직 계산되지 않았으면
temp = fibonacci(n - 1) + fibonacci(n - 2); // 재귀호출
memo[n] = temp; // 결과 값을 memo 배열에 저장
done[n] = true; // 이미 계산된 것으로 표시
return temp; // 결과를 리턴
]

 

피보나치 문제에 동적 프로그램 기법을 적용한 예다. 이전 예와 동일한 재귀호출이지만 한 번 계산한 것은 두 번 다시 계산하지 않는다. memo[n]fibonacci(n) 값을 저장한 배열이고, done[n]은 값이 이미 계산되어 있는지 여부를 나타낸다. if 문의 조건에 의해 이미 계산되어 있으면 그것을 재사용한다. 그렇지 않으면 else 내부의 재귀호출에 의해 fibonacci(N)을 계산하여 memo[n]에 저장하고 또, done[n]true로 놓음으로써 이미 계산되어 있다고 표시한다. 다시 말해, 부분문제의 해를 memo 배열에 메모해 놓고 재사용함으로써 동일한 계산을 반복하지 않는다.

 

그림입니다.

원본 그림의 이름: CLP00001dc00008.bmp

원본 그림의 크기: 가로 593pixel, 세로 441pixel

 

T(N) = T(N - 1) + T(N - 2)
= T(N - 1) + 1
= T(N - 2) + 1 + 1
= ... = T(0) + N = O(N)

 

일반적인 재귀호출과 달리 이 방법의 효율은 O(N)이다. 재귀호출 순서에 의하면 fib(5), fib(4), fib(3), fib(2) 순서로 가서 베이스 케이스인 fib(1)fib(0)를 만나면 fib(2) = fib(1) + fib(0)가 확정된다. 이후 호출함수인 fib(3)로 되돌아가서 fib(3) = fib(2) + fib(1)를 계산한다. 그런데 이 시점에 fib(1)은 이미 초기화에 의해 계산이 완료된 상태다.

 

이후 호출함수인 fib(4)로 되돌아가서 fib(4) = fib(3) + fib(2)를 계산한다. 그런데 이 역시 이 시점에 fib(2)는 이미 계산이 완료된 상태다. 같은 맥락에서 fib(5)를 계산할 시점에 fib(3)은 이미 계산이 완료된 상태다. 다시 말해, 모든 내부 노드의 오른쪽 자식 노드는 이미 왼쪽 자식 노드를 구하는 도중에 계산이 완료된 상태다. 따라서 값을 평가하기 위해 그 아래 서브트리로 내려가지 않는다. 따라서 에서 T(N - 2)O(1)이라 할 수 있다. memo 배열에서 읽어오는 작업은 O(1)이기 때문이다. 결국 위 식에 의하면 이 알고리즘의 효율은 O(N)이다. 크기 N의 문제를 그보다 작은 문제로 나누어 해결하는 도중, 작은 문제의 해결책을 재사용하기 때문에 이러한 방식을 하향식 동적 프로그래밍(Top-down Dynamic Programming)이라 부른다.

 

 

// 메모이제이션에 대한 설명.

 

 

거스름 돈 문제 I

 

거스름돈 문제(Coin Change Problem)에 탐욕 알고리즘을 적용해 보자. 이 문제는 잔돈을 어떻게 거슬러 주어야, 동전의 개수를 최소화하는지를 묻는 문제다. 예를 들어, 어떤 자판기가 500, 100, 50, 10원 짜리 동전을 갖고 있을 경우, 잔돈이 280원이라면 10원 짜리 28개로 주어도 되지만, 50원 짜리 5개와 10원 짜리 3개로 해서 총 8개로 주어도 된다. 더 나은 방법은 없는가.

 

greedy_change(change){ // chage는 거스름돈
given = 0; // 돌려준 돈
while (given < change){ // 돌려준 돈이 거스름돈보다 작으면
pick the largest coin; // 가장 단위가 큰 동전을 선택
if (given + coin > change) // 돌려준 돈과 그것의 합이 거스름돈보다 크면
reject and do not pick the coin again; // 그 동전은 포기
else{ // 그렇지 않으면
give the coin; // 그 동전을 돌려주고
given += coin; // 돌려준 돈의 총액을 갱신
]

 

탐욕 알고리즘을 적용하려면 일단 고액권을 최대한 많이 사용하는 것이 해결책이 될 수 있다. 거스름돈이 280원일 경우, 500원은 너무 크기 때문에 일단 100원짜리 2개를 주면 80원을 더 거슬러 주어야 한다. 따라서 50원 짜리 1개를 주고, 다시 10원 짜리 3개를 주면 총 6개가 된다.

 

 

{8원 문제의 최적해}
= {5} + {3원 문제의 최적해}
= {5} + {1} + {2원 문제의 최적해}
= ... = {5, 1, 1, 1}

 

어떤 나라의 동전이 10, 5, 4, 1원 단위로 이루어져 있을 때, 8원을 거슬러 주려고 한다고 가정해 보자. 만약 이 알고리즘이 최적 부분구조를 갖추고 있다면 이 문제는 위 식에 의해 풀 수 있다. , 탐욕적 선택에 의해 일단 5원을 주고, 남은 부분문제인 3원 문제에 대한 부분해를 구하면 된다. , 3원을 거슬러 주는 문제에 대해서도 탐욕 알고리즘을 적용하면 1원 짜리 3개를 주면 된다. 따라서 이 알고리즘에 따르면 동전의 개수는 4개가 최적해다.

 

그러나 이 문제에 관한 한, 탐욕 알고리즘은 일정한 전제 하에서 최적 부분구조 속성을 지닌다. 실제로 이 문제의 해는 {4, 4}으로서 동전 2개가 최적이다. 작은 단위의 동전 2개를 합친 금액이 그보다 큰 단위의 동전보다 크거나 같으면 이러한 현상이 일어난다. 예에서는 (4 + 1) 5이기 때문이다. 이를 등 넘기(Leap Frog) 현상이라 부른다. 화폐 단위에 등 넘기 현상이 일어날 때에는 위 식이 참이 아니다. 다시 말해, 이 문제에 있어서 탐욕 알고리즘은 최적 부분구조를 갖추지 못한다. 부분해인 {5}이나 {1}이 전체해인 {4, 4}에 포함되지 않기 때문이다. 탐욕적 선택 속성도 참이 아니다. {5}이나 {1}으로 시작하는 최적해가 존재하지 않기 때문이다.

 

인천에서 뉴욕까지 가는 가장 싼 비행기 표를 예로 들어 최적 부분구조를 설명해 보자. 이 경우는 서울에서 부산까지 가는 최단 경로 문제와는 다르다. 인천동경LA뉴욕으로 가는 비용이 가장 싸다고 해서, 동경LA뉴욕으로 가는 비용도 가장 싸다고 말할 수는 없다. 예를 들어, 동경LA뉴욕으로 가는 비용은 매우 비싸지만, 인천동경으로 가는 비용이 그보다 훨씬 싸기 때문에 전체적으로 가장 싼 비행기 표가 될 수도 있다. 따라서 이 문제에 관한 비용은 최적 부분구조 속성을 지니지 않는다. , 부분문제에 대한 최적해가 단지 해당 부분문제에 대한 최적해에 그칠 뿐, 문제 전체에 대한 최적해의 일부로 포함되지는 않는다.

 

 

 

거스름 돈 문제 II

 

전술한 대로 거스름돈 문제(Coin Change Problem)에서 등 넘기 현상이 일어나면 탐욕 알고리즘으로는 문제를 풀 수 없다. 그 경우에도 최적해를 구할 수 있는 알고리즘을 생각해 보자.

 

int minimum_coins(coin_list, change){
min_coins = change;
if (change is in coin_list)
return 1;
else {
for each coin in coin_list
if (coin < change){
num_coins = 1 + minimum_coins(coin_list, change - coin);
if (num_coins < min_coins)
min_coins = num_coins;
}
return min_coins;
]

 

거스름돈 문제를 백트래킹으로 푸는 알고리즘이다. 만약 동전 단위가 1, 10, 15, 20원이면 인자인 coin_list1, 10, 15, 20으로 구성된 배열이다. , change는 잔돈 액수다. min_coins는 잔돈을 모두 1원 짜리로 줄 때 필요한 동전 수다. 만약 잔돈이 coin_list에 있는 동전 단위와 일치하면 에 의해 1개를 리턴 한다. 그렇지 않으면 coin_list에 있는 각 동전 단위에 대해 의 루프를 돌린다. 는 그 동전을 포함할 때의 최소 동전 수다. 우변 첫 항인 1은 동전 수가 하나 늘어남을 나타낸다. 둘째 항이 재귀호출로서, 그 동전의 금액을 제외한 나머지 금액에 대한 최소 동전 수다. 루프를 돌면서 에서 각 동전을 선택할 때마다 가능한 최소 동전 수를 갱신하고 에서 그것을 돌려준다. 이를 재귀 관계식으로 표현하면 아래와 같다.

 

minimum_coins
= min( 1 + minimum_coins(change - 1), 1 + minimum_coins(change - 10),
1 + minimum_coins(change - 15), 1 + minimum_coins(change 20))

 

그림입니다.

원본 그림의 이름: CLP0000258c0002.bmp

원본 그림의 크기: 가로 819pixel, 세로 407pixel

 

백트래킹 알고리즘의 결정 트리다. 노드 옆의 숫자는 잔액을 나타낸다. 동전 단위 별로 링크가 갈라진다. 물론 이 방법은 타당성을 기준으로 가지를 쳐내기 때문에 억지 기법보다 낫다. 예를 들어 잔액 8인 노드에서 내려오는 20, 15, 10은 가지를 쳐 낸다. 동전 금액이 잔액보다 크기 때문이다.

 

하향식 동적 프로그래밍 기법을 쓸 수도 있다. 피보나치보다는 중복 노드가 적을 수 있지만, 이미 최소 동전 수를 계산한 잔액(노드)은 재사용할 수 있기 때문이다.

 

분기 한정 기법을 적용하여 추가로 가지를 쳐낼 수도 있다. 루트에서 리프까지 내려오는 경로의 길이가 바로 동전의 개수다. 따라서 항상 지금까지의 최소 경로를 추적하고 그보다 길면 가지를 쳐 낼 수 있다.

 

 

 

문제:

 

1. 거스름돈 문제를 백트래킹에 의해 푸는 알고리즘을 코딩으로 구현하라. , 프로그램 언어는 어떤 것을 써도 무방하다.

 

> Enter the Coin Unit

> 1, 10, 15, 20

> Enter the Total Change

> 24534

> Answer: You need ? 1’s, ? 5’s, ? 15’s, ? 20’s. (물음표 안을 채울 것)

> 필요한 총 동전 수는 ?개입니다.

> Running Time is ? minutes. (프로그램 실행 시간을 적을 것)

 

2. 1에 하향식 동적 프로그래밍 기법을 추가하여 알고리즘의 실행 속도를 개선한 다음, 위 출력을 통해서 Running Time이 줄어든 것을 보여라.

 

 

3. 1에 분기 한정 기법 기법을 추가하여 알고리즘의 실행 속도를 개선한 다음, 위 출력을 통해서 Running Time이 줄어든 것을 보여라.

 

 

 

 

참고: 아래 코드를 참조로, 소스 코드에 time 함수를 넣어서 실행 시간 측정

 

#include <stdio.h>
#include <time.h>
int main( ){
time_t now; char* str;


now = time(NULL);
str = ctime(&now);
printf("Current time is : %s.\n", str);
return 0;
}

time_t time(time_t* ptr);
char* ctime(const time_t* ptr);

 

time.h 파일에는 시간 관련 함수가 선언되어 있다. time_t 타입은 경과 시간을 초 단위로 표현하기 위해 정의된 int 타입이다. time 함수는 19701100:00:00 이후 지금까지 경과한 시간을 초 단위로 리턴하는 함수다. 따라서 에 의해 그 값이 now에 저장된다. 이제 now를 가리키는 포인터를 의 인자로 넘겨주면 ctime 함수는 현 시점의 요일, , , 시간, 연도 등을 문자열을 리턴한다.


*/

-5
0
  • 댓글 9

  • pooq
    5k
    2020-10-18 18:52:37

    양심도 없고, 개념도 없는데 노력도 안하는 사람이네. 

  • 코딩으로밥벌어먹자
    136
    2020-10-18 19:32:44

    허허 이렇게 모든 문제를 가져올줄은 몰랐네요 ㅋㅋㅋㅋㅋ

    적어도 나중에 직장가셔서 물어볼때는

    해결할문제 -> 본인 생각 -> 그에 발생한 문제 -> 의문점 질문 으로 물어보시길 바랍니다.

    안타깝지만 여기 이런 긴 날것의 문제들 대답해줄 사람 없을거에요 

  • 답정너심판자
    2k
    2020-10-18 20:16:48

    아무리 생각하긴 뭘 아무리 생각해요

    생각한 흔적이 없구만

  • 만년코더
    7k
    2020-10-18 20:24:39
    이건 뭐지? 
  • 이오니
    1k
    2020-10-18 22:15:20

    ..... 이거 규칙 못찾으면... 그냥 이 길 포기하셔도 됩니다...;;;

    코드.. 못짤 수도 있죠... 당연히..;;;

    근데 말로 설명 못하는 단계면... 진짜 고민해보셔야해요..;;;

  • 나카지마요코
    126
    2020-10-19 00:55:11

    차라리 다 알려달라고 하시지 힌트 요구는  교수한테 묻고요

  • 어우배야
    41
    2020-10-19 11:13:14

    문제안에 힌트도 다 있고

    검색만 해도 나오는걸...

    음...


  • 말년개발
    2k
    2020-10-19 14:14:17

    아..어그로한테도 비추를 안누르는데 

    이건 참을 수 없네요.

  • 재현아빠
    3k
    2020-10-20 08:27:19

    ㅋㅋ 이미 탈퇴하셨지만, 학생이라면 다른 과로 옮기시고 직장인이라면 다른 직업을 알아보심이 좋을 듯 합니다.

  • 로그인을 하시면 댓글 을 등록할 수 있습니다.