탐욕법(Greedy)

부분적인 최적해가 전체적인 최적해가 되는 마법!

출제 빈도	평균점수	문제 세트
낮음	낮음	6 / 6

체육복

# sol 1
def solution(n, lost, reserve):
    intersect = set(lost) & set(reserve) # 여분 가지면서 도난당한 학생
    
    # 남은 체육복이 하나기에 제외
    _lost = set(lost) - intersect
    _reserve = set(reserve) - intersect 
    
    for r in _reserve:
        if r - 1 in _lost: # 학생의 왼쪽 번호부터 확인
            _lost.remove(r - 1)
        elif r + 1 in _lost: # 오른쪽 번호 확인
            _lost.remove(r + 1)
    
    # 전체 학생 - 도난당한 학생
    answer = n - len(_lost)
    
    return answer

# sol 2
def solution(n, lost, reserve):
    # 여유분이 있으면서 도난당한 학생 제외
    _lost = [l for l in lost if l not in reserve]
    _reserve = [r for r in reserve if r not in lost]
    
    # 작은 번호를 가진 학생을 먼저 확인해야 한다.
    _reserve.sort()
    
    for r in _reserve:
        prev, next = r - 1, r + 1
        # 이전 번호의 학생부터 확인한다.
        if prev in _lost:
            _lost.remove(prev)
        elif next in _lost:
            _lost.remove(next)
    return n - len(_lost)

아이디어 & 설명

✅ 핵심

• 여벌을 가지고 있는 학생의 앞쪽(왼쪽) 번호의 학생에게 먼저 빌려준다.
• 여벌을 가지고 있는 학생이 도난당한 경우를 처리해야 한다.

먼저, 여벌을 가지고 있는 학생이 도난당한 경우를 처리한다.

• set으로 중복 제외
• 새로운 리스트 생성

그리고 여벌을 가지고 있는 학생을 탐색하면서, 현재 학생보다 lost에 있는 앞쪽(왼쪽) 번호의 학생에게 먼저 빌려준다.
만약, 앞쪽(왼쪽) 번호가 없다면, 뒤쪽(오른쪽) 번호의 학생에게 빌려준다.
그리고 해당 학생을 remove한다.

만약 새로운 리스트(_reserve)를 생성해서 여벌을 가지고 있는 학생이 도난당한 경우를 처리했다면 reserve를 먼저 정렬해야 한다.
예를 들어, lost = [3, 5], reserve = [4, 2] 이라면 4가 3에게 빌려주는 단 하나의 경우만 가능하다. 하지만 reserve를 정렬했다면, 2는 3에게, 4는 5에게 빌려주므로 2명에게 빌려줄 수 있다.

---

조이스틱

다른 코드 참고

def solution(name):
    n = len(name)
    count = 0
    _min = n - 1
    
    for i, c in enumerate(name):
        count += min(ord(c) - ord('A'), ord('Z') - ord(c) + 1)
        
        nxt = i + 1
        while nxt < n and name[nxt] == 'A':
            nxt += 1
        
        _min = min(_min, 2 * i + n - nxt, i + 2 * (n - nxt))
    
    count += _min
    return count        

아이디어 & 설명

✅ 다시 풀어볼 문제 (코드 이해 부족)

---

큰 수 만들기

def solution(number, k):
    stk = []
    for n in number:
        # 더 이상 제거 못하는 경우
        if k == 0:
            stk.append(n) # 그냥 이어붙인다.
            continue
        if stk:
            while stk and stk[-1] < n and k > 0: # 현재 원소보다 top의 원소의 크기가 더 작은 경우
                stk.pop() # top의 원소를 제거한다.
                k -= 1 # 제거 횟수 갱신
        stk.append(n) # 이어붙인다.
        
    # k가 0이 아닌 경우 == 제거를 모두 하지 않은 경우
    # 뒤에서 k만큼 뺀 나머지를 문자열로 반환한다.
    return "".join(stk[:len(number)-k])

아이디어 & 설명

✅ 핵심

• 스택의 top을 확인하면서 현재 원소보다 작다면 pop을 수행한다.
• 모든 수를 탐색했는데 k가 0이 아니라면, 뒤에서 k만큼 제외한 나머지 문자열을 반환한다.

---

구명보트

def solution(people, limit):
    answer = 0
    
    people.sort() 
    
    # 투 포인터
    l, r = 0, len(people) - 1
    while l <= r:
        # 무게 제한보다 적게 나가면
        if people[l] + people[r] <= limit:
            answer += 1 # 보트 수 갱신
            # 포인터 갱신 → 다음 사람 확인
            l += 1
            r -= 1
        else: # 더 많이 나가면
            r -= 1 # 다음 사람 확인
            answer += 1 # people[r]은 어떤 사람과도 같이 탈 수 없으므로, 보트가 무조건 1개 필요
            
    return answer

아이디어 & 설명

✅ 핵심

• 가장 무게가 작은 2명을 묶어서 보트를 태우면 안된다.
• 최소 무게와 최대 무게인 2명을 묶어서 보트에 태워야 한다.
• 만약 묶어서 보트를 태울 수 없다면, 최대 무게인 사람은 어느 누구와도 묶일 수 없으므로 보트 1개를 독차지한다.

---

섬 연결하기

def solution(n, costs):
    def find_parent(parent, x):
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]
    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
            
    parent = [0] * n
    for i in range(n):
        parent[i] = i
        
    answer = 0
    
    costs.sort(key=lambda x: x[2])
    
    for cost in costs:
        a, b, c = cost
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += c
    
    return answer

아이디어 & 설명

✅ 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구하기

이 키워드에서 크루스칼 알고리즘을 떠올렸다.

일반적인 크루스칼 알고리즘에서는 입력으로 주어진 노드-간선 정보를 edges 리스트에 넣어서, edges 리스트를 비용을 기준으로 오름차순 정렬을 수행한다.

여기서 costs에 모든 정보가 들어있으므로, 굳이 edges를 만들지 않아도 된다.

---

단속카메라

진입 시점 기준

def solution(routes):
    answer = 0
    # 이전 진출, 진입
    prev_out = -30000
    
    # 진입 기준, 오름차순 정렬
    routes.sort(key=lambda x:x[0])
    
    for route in routes:
        # 현재 진입, 진출
        cur_in, cur_out = route
        
        # 이전 진출보다 현재 진입이 더 크다면 -> 겹치는 범위가 없다.
        if prev_out < cur_in:
            answer += 1 # 단속용 카메라 + 1
            prev_out = cur_out # 이전 진출 갱신
        else:
            prev_out = min(prev_out, cur_out)
        
    return answer

진출 시점 기준

def solution(routes):
    answer = 0
    routes.sort(key=lambda x:x[1])
    prev_out = -30000 # 이전 진출 시점
    
    for route in routes:
        # 현재 진입, 진출 시점
        cur_in, cur_out = route
        # 이전 진출보다 현재 진입이 더 크다면 -> 겹치는 범위가 없다.
        if prev_out < cur_in:
            answer += 1 # 단속카메라 개수 + 1
            prev_out = cur_out # 이전 진출 갱신
    return answer

아이디어 & 설명

문제는 백준의 회의실 배정 문제와 유사하다.
핵심은 아래와 같다.

✅ 각 자동차의 [진입, 진출]시점에서 겹치는 범위를 찾는다.

문제는 무엇을 기준으로 하느냐에 따라 달라지지만, 그림을 그려보면 핵심은 동일하다.