💎그리디 알고리즘

그리디 알고리즘은 국내에서는 "탐욕법" 이라고 불리며 말 그대로 현재 상황에서 지금 당장 좋은 것만 고르는 방법 이다.

#11399 ATM

문제

🔗https://www.acmicpc.net/problem/11399

하하핫 쉽다!!
돈을 인출하는데 필요한 시간을 다 입력받고 오름차순으로 정렬한 후, 차례로 합을 구한다음 그걸 다시 더해주면 되겠구나 생각했다.

import sys

n=int(sys.stdin.readline().rstrip())
p=list(map(int,sys.stdin.readline().split()))
p.sort()
sum=0

for i in range(n+1):
    for m in range(i):
        sum+=p[m]

print(sum)

처음에는 이렇게 이중 for문으로 풀었다. 성공했지만 규칙성을 보니까 for문 하나로 정리할 수 있을 것 같아서 다시 수정하였다.

코드

import sys

n=int(sys.stdin.readline().rstrip())
p=list(map(int,sys.stdin.readline().split()))
p.sort()
sum=0
result=0

for i in p:
    sum+=i
    result+=sum

print(result)

시간은 딱 절반정도 단축!!

#11047 동전 0

문제

🔗https://www.acmicpc.net/problem/11047
교재에 나왔던 설명과 유사한 문제이다.
위 문제같은 경우는 화폐 단위에서
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
와 같은 조건이 있어서 그리디 알고리즘으로 풀 수 있었다.
만약 무작위로 화폐단위를 입력받는 거였다면 다른 방법을 이용해 풀어야 했을 것이다!

코드

import sys

n,k=map(int,sys.stdin.readline().split())
coins=[]
for _ in range(n):
    coins.append(int(sys.stdin.readline().rstrip()))
coins.sort(reverse=True)

cnt=0

for coin in coins:
    if coin<=k:
        cnt+=k//coin
        k%=coin
    if k==0:
        break

print(cnt)

#4796 캠핑

문제

🔗https://www.acmicpc.net/problem/4796
강산이의 휴가 기간=20일 ,캠핑장을 연속하는 8일 중, 5일동안만 사용할 수 있다고 할 때
20을 8로 나눈 몫에다가 8을 곱한 숫자에, 이후 20을 8로 나눴을때 나머지와 5중 작은 숫자를 선택해 더해준다.
(20//8)×8+min(20%8,5) => (v//p)×l+min(v%p,l)
위 계산식을 이용해 코드를 구현하였다.

코드

import sys

l,p,v=map(int,sys.stdin.readline().split())
case=0

while (True):
    if (l==0)and(p==0)and(v==0):
        break
    case+=1
    result=0
    result=(v//p)*l+min(v%p,l)

    print("Case ",case,": ",result, sep='')

    l,p,v=map(int,sys.stdin.readline().split())

#1439 뒤집기

문제

🔗https://www.acmicpc.net/problem/1439
우선 숫자의 덩어리(?)를 세고! 후에 그 덩어리를 식으로 통해 풀어나가면 되겠구나하고 이해를 했다.
-> 만약 문자열 11000011110011 이 있다면 (11)(0000)(1111)(00)(11)로 나누는 것처럼!

문자열을 한번 돌면서, i번째 숫자와 i+1번째 숫자가 다를 시에 cnt+1을 해줌으로써 숫자가 총 몇 번 바뀌는 지를 확인하고
최소 횟수는 해당 바뀐 횟수/2의 반올림이므로
round(cnt/2)로 출력하면 된다고 생각했는데 틀렸다...
문제는 바로 반올림 함수였는데,
4.5를 반올림 하는데도 계속 4가 되는 현상이 일어나서 한창을 끙끙 앓다가 검색을 했더니 바로 나왔다.

반올림 대상이 절반에 걸리는 경우 가까운 짝수로 맞춰준다. 0.5는 0, 1.5와 2.5는 2가 되는 식이다. IEEE 754가 기본값으로 추천하는 방식으로, 파이썬의 round 함수도 이 방식을 사용하고 있다. Bankers' rounding, Gaussian rounding이라 부르기도 한다.

출처 : https://velog.io/@city7310/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%98%EC%98%AC%EB%A6%BC-%EC%9D%B4%EC%83%81%ED%95%B4%EC%9A%94
(왜 이런 방식을 쓰는지에 대한 이유도 나와있어서 정말 좋은 글 같다!!)

무조건 4는 버림, 5는 올림하는 사사오입 방식은 반올림의 한 종류일 뿐이고, 그 이외 다양한 반올림 방식이 있다는 것은 이번을 통해 확실히 알 수 있었다.

여튼 이것때문에 나는 반올림 함수를 따로 만들었고 이후에 성공했다.

코드

import sys

def real_round(num):
    return int(num)+1 if (num-int(num))>=0.5 else int(num) 

string=list(map(int, sys.stdin.readline().rstrip()))

cnt=0

for i in range(len(string)-1):
    if string[i]!=string[i+1]:
        cnt+=1

print(real_round(cnt/2))

#1080 행렬

문제

🔗https://www.acmicpc.net/problem/1080
어떻게 이 문제를 그리디로 해결하지?
아하! 행렬을 돌면서 가장 많이 뒤집어야 하는 구간을 찾아서 뒤집으면 되지 않을까?! -> 실패...
이후에 다른 사람들 코드를 참고하면서 그냥 좌->우,상->하로 순차적으로 뒤집는구나... 확인 후 그렇게 구현
근데 아직도 이게 왜 그리디인지 잘 모르겠다...

코드

import sys

n,m=map(int,sys.stdin.readline().split())
a = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
b = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
cnt=0

for i in range(n - 2):
    for j in range(m - 2):
        if a[i][j]!=b[i][j]:
            for x in range(3):
                for y in range(3):
                    a[i+x][j+y] = 1-a[i+x][j+y]	 
            cnt+=1	
            
if a==b:
    print(cnt)
else:
    print(-1)