[Algorithm] Greedy (그리디)

그리디 알고리즘(Greedy algorithm)

탐욕 알고리즘(Greedy algorithm)은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

• 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

• 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

그리디 알고리즘 관련 문제 (프로그래머스 - Leetcode)

Easy (Lv1)

프로그래머스 LV1. 체육복 과 Leetcode의 455. Assign Cookies

프로그래머스 Lv1. 체육복 : https://school.programmers.co.kr/learn/courses/30/lessons/42862

• 전체 학생수 n과, 체육복을 도난당한 학생의 인덱스가 담긴 lost 배열, 여분의 체육복이 있는 학생의 인덱스가 담긴 reserve가 주어진다.
  여벌 체육복을 가져온 학생이 다른 학생에게 체육복을 빌려 줄 수 있는데, 여벌 체육복은 바로 앞 번호나 바로 뒷번호 학생에게만 빌려줄 수 있음.
  여기서 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있고, 이 학생은 체육복을 하나만 도난 당했다고 가정하고 남은 체육복이 하나이므로 다른 학새엥게 체육복을 빌려줄 수 없음

def solution(n, lost, reserve):
    set_lost = set(lost) - set(reserve)
    set_reserve = set(reserve) - set(lost)
    
    for i in set_reserve:
        if i-1 in set_lost:
            set_lost.remove(i-1)
        elif i+1 in set_lost:
            set_lost.remove(i+1)
            
    return n - len(set_lost)

• 해당 문제는 도난당한 체육복과 여분의 체육복을 집합에 넣어서, 도난 당한 체육복의 학생이 여분의 체육복이 있는지 확인하고, 여분의 체육복이 있는 학생이 도난 당했는지 확인해서 해당 집합을 업데이트 한다.
  업데이트한 여분의 체육복 집합을 돌면서, 왼쪽, 오른쪽의 양 사이드로 도난 당한 학생이 있는지 확인하고 있으면 도난당한 학생 집합에서 체육복을 빌려줬다고 생각하고 제거하여 업데이트 한다.
  여분의 체육복 집합을 다 돌고 나서, 전체 학생에서 도난당한 학생 집합을 빼면 되는 문제이다.

Leetcode 455. Assign Cookies : https://leetcode.com/problems/assign-cookies/

• 해당 문제에서는 만족도 배열(g)과 쿠키 배열(s)을 제공하고 아이들에게 쿠키를 할당하는데, 각 아이는 만족도가 다르게 주어진 쿠키를 받게된다. 최대한 많은 아이들에게 만족도를 높이는 쿠키를 할당하는 것이다.
  각 아이는 자신의 만족도 이상의 크기를 가진 쿠키를 받으면 만족한다.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        
        i,j = 0,0
        ans = 0
        
        while i<len(g) and j<len(s):
            if g[i] <= s[i]:
                ans +=1
                i+=1
            j+=1
            
        return ans

Medium (Lv2) - 1

프로그래머스 큰 수 만들기 와 Leetcode 402. Remove K Digits

프로그래머스 Lv2. 큰 수 만들기: https://school.programmers.co.kr/learn/courses/30/lessons/42883

• 해당 문제는 숫자 문자열에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 반환하는 것이다.

def solution(number, k):
    stack = []
    
    for n in number:
        while k>0 and stack and stack[-1] < n:
            stack.pop()
            k-=1
            
        stack.append(n)
        
    while k>0:
        stack.pop()
        k-=1
    
    answer = ''.join(stack)
    
    if not answer:
        return '0'
    
    return answer

• 해당 문제에서는 숫자 문자열에서 한 자리씩 숫자를 제거하면서 가장 작은 숫자를 만들어내는 탐욕적인 방식으로 스택을 만드는데, 숫자 문자열 num을 순회하면서 각 숫자를 스택에 넣는다. 해당 스택에 숫자를 넣을 때는 스택에 숫자를 넣을 때마다 현재 스택의 맨 위 숫자가 넣으려는 숫자보다 작으면서 아직 제거할 숫자 k가 남아있다면, 스택에서 맨 위 숫자를 제거한다. 이 과정을 반복하여 제거할 숫자 k를 모두 제거 할 수 있다.
  숫자를 스택에 모두 넣은 후에도 제거할 숫자 k가 남아있다면, 스택에서 숫자를 제거하고, 스택에 남아있는 숫자들을 이어붙여 문자열로 만든 후 왼쪽의 0을 제거한다.
  만약 결과 문자열이 비어있다면 '0'을 반환하는 문제이다.

Leetcode 402. Remove K Digits :
https://leetcode.com/problems/remove-k-digits/

• 해당 문제는 음이 아닌 정수 num을 나타내는 문자열 num과 정수 k가 주어지면 num에서 k 자리를 제거한 후 가능한 가장 작은 정수를 반환하는 문제이다.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        
        for n in num:
            while k>0 and stack and stack[-1] > n:
                stack.pop()
                k-=1
            stack.append(n)
        
        while k>0:
            stack.pop()
            k-=1
        result = ''.join(stack).lstrip('0')
        
        if not result:
            return '0'
        
        return result
        

• 해당 문제에서는 숫자 문자열에서 한 자리씩 숫자를 제거하면서 가장 작은 숫자를 만들어내는 탐욕적인 방식으로 스택을 만드는데, 숫자 문자열 num을 순회하면서 각 숫자를 스택에 넣는다. 해당 스택에 숫자를 넣을 때는 스택에 숫자를 넣을 때마다 현재 스택의 맨 위 숫자가 넣으려는 숫자보다 크면서 아직 제거할 숫자 k가 남아있다면, 스택에서 맨 위 숫자를 제거한다. 이 과정을 반복하여 제거할 숫자 k를 모두 제거 할 수 있다.
  숫자를 스택에 모두 넣은 후에도 제거할 숫자 k가 남아있다면, 스택에서 숫자를 제거하고, 스택에 남아있는 숫자들을 이어붙여 문자열로 만든 후 왼쪽의 0을 제거한다.
  만약 결과 문자열이 비어있다면 '0'을 반환하는 문제이다.

Medium (Lv2) - 2

프로그래머스 구명보트 와 Leetcode 881. Boats to Save People

프로그래머스 Lv2. 구명보트:
https://school.programmers.co.kr/learn/courses/30/lessons/42885

• 사람의 무게를 담은 배열 people과 제한 무게 limit이 주어질 때, 보트에 한 번에 최대 2명씩 태운다고 할때 구명보트를 최대한 적게 사용해 모든 사람들을 이동시키는 문제이다.

def solution(people, limit):
    l, r = 0, len(people)-1
    answer = 0
    people.sort()
    while l<=r:
        if people[l] + people[r] <= limit:
            l+=1
        r-=1
        answer +=1
    return answer

보트의 최대 수용 인원을 고려하여 사람들을 정렬하는데, 보트에 최대한 많은 사람을 태우기 위해서는 무거운 사람과 가벼운 사람을 함께 태워야 한다. 따라서 몸무게를 기준으로 오름차순으로 정렬한다.
그리고 나서 그리디 알고리즘을 사용하여 각 단계에서 가장 최적의 선택을 진행한다. 이 경우에는 가장 무거운 사람과 가장 가벼운 사람을 함께 보트에 태우되, 보트의 최대 수용 인원을 초과하지 않도록 이진 탐색을 사용해서 가장 가벼운 사람, 가장 무거운 사람의 포인트를 옮겨가면서, 무게가 초과되면 보트를 하나 띄워보내고, 그다음 무거운사람과 가벼운사람을 매칭해가면서 푼다.

Leetcode 881. Boats to Save People :
https://leetcode.com/problems/boats-to-save-people/

• 해당 문제도 프로그래머스와 동일한 문제이다. 사람의 무게를 의미하는 people 배열과 제한 무게 limit이 주어질 때, 모든 사람을 최소한으로 옮길 수 있는 보트의 수를 구해야 한다.

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        l,r = 0, len(people)-1
        ans = 0
        
        while l<=r:
            if people[l] + people[r] <=limit:
                l+=1
            r-=1
            ans +=1
            
        return ans

두 문제 그리디이면서 이진탐색을 사용해서 해결한다.

Medium (Lv2) - 3

프로그래머스 조이스틱과 Leetcode 1541. Minimum Insertions to Balance a Parentheses String

프로그래머스 조이스틱:
https://school.programmers.co.kr/learn/courses/30/lessons/42860

코드를 입력하세요

Leetcode 1541. Minimum Insertions to Balance a Parentheses String :
https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/

• 해당 문제는 문자 '(' 및 ')'만 포함하는 괄호 문자열 s가 제공됩니다. 다음과 같은 경우 괄호 문자열이 균형을 이룹니다.

왼쪽 괄호 '('에는 해당하는 두 개의 연속 오른쪽 괄호 '))'가 있어야 합니다.
왼쪽 괄호 '('는 해당하는 두 개의 연속된 오른쪽 괄호 '))' 앞에 와야 합니다.
즉, '('를 여는 괄호로, '))'를 닫는 괄호로 처리합니다.

예를 들어, "())", "())(())))" 및 "(())())))"는 균형을 이루고 ")()", "()))" 및 "( ()))"의 균형이 맞지 않습니다.
필요한 경우 균형을 맞추기 위해 문자열의 어느 위치에나 '(' 및 ')' 문자를 삽입할 수 있습니다.

s를 균형 있게 만드는 데 필요한 최소 삽입 수를 반환합니다.

class Solution:
    def minInsertions(self, s: str) -> int:
        ans, closed = 0,0
        
        for c in s:
            if c == '(':
                if closed%2==1:
                    closed -=1
                    ans+=1
                closed+=2
            else:
                closed-=1
                if closed <0:
                    ans+=1
                    closed+=2
        return ans+ closed

필요한 왼쪽 괄호 opened, 오른쪽 괄호 closed라고 할 때, 주어진 문자열을 탐색하면서

• 문자열이 '(' 일 때
  만약 close가 홀수이면, 쌍을 이루는 )가 하나 더 필요한 상태이다. 그러므로 close를 하나 줄이고, 삽입 횟수 ans를 하나 증가시킨다.
  그리고 close에 2를 더해주는데, 이는 쌍을 이루는 )가 두 개 추가로 필요하다는 것을 의미한다.

• 문자열이 '(' 일 때, close를 하나 줄인다. 이는 쌍을 이루는 (가 하나 출현했다는 것을 의미한다.
  만약 close가 음수이면, 쌍을 이루는 (가 부족한 상태이다. 이 경우, close를 다시 2만큼 더해주고, 삽입 횟수 ans를 하나 증가시킵니다.
  마지막으로, close와 ans를 합하여 최종 결과를 반환한다.

Hard (Lv3) - 1

프로그래머스 섬 연결하기와

프로그래머스 섬 연결하기:

코드를 입력하세요

Leetcode

코드를 입력하세요

Hard (Lv3) - 2

프로그래머스 단속카메라와

프로그래머스 단속카메라:

코드를 입력하세요

Leetcode

코드를 입력하세요