[알고리즘] 그리디 알고리즘과 브루트포스 알고리즘

그리디(greedy) 알고리즘

: 탐욕의 알고리즘(?). 매 순간마다 주어지는 선택의 과정에서 현재의 상태에서만을 기준으로 더 나은 선택을 지향하는 알고리즘입니다

그리디 알고리즘은 현재 상태에서 최선의 선택을 함으로써 단편적이고 일시적인 부분에서 바라보았을 때에는 합리적이라고 할 수 있겠으나, 종합적으로 판단하였을 때 가장 합리적인 선택이라고 단정 지을 수는 없다는 단점이 있습니다. 때문에 어떤 상황인지에 따라서 잘 유의하고 사용해야 하는 알고리즘입니다!

그리디 알고리즘의 장점

• "수행시간": 동적 계획법이(DP,다이나믹 프로그래밍)라는 방법을 사용하기 때문에 다른 알고리즘 기법보다 수행 시간이 빠르다.
• "근사치": 완벽한 답안보다는 빠르고 간단하게 정답에 근접한 근사치를 찾는 것만으로 만족이 가능한 코드 구현에는 더욱 유용하게 쓰일 수 있다.

예시

: 거스름돈. 거슬러주어야 하는 돈이 명시되었을 때, 먼저 큰 화폐로 줄 수 있는 거스름부터 계산하고 차례로 남은 화폐에서 거슬러 줄 수 있는 금액을 환산하는 방법이 그리디 알고리즘의 대표적인 예로 들 수 있습니다!

코드 예제

자세한 예시를 위해 실제로 문제를 풀어보았습니당

문제: 백준 - 전자레인지(10162)
https://www.acmicpc.net/problem/10162

#include <iostream>

using namespace std;

int main() {
    int t, a, b, c;
    cin >> t;
    a = t / 300;
    b = (t % 300) / 60;
    c = (t % 300) % 60 / 10;
    if (t % 10 == 0) {
        cout << a << " " << b << " " << c;
    }
    else
        cout << -1;
}

풀이

1. 입력받은 값을 300으로 나눈 몫을 5분을 누르는 횟수.
2. 나누고 남은 나머지에서 60으로 나눈 몪을 1분을 누르는 횟수.
3. 거기에 10을 나눈 몫을 10초를 누르는 횟수.
4. 10으로 나누어 떨어진다면 5분, 1분, 10초를 눌러야 하는 횟수를 출력하고, 그렇지 않으면 -1을 출력.

실제로 큰 수부터 차례로 작은 수로 가면서 매번 최선의 선택을 한다는 것이 대표적인 그리디 알고리즘이죠. 그치만 해당 예제는 동적계획법을 사용하지 않은 예제입니다! 동적계획법은 이후에 다룰 이론이기 때문에 이를 배제한 예제를 작성하였습니다.

---

브루트포스(Brute Force) 알고리즘

: 무식한 알고리즘. 쉽게 노가다라고 표현할 수 있습니다. 완전 탐색을 기반으로 모든 경우의 수를 하나하나 조사하여 결과를 도출해 내는 알고리즘입니다.

브루트포스 알고리즘의 장점

• "간단함": 알고리즘의 구현이 비교적 간단하다. (설명마저 간단!)
• "정확함": 모든 경우의 수를 탐색하는 과정이기 때문에 예외 없이 결과가 도출될 것이다.

예시

: 암호를 푸는 과정을 브루트포스의 가장 큰 예로 들 수 있을 것 같습니다. 4자리 수의 자물쇠를 풀고자 한다면, 힌트가 없는 이상 0000부터 9999까지 모든 경우의 수를 하나씩 조사해 보는 수밖에 없습니다

코드 예제

자세한 예시를 위해 실제로 문제를 풀어보았다.
문제: 백준 - 셀프넘버(4673)
https://www.acmicpc.net/problem/4673

  #include <iostream>

using namespace std;

int main() {
    int a[10001];

    for (int j = 1; j <= 10000; j++) {
        int result;
        a[j] = j;
        for (int i = 1; i <= 10000; i++) {
            result = i + (i % 10) + ((i%100)/ 10) + ((i % 1000) / 100) + (i / 1000);
            if (j == result) {
                a[j] = 0;
            }
        }
    }

    for (int i = 1; i <= 10000; i++) {
        if (a[i] != 0)
            cout << a[i] << endl;
    }

    return 0;
}

풀이
기본 개념. 셀프넘버: 답+답의 각 자릿수에 있는 자연수들? ( * )

1. 1부터 10000까지의 숫자에 대해 각각의 셀프넘버 여부를 판별하기 위해 배열 a를 초기화합니다.
2. 중첩된 반복문을 통해 각 자릿수의 합을 계산하고, 해당 값이 배열의 인덱스와 일치하는지를 확인합니다.
3. 셀프넘버가 아니라면 배열의 값을 0으로 설정합니다.
4. 최종적으로 배열을 검사하면서 0이 아닌 값을 출력합니다.

상대적으로 단순한 알고리즘임을 알 수 있습니다.

반응형