Greedy

현재 상황에서 지금 당장 좋은 것만 고르는 방법

보통의 코테에서 그리디유형의 문제는 창의력, 즉 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

거스름돈

거스름돈으로 사용할 500원, 100원, 50원, 10원이 무한히 존재할 때, 손님에게 거슬러줘야할 돈이 N원이라면, 거슬러줘야할 동전의 최소 개수를 구하라. 단 거슬러줘야할 돈 N 은 항상 10의 배수이다.

→ 가장 큰 화폐단위부터 돈을 거슬러주는것. → 500, 100,50,10원 순으로 가는것이 Greedy알고리즘

def solution(coins, N):
    answer=0
    coins = sorted(coins, reverse=True)
    for coin in coins:
        answer += N // coin
        N = N % coin
    return answer
solution([10,50,100,500], 1260)

이런식으로 가장 큰 동전단위부터 순간순간으로 선택하는것이 그리디알고리즘이다.

#include<bits/stdc++.h>
using namespace std;
int n=1260;
int cnt=0;
int coins[4] = {500,100,50,10};
for (int i=0; i<4; i++) {
    int coin = coins[i];
    cnt += n/coin;
    n %= coin;
}
cout << cnt << endl;

위와같은 방식으로 가장 큰 화폐단위부터 가장 작은 화폐단위까지 차례대로 확인해서 거슬러줄 수 있다 .

위 방식이 가능했던 이유는 갖고있는 동전 중 큰 단위가 항상 작은단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

예를들어 화폐단위가 500, 400, 100 의 경우 800원을 거슬러줘야한다면, 그리디알고리즘에서는 500 + 100*4 가 되어 5개가 된다.

하지만 400 + 400 의 두개의 동전으로 해결할 수 있다.

큰수의 법칙

N개의 수를 가진 array에 대하여, 해당 배열의 주어진 수들을 M번 더하여 가장 큰 수를 만드는데, 여기서 배열의 특정한 인덱스에 해당하는 수가 연속으로 K번 초과하여 더할 수 없는 상황.

n=5;m=8;k=3
data=[2,4,5,4,6]
data = sorted(data)
answer=0
cnt=0
while cnt<8:
    for _ in range(k):
        answer+=data[-1]
        cnt+=1
    answer+=data[-2]
    cnt+=1
answer

위와같이 루프를 형성해서 반복을 시킬 수 있다.

하지만

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> v;
int main(){
    // N,M,K를 공백을 기준으로 구분하여 입력받기
    // cin >> n>>m>>k;

    // for (int i=0; i<n; i++){
    //     int x;
    //     cin>>x;
    //     v.push_back(x);
    // }
    n=5; m=8; k=3;
    v={2,4,5,4,6};
    sort(v.begin(), v.end()); //입력받은 수 정렬
    int first = v[n-1];
    int second = v[n-2];

    int cnt = (m/(k+1))*k;
    cnt += m % (k+1);

    int result = 0;
    result += cnt*first;
    result += (m-cnt)*second;

    cout<<result<<endl;
}

위와같이 $(m/(k+1))*k$ 의 식을 통해서 한번에 카운팅을 진행해 버릴 수 있다.

이걸 보면, $(더할 수\ 개수 / (최대반복+1))\ *\ 전체숫자수$ 이다.
연속으로 더할 수 있는 횟수는 최대 K번이므로, 가장 큰수를 k번 더하고, 두번쨰큰수를 한번 더하는 연산의 반복이 된다.

1이 될 때까지

어떠한 수 N이 1이 될 떄까지 두 과정 중 하나를 반복적으로 선택하여 수행

1. N에서 1을 뺸다.
2. N이 K로 나누어떨어진다면 K로 나눈다.

이렇게 연산할 때 N을 1로 만드는 최소 수행 수를 구하기

예를들어 N = 17 , K=4라면,

1번수행 (N=16)
2번수행 (N=4)
3번수행 (N=1)로 종료

최종 3번 실행으로 종료

def solution(n,k):
    answer=0
    while n!=1:
        answer+=1
        if n%k==0:
            n = n//k
        else:
            n -=1
    return answer
solution(17,4)

#include <bits/stdc++.h>
using namespace std;
int n,k;

int main(){
    // N,K를 공백을 기준으로 구분하여 입력받기
    // cin >> n >> k;

    n=17; k=4;
    int answer = 0;
    cout<<n<<endl;
    while(n>1){
        answer +=1;
        if (n%k == 0){
            n /= k;
        }
        else{
            n -=1;
        }
        cout<<n<<endl;
    }
    return answer;
}

시각

주어진 시간 n 에 대하여 00시 00분 00초부터 n시 59분 59초까지 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하자!

여러 계산을 통해 하나하나 확인하지않고 곱셈을 통해 가능하겠지만.. 시간적 여유로 다음문제를 풀러 뛰어가야하는 상황이라면 얼른 완전탐색으로 코딩해서 돌리고 다음문제에 더 집중하는것이 맞다고 생각된다..

def solution(n):
    cnt=0
    for h in range(n+1):
        for m in range(60):
            for s in range(60):
                if '3' in str(h)+str(m)+str(s):cnt+=1
    return cnt
print(solution(5)) 

#include <bits/stdc++.h>
using namespace std;
// int h,cnt;
int h=5;
int cnt=0;
int main(){
    for (int i=0; i<=h;i++){
        for(int j=0;j<60;j++){
            for(int k=0; k<60;k++){
                if (i%10==3 || j/10==3 || j%10==3 || k/10==3 || k%10 ==3){
                    cnt+=1;
                }
            }
        }
    }
    cout<<cnt<<endl;
}