[ 그리디 ] 알고리즘

 

 

1. 개념

 

그리디 알고리즘 : 현재 상태에서 최선의 선택을 하는 알고리즘

 

그리디 알고리즘은 시간복잡도가 좋지만 항상 최고의 답을 도출해내지는 못한다.

따라서 그리디 알고리즘은 문제를 보고 그리디 알고리즘으로 최적해를 구할 수 있는지 파악하는 것이 중요하다.

 

그리디 알고리즘으로 최적해를 구할 수 있는 문제들은 최적 부분 구조를 갖는다.

최적 부분 구조는

1 )  현재의 선택이 다음 선택에 무관한 값이어야 한다. 

2)  현재의 최적해가 전체에 대한 최적해여야 한다. 

 

 

 

 

2. 문제 풀이

 

# 1  동전 0 - 백준 11047번

https://www.acmicpc.net/problem/11047

11047번: 동전 0

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
coin = []
cnt = 0

for i in range(n):
    coin.append(int(input()))

coin.sort()
coin.reverse()

for i in range(n):
    if k // coin[i] > 0:
        coinNum = (k//coin[i])
        cnt += coinNum
        k -= (coinNum * coin[i])
    
    if k == 0:
        break 

print(cnt)

 

 

 

 

 

# 2  카드 정렬하기 - 백준 1715번

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

import sys
import heapq

input = sys.stdin.readline

n = int(input())
card = []
cnt = 0

for i in range(n):
    heapq.heappush(card, int(input()))

while len(card) > 1:
    card1 = heapq.heappop(card)
    card2 = heapq.heappop(card)
    temp = card1 + card2
    cnt += temp

    heapq.heappush(card, temp)

print(cnt)

 

 

 

 

 

# 3  수 묶기  - 백준 1744번

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

import sys

input = sys.stdin.readline

n = int(input())
num = []
newNum = []
cnt = 0


def Tie(a, b):
    if a > 0:
        if a == 1:
            return False
        elif b == 1:
            return False
        return True
    elif a == 0:
        return False
    else:
        if b < 0:
            return True
        elif b == 0:
            return True
        else:
            return False


if n == 1:
    num.append(int(input()))
    print(num[0])

else:
    for i in range(n):
        num.append(int(input()))

    num.sort()

    for i in range(n):
        if num[i] > 0:
            newNum.extend(num[:i])
        else:
            continue
        num.reverse()
        newNum.extend(num[:len(num)-i])
        break

    if len(newNum) == 0:
        newNum.extend(num)

    if n == 2:
        n1 = newNum.pop(0)
        n2 = newNum.pop(0)
        tie = Tie(n1, n2)
        if tie:
            print(n1 * n2)
        else:
            print(n1 + n2)

    else:
        n1 = newNum[0]
        n2 = newNum[1]

        while len(newNum) > 0:

            if Tie(n1, n2):
                temp = n1 * n2
                cnt += temp
                newNum.pop(0)
                newNum.pop(0)

                if len(newNum) <= 1:
                    break

                else:
                    n1 = newNum[0]
                    n2 = newNum[1]

            else:
                cnt += n1
                newNum.pop(0)

                if len(newNum) <= 1:
                    break
                else:
                    n1 = n2
                    n2 = newNum[1]

        if len(newNum) == 1:
            cnt += newNum[0]
            print(cnt)

        else:
            print(cnt)

우왕 코드 조금 더럽긴 한데 처음으로 골드 문제 혼자서 풀었다!! 햅삐~~

 

 

 

 

# 4  회의실 배정하기 - 백준 1931번

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

import sys
input = sys.stdin.readline

cnt = 0
end = -1

n = int(input())
A = [[0]*2 for _ in range(n)]

for i in range(n):
    s, e = map(int, input().split())
    A[i][0] = e
    A[i][1] = s

A.sort()

for i in range(n):
    if A[i][1] >= end:
        end = A[i][0]
        cnt += 1
print(cnt)

 

머리 과부화 걸려서 요건 책 보고 따라 썼다...

다음에 다시 풀어보기..!!

 

 

 

 

# 5  잃어버린 괄호 - 백준 1541번

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

import sys

input = sys.stdin.readline

formula = list(map(str, input().split('-')))
cnt = 0

for i in range(len(formula)):
    inner = list(map(int, formula[i].split('+')))
    if i == 0:
        cnt += (sum(inner))
    else:
        cnt -= (sum(inner))

 

 

 

 

 

 

 

 

---

 

 

히히 실버 1 달았다아아

골드 가자자자자잣