2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/알고리즘 수학

[컴퓨팅사고력] 약수물을 뜨는 시간을 최소화 해보자

원당컴1 2022. 2. 10. 17:23

원당이가 사는 원당동 금정산에는 약수터가 있습니다.

약수터의 물은 1초에 1리터씩을 담을 수 있습니다.

원당이가 약수터에 올라가 보니 사람들이 약수통을 들고 가장 최소한의 시간을 대기해서 물을 받으려면 어떤 순서대로 받는것이 가장 좋을지 논의 하고 있었습니다.

지금 약수터에 물을 받고 싶어하는 사람은 네명이며 첫번째 사람은 3리터, 두번째 사람은 5리터, 세번째 사람은 2리터, 네번째 사람은 1리터 들이 물통을 가지고 있습니다.

이때 첫번째,두번째,세번째,네번째 순으로 물을 받는다면 대기한 시간은 첫번째 사람은 자신의 물을 받는 시간 3초 + 두번째 사람은 3초 대기후 자신의 물을 받는 시간 5초 이므로 8초 + 세번째 사람은 8초 대기후 자신의 물을 받는 시간 2초 이므로 10초 + 네번째 사람은 10초 대기후 자신의 물을 받는 시간 1초이므로 11초 로 총 합은 32초를 대기하게 됩니다.

원당이는 이것보다 더 좋은 방법이 없는지 궁금합니다.

여러분이 원당이를 도와 주세요.

 

문제풀이

물받는 시간이 적은 순서로 물을 받으면 대기 시간을 줄일 수 있습니다.
즉 네번째사람(1리터),세번째사람(2리터),첫번째사람(3리터),두번째사람(5리터) 순으로 물을 받으면 
네번째사람은 1초,
세번째사람은 1초 + 2초 = 3초
첫번째사람은 3초 + 3초 = 6초
두번째 사람은 6초 + 5초 = 11초
총 합은 21초 입니다.

 

컴퓨팅사고력

이러한 문제는 컴퓨팅 사고력의 그리디알고리즘(탐욕알고리즘) 으로 해결이 가능합니다.

그리디 알고리즘은 자신의 순서에 최선의 값을 선택해 주는 알고리즘입니다.

이러한 그리디 알고리즘은 자신의 순서에 최선의 값이 올 수 있도록 데이터를 나열 하는 것이 중요합니다.

또한 그리디 알고리즘을 이용하기 위해서는 그리디 알고리즘을 사용할 수 있는지 증명하는 방법이 중요합니다.

위와 같은 문제를 그리디 알고리즘을 사용할 수 있는지 증명을 하기 위해서는 먼저 물통을 작은 순서부터 큰 순서로 나열을 하는 경우 1,2,3,5 와 같이 정렬을 할 수 있습니다.

이때 i번째까지 총대기시간을 Ti 이고 i번째 사람이 대기한 시간 Di, i번째 사람이 물을 받는 시간을 t(i) 라고 하면

i+1번째 까지 대기하는 시간 T(i+1) = Ti + Di + t(i+1) 이 됩니다.

Di = D(i-1) + t(i) 이고

T(i) = T(i-1) + D(i-1) + t(i) 입니다. 

T(i+1) = T(i-1) + D(i-1) + t(i) + D(i-1) + t(i) + t(i+1)이 됩니다.

따라서 i+1 까지의 총합은 t(i) 가 두번 더해 지고 t(i+1) 이 한번 누적 됩니다.

따라서 t(i) < t(i+1) 이 t(i) > t(i+1) 보다 반드시 작게 된다는 것을 확인 할 수 있습니다.

 

이렇게 확인 후에 그리디 알고리즘으로 순차적으로 해결하면 됩니다.

위의 문제를 c언어로 구현하면 다음과 같이 구현할 수 있습니다.

    int arr[]={3,5,2,1};
    sort(arr,arr+4);
    int tsum=0; ///기다린 시간의 합
    int dsum=0; ///기다리는 시간
    for(int i=0;i<4;i++){
        tsum+= dsum + arr[i];
        dsum+= arr[i];
    }
    cout << tsum;

 

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기