[TIL] Greedy Algorithm에 대해 알아보자

sorzzzzy·2022년 2월 10일

TIL algorithm

TIL

목록 보기

24/36

Greedy Algorithm?

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.

Greedy는 탐욕스러운이라는 뜻을 가지는데, 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게 탐욕적으로 문제를 푸는 것이다.

여기서 탐욕적이란, 현재 상황에서 당장 좋은 선택지를 고르는 것을 의미한다.
매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

문제를 해결하는 방법

그리디 알고리즘으로 문제를 해결하는 방법은 크게 3가지 단계로 이루어져 있다.

선택 절차(Selection Procedure)
➡️ 현재 상태에서의 최적의 해답을 선택
적절성 검사(Feasibility Check)
➡️ 선택된 해답이 문제의 조건을 만족하는지 검사
해답 검사(Solution Check)
➡️ 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

거스름돈 문제

그리디 알고리즘의 대표적인 문제인 거스름돈 문제를 간단히 살펴보자.

🤔 : 당신은 음식점의 계산을 도와주는 점원이고 카운터에는 거스름돈으로 사용할 500원, 100원, 10원짜리 동전이 무한히 존재한다.
손님에게 거슬러 줘야 할 돈이 N 원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하여라.
단, 거슬러 줘야 할 돈 N 원은 항상 10의 배수이다.

def solution(money):
    res = 0
    change = [500, 100, 50, 10]
    remain = money
    for i in change:
        res += remain // i
        remain = remain % i
    return res

💡 해결방법은 간단하다. 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
N 원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 주고,
그 다음은 100원 다음은 10원 순서로 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

다양한 문제 풀이

📌 모두 python 을 사용했습니다.

✔️ [BOJ] 폴리오미노/1343

from sys import stdin

board = stdin.readline().rstrip()

idx = 0

while True:
    if idx >= len(board):
        break

    if board[idx:idx+4] == 'XXXX':
        # 인덱스 위치를 4칸 뒤로 변경
        idx += 4
        board = board.replace('X', 'A', 4)
    elif board[idx:idx+2] == 'XX':
        # 인덱스 위치를 2칸 뒤로 변경
        idx += 2
        board = board.replace('X', 'B', 2)
    elif board[idx] == '.':
        # 인덱스 위치를 1칸 뒤로 변경
        idx += 1
    else:
        board = -1
        break
print(board)

✔️ [BOJ] 뒤집기/1439

from sys import stdin

S = stdin.readline()
cnt_zero = 0
cnt_one = 0
for str in range(len(S)-1):
    if S[str] == S[str+1]:
        continue
    else:
        if S[str] == '0':
            cnt_zero += 1
        elif S[str]  == '1':
            cnt_one += 1
            
print(min(cnt_zero, cnt_one))

✔️ [BOJ] 수리공항승/1449

from sys import stdin

N, L = map(int, stdin.readline().split())
pipe_list= list(map(int, stdin.readline().split()))

# 오름차순 정렬
pipe_list.sort() 

res = 1

# 테이프를 붙일 수 있는 지점
length = pipe_list[0] + L - 0.5 

for pipe in pipe_list:
    # (현재값 + 테이프 길이 + 0.5(간격 필요)) 가 그 다음 값보다 작거나 같다면
    # 한 테이프로 이어 붙일 수 있다는 소리이므로, 따로 결과값 카운트 X
    if pipe <= length:
        continue
    else:
        res += 1
        # 테이프를 붙일 지점을 새롭게 업데이트 해줌
        length = pipe + L - 0.5

print(res)

✔️ [BOJ] 회의실 배정/1931

from sys import stdin

N = int(stdin.readline())

meetings = [list(map(int, stdin.readline().split())) for _ in range(N)]
# 1번째 인덱스를 기준으로 오름차순 정렬
# 회의가 빨리 끝나야, 그 뒤에 올 수 있는 회의 개수가 많아질 것이기 때문
meetings.sort(key=lambda x:(x[1], x[0]))

res = 0
now = 0

for start, end in meetings:
    # 시작 시간과 종료 시간이 같을 수 있으므로 >=
    # 앞으로 시작될 회의 시간이 현재 시간보다 같거나 커야함
    if start >= now:
        res += 1
        # 회의가 끝난 시간을 현재 시간으로 업데이트
        now = end
print(res)

✔️ [BOJ] 주유소/13305

from sys import stdin

n = int(stdin.readline())
road = list(map(int, stdin.readline().split()))
price = list(map(int, stdin.readline().split()))
res = 0
tmp = price[0]
for i in range(len(road)):
    if price[i] < tmp:
        tmp = price[i]    
    res += tmp*road[i]
print(res)

✔️ [BOJ] 방탈출/15729

from sys import stdin

N = int(stdin.readline())
target = list(map(int, stdin.readline().split()))

buttons = [0 for _ in range(N)]
res = 0
for idx in range(N):
    # 현재 위치와 타겟 위치의 값이 같다면 continue
    if buttons[idx] == target[idx]:
        continue
    
    # 값이 다른 경우
    #   -> 불이 꺼진 경우라면 켜고
    if buttons[idx] == 0:
        buttons[idx] = 1 
    #   -> 불이 켜진 경우라면 끄기
    else:
        buttons[idx] = 0
    #   -> 오른쪽 버튼 확인  
    if idx + 1 < N:
        if buttons[idx + 1] == 0:
            buttons[idx + 1] = 1
        else:
            buttons[idx + 1] = 0     
    if idx + 2 < N:
        if buttons[idx + 2] == 0:
            buttons[idx + 2] = 1 
        else:
            buttons[idx + 2] = 0       
    
    # 결과값 1 카운트
    res += 1

print(res)