[그리디] 💡 BOJ - 2839번, 1931번, 1202번, 1715번, 11000번, 1744번, 1339번, 1700번, 2812번, 3109번, 2437번, 10775번

그리디 알고리즘

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

그리디로 얻은 해가 최적의 해를 보장할 수 있는가?에 대한 정당성을 늘 고민할 것

 

🚀 그리디하게 해결하려고 할 때 다루기 쉬운 자료구조: 배열, 힙, 스택 등

🚀 주요 아이디어: 정렬, 조건에 맞춰 pop

🚀 알고 있는 걸 잘 꺼내자.

 

 

 

문제풀이

✅ 2839번 설탕배달 (S4)

1931번: 회의실 배정

def getInput():
    return int(input())


def solution():
    n = getInput()
    total = n
    bucket = 0

    # case 1
    if n % 5 == 0:
        return n // 5

    while total > 0:
        if total == 1 or total == 2:
            return -1
        if total % 5 == 0:
            return bucket + (total // 5)
        total -= 3
        bucket += 1

    return bucket


print(solution())

 

 

✅ 1931번 회의실 배정 (S1)

1931번: 회의실 배정

# 시간 복잡도
def getInput():
    N = int(input())
    meeting = []
    for i in range(N):
        meeting.append(list(map(int, input().split())))
    return meeting


def solution():
    schedules = getInput()
    # 정렬 우선 순위 (endTime > startTime)
    target_arr = sorted(schedules, key=lambda x: (x[1], x[0]))
    curr = 0
    result = 0
    for start, end in target_arr:
        if curr <= start:
            result += 1
            curr = end
    return result


print(solution())

 

 

 

✅ 1202번 보석 도둑 (G2)

• key:
  • 가방에는 최대 한 개의 보석만 넣을 수 있다.
  • 훔칠 수 있는 보석의 최대 가격

1202번: 보석 도둑

import heapq


def getInput():
    N, K = map(int, input().split())
    jewerly = []
    for _ in range(N):
        jewerly.append(list(map(int, input().split())))
    bags = []
    for _ in range(K):
        bags.append(int(input()))

    jewerly.sort(reverse=True)
    bags.sort()
    return jewerly, bags


def solution():
    jewerly, bags = getInput()

    result = 0
    heap = []  # 가격이 큰 보석이 우선순위가 되니까 price에 대한 maxHeap

    # 작은 가방 기준으로 보석 보기
    for bag in bags:
        while jewerly:
            w, p = jewerly[-1][0], jewerly[-1][1]
            if w > bag:
                break
            heapq.heappush(heap, -p)  # maxHeap
            jewerly.pop()
        # 담을 수 있는 쥬얼리 후보, 어차피 여기 들어가면 다음 가방에도 들어가기 때문에 남아 있어도 문제 X
        if heap:  # 그 중 가장 가치 있는 쥬얼리 담고 넘어감
            result += (-1) * heapq.heappop(heap)

    return result


print(solution())

 

 

 

 

✅ 1715번 카드 정렬하기 (G4)

1715번: 카드 정렬하기

import heapq


def getInput():
    N = int(input())
    arr = [int(input()) for _ in range(N)]
    return arr

    
def solution():
    cards = getInput()
    
    if len(cards) == 1:
        return 0

    heapq.heapify(cards)  # 최소 힙으로 카드 크기를 관리, 가장 작은 크기의 카드 두 장 선택 하기 위함

    result = 0
    while len(cards) > 1:
        a = heapq.heappop(cards)
        b = heapq.heappop(cards)
        cost = a + b
        result += cost
        heapq.heappush(cards, cost)  # 합친 결과를 다시 카드 묶음에 추가

    return result


print(solution())

 

 

 

 

✅ 11000번 강의실 배정 (G5)

startTime 기준으로 정렬하고, endTime 간의 비교를 통해 병렬로 필요한 강의실 개수를 구할 수 있다.

11000번: 강의실 배정

import heapq


def getInput():
    N = int(input())
    lecture = []
    for i in range(N):
        lecture.append(list(map(int, input().split())))
    sorted_lecture = sorted(lecture, key=lambda x: x[0])
    return sorted_lecture, N


def solution():
    lecture, n = getInput()

    heap = []
    initial_end_time = lecture[0][1]
    heapq.heappush(heap, initial_end_time)

    for i in range(1, n):
        curr_start = lecture[i][0]
        curr_end = lecture[i][1]
        standard = heap[0]
        if curr_start < standard:
            heapq.heappush(heap, curr_end)
            continue
        heapq.heappop(heap)
        heapq.heappush(heap, curr_end)

    return len(heap)


print(solution())

 

 

 

✅ 1744번 수 묶기 (G4)

적절한 케이스 분류에 대한 아이디어 (예: 음수, 양수)

1744번: 수 묶기

def getInput():
    N = int(input())
    negative_nums = []  # 음수를 저장할 배열
    positive_nums = []  # 양수를 저장할 배열

    for _ in range(N):
        num = int(input())
        if num <= 0:
            negative_nums.append(num)
        else:
            positive_nums.append(num)

    # 음수 배열은 절댓값이 큰 순서대로 정렬
    negative_nums.sort()
    # 양수 배열은 큰 수부터 정렬
    positive_nums.sort(reverse=True)
    return positive_nums, negative_nums


def solution():
    pos, neg = getInput()
    
    result = 0

    # 음수 배열 처리
    for i in range(0, len(neg), 2):
        if i == len(neg) - 1:
            result += neg[i]
            continue
        result += neg[i] * neg[i+1]

    # 양수 배열 처리
    for i in range(0, len(pos), 2):
        if i == len(pos) - 1:
            result += pos[i]
            continue
        result += max(pos[i] * pos[i+1], pos[i] + pos[i+1])
    return result


print(solution())

 

 

 

✅ 1339번 단어 수학 (G4)

1339번: 단어 수학

 

가중치 계산 예시

단어: APPLE, EAT

A: 10000 (from APPLE) + 10 (from EAT) = 10010
P: 1100 (from APPLE) = 1100
L: 10 (from APPLE) = 10
E: 1 (from APPLE) + 100 = 101
T: 1 (from EAT) = 1

순서대로 A에 9, P에 8, E에 7, L에 6, T에 5 부여하여
90090 + 8800 + 707 + 60 + 5
= 99662

def getInput():
    n = int(input())
    words = [input() for _ in range(n)]
    return words


def solution():
    words = getInput()
    
    result = 0

    # 모든 알파벳의 가중치를 계산, 저장할 배열
    alphabet = [0] * 26

    # 각 단어의 가중치 값을 계산
    for word in words:
        for i, char in enumerate(word):
            alphabet[ord(char) - ord('A')] += 10 ** (len(word) - i - 1)

    # 알파벳의 가중치 오름차순으로 정렬
    alphabet.sort()

    # 가중치가 큰 알파벳부터, 9부터 1까지 할당 (0이면 더해도 0이니 무시)
    for i in range(9, 0, -1):
        result += alphabet.pop() * i

    return result


print(solution())

 

 

 

❌✅ 1700번 멀티탭 스케줄링 (G1)

가장 나중에 사용될 기기의 인덱스를 교체

1700번: 멀티탭 스케줄링

def getInput():
    N, K = map(int, input().split())  # 기기 개수와 멀티탭 구멍 개수 입력
    plugs = list(map(int, input().split()))  # 각 기기의 사용 순서 입력
    return N, K, plugs


def solution():
    n, k, plugs = getInput()  # 입력 받기
    result = 0  # 멀티탭 뽑는 횟수 초기화
    multi_tap = []  # 현재 멀티탭에 꽂힌 기기들을 저장할 리스트

    for i in range(k):  # 각 사용 순서마다 확인
        if plugs[i] in multi_tap:  # 이미 해당 기기가 멀티탭에 꽂혀 있는 경우 스킵
            continue
        if len(multi_tap) < n:  # 멀티탭에 빈 자리가 있는 경우
            multi_tap.append(plugs[i])  # 기기를 멀티탭에 꽂음
            continue
        # 그리디하게 제거하기
        remove_idx = -1
        latest_idx = -1  # 현재 멀티탭에 꽂혀있는 기기 중에서 가장 나중에 사용될 기기의 인덱스
        for curr_idx in range(n):  # 멀티탭에 꽂혀 있는 기기들 중에서 어떤 기기를 뽑을지 결정
            remains = plugs[i + 1:]  # 현재 기기 이후에 사용할 기기들
            curr_device = multi_tap[curr_idx]
            if curr_device not in remains:  # 나중에 사용하지 않을 경우
                remove_idx = curr_idx
                break
            if remains.index(curr_device) > latest_idx:  # 더 나중에 사용되는 경우
                latest_idx = remains.index(curr_device)
                remove_idx = curr_idx
        multi_tap[remove_idx] = plugs[i]  # 선택된 기기로 멀티탭 교체
        result += 1

    return result


print(solution())

 

 

 

✅ 2812번 크게 만들기 (G3)

n 길이 배열에서 앞에서부터 작은 k개의 원소를 제거하는 방법 (O(n) 풀 수 있음)

2812번: 크게 만들기

def getInput():
    n, k = map(int, input().split())
    num = list(input())
    return k, num


# O(n^2) 불가
# 앞에서부터 작은 수 k개 지우기

def solution():
    remain, num = getInput()
    stack = []
    for i in range(len(num)):
        # 스택에서 원소를 뺄 수 있고, 스택 top에 있는 게 현재 숫자보다 작으면
        while stack and remain > 0 and stack[-1] < num[i]:
            stack.pop()
            remain -= 1
        stack.append(num[i])
    return ''.join(stack[:len(stack) - remain])


print(solution())

 

 

 

 

✅ 3109번 빵집 (G2)

3109번: 빵집

def getInput():
    R, C = map(int, input().split())
    board = [input() for _ in range(R)]
    return R, C, board


def is_valid(x, y, R, C):
    return 0 <= x and x < R and 0 <= y and y < C


def solution():
    R, C, board = getInput()
    result = 0
    BLANK = '.'
    BUILDING = 'x'

    def dfs(x, y):  # 파이프를 연결해 가스관까지 도달하는 경로 찾기
        if y == C - 1:
            return True
        dx = [-1, 0, 1]
        for d in dx:
            nx, ny = x + d, y + 1
            if is_valid(nx, ny, R, C) and board[nx][ny] == BLANK:
                board[nx] = board[nx][:ny] + BUILDING + board[nx][ny + 1:]
                if dfs(nx, ny):  # 경로 찾음
                    return True
        return False

    for i in range(R):  # 각 행에 대한 dfs 수행
        if dfs(i, 0):
            result += 1
    return result


print(solution())

 

 

 

✅ 2437번 저울 (G2)

2437번: 저울

# 추들을 사용해 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램
def getInput():
    n = int(input())
    weights = list(map(int, input().split()))
    return weights


def solution():
    weights = getInput()
    weights.sort()  # 무게추를 정렬

    total_weight = 0  # 측정 가능한 무게 범위의 최대값
    for weight in weights:
        # 현재 무게를 측정할 수 없는 경우
        if total_weight + 1 < weight:
            break
        total_weight += weight

    return total_weight + 1  # 가능한 한계 + 1 해야 측정할 수 없는 값임


print(solution())

 

 

 

 

❌✅ 10775번 공항 (G2)

10775번: 공항

# 입력을 받는 함수
def getInput():
    G = int(input())
    P = int(input())
    planes = [int(input()) for _ in range(P)]
    return G, P, planes


def find(gate, x):
    if gate[x] != x:
        gate[x] = find(gate, gate[x])
    return gate[x]


def union(gate, a, b):
    a = find(gate, a)
    b = find(gate, b)
    if a < b:
        gate[b] = a
    else:
        gate[a] = b


def solution():
    G, P, planes = getInput()
    gates = [i for i in range(G + 1)]  # 각 게이트의 부모를 자기 자신으로 초기화
    result = 0  # 도킹된 비행기 개수 초기화

    for plane in planes:  # 각 비행기에 대해서 처리
        docked_gate = find(gates, plane)  # 비행기가 도킹할 게이트의 루트 찾기
        if docked_gate == 0:  # 더 이상 도킹할 수 없는 경우 종료
            break
        union(gates, docked_gate, docked_gate - 1)  # 현재 게이트와 직전 게이트를 합치기
        result += 1  # 비행기가 도킹되었으므로 결과 개수 증가

    return result


print(solution())