[알고리즘] 그리디 알고리즘 개념 & C언어.ATM(11399번)

 

 

 

분명 나는 알고리즘을 배웠는데... 왜 다 까먹은 것일까...

그리디 알고리즘.. 뭔가 이름만 들어도 욕심쟁이같은 느낌이 든다 !!

---

 

그리디 알고리즘 (Greedy Algorithm)

눈앞의 이익만 우선 추구하는 알고리즘 (Greedy = 탐욕스러운)

 

[개념]

• 최적해를 구할때 눈 앞에 가장 좋아 보이는 선택을 반복하여 최적해를 찾는 알고리즘.

• 최적해를 보장하진 않음. (그 상황에서 좋아 보이는 선택을 하기 때문에 대부분 뛰어난 결과를 도출하지 못함.)

• 극단적으로 문제에 접근함. (무조건 숫자가 높은순으로, 무조건 숫자가 낮은 순으로, 무조건 짧은 순으로 등등..)

 

[예시]

Q. 동전 660원의 동전 갯수는?

• 조건 : 무조건 금액이 높은 동전 순서대로     >>>>    극단적인 조건

  • 500원 > 1개

  • 100원 > 1개

  • 50원 > 1개

  • 10원 > 1개

     

총 4개의 동전만 있으면 된다.

이렇게 단순한 경우의 수만 따져가면서 탐욕적으로 해를 찾는 기법을 그리디 알고리즘 이라고 할 수 있다. 

 

---

 

ATM 문제는 버블정렬과 malloc 함수를 배울 수 있는 예제이다. 

백준 문제를 풀어보면서 그리디 알고리즘을 코드에 적용해보자!

 

[백준 문제]

 

 

 

 

이 문제에서 해를 구하기 위한 조건은 가장 적은 시간 순서이다.

가장 시간이 적은 순서대로 정렬을 하여 문제를 풀어보았다. 

 

malloc () : 메모리 공간 할당 함수 (동적배열 가능)

버블정렬 : 모든 요소를 비교하여 큰 숫자가 뒤에 위치하도록 정렬.

 

 

 

# 소스코드

#include <stdio.h>
#include <stdlib.h>  // malloc, free

int main()
{
    int size, i, temp, result=0;
    int *arr;

    scanf("%d\n",&size);

    arr = (int *)malloc(sizeof(int) * size);

    for (i=0;i<size;i++) scanf("%d",&arr[i]);

    for (i=0;i<size;i++) {
        for (int j=0;j<size-1; j++) {
            if(arr[j] > arr[j+1]){    // bubble sort
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    for (i=0;i<size;i++) {
        result += arr[i]*(size-i);
    }

    printf("%d",result);
    free(arr);
}

 

# 결과

---

 

많은 알고리즘이 그리디 알고리즘에 속한다고 한다.

그만큼 활용도가 높은 알고리즘으로 까먹지 말고 활용할 수 있도록 하자!!

---