[알고리즘] 그리디 알고리즘

그리디 알고리즘

• 현재의 선택이 나중에 미칠 영향을 고려하지 않고, 각 단계에서 가장 최선의 선택을 하는 기법이다.
• 그리디 알고리즘은 100% 최적해를 보장해주지 않고, 어느 정도 적합한 수준의 해답을 알려준다.
• 시간 복잡도가 낮아 계산 속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 때문에 실용적으로 사용 가능하다

그리디 알고리즘 구조

1. 현재 상태에서의 최적의 해답을 선택한다.
2. 선택한 해가 문제의 조건을 만족하는지 검사한다.
3. 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번 과정으로 돌아가 위의 과정을 반복한다.

그리디 알고리즘  사용 조건

• 탐욕 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
• 최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해로 구성되야 합니다.

---

그리디 알고리즘 문제(Lv1, Easy)

프로그래머스 Lv1. 체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

def solution(n, lost, reserve):

    # 체육복이 있는 학생의 수 = 전체 학생수(n) - 도난당한 학생수(lost의 수)
    answer = n-len(lost)

    # 여벌의 체육복이 있지만 도난당한 학생의 경우
    for i in range(1,n+1) :
        if i in lost and i in reserve :
            reserve.remove(i)
            lost.remove(i)
            answer+=1

    # 도난당해 체육복이 없는 학생의 경우 앞 뒤 학생에게 체육복을 빌린다.
    for i in range(1,n+1) :
        if i in lost :
            if i-1 in reserve :
                answer+=1
                reserve.remove(i-1)
            elif i+1 in reserve :
                answer+=1
                reserve.remove(i+1)

    return answer

 

LeetCode Easy DI String Match 

https://leetcode.com/problems/di-string-match/description/

DI String Match - LeetCode

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        list_result = []
        max_val = len(s)
        min_val = 0

        for i in range(len(s)):
            if s[i] == 'I' :
                list_result.append(min_val)
                min_val+=1
            elif s[i] == 'D' :
                list_result.append(max_val)
                max_val-=1
        list_result.append(max_val)

        return  list_result

 

LeetCode Easy. Can Place Flowers

https://leetcode.com/problems/can-place-flowers/

Can Place Flowers - LeetCode

def canPlaceFlowers(flowerbed, n) :

    # 배열의 길이가 1일 경우 예외 처리
    if(len(flowerbed) == 1) :
        if flowerbed[0] == 1 and n == 0 :
            return True
        elif flowerbed[0] == 0 and n <= 1:
            return True
        else :
            return False

    for i in range(len(flowerbed)) :
        # 첫번째 요소일 경우 바로 뒤 인덱스만 고려하면 된다.
        if i==0 :
            if flowerbed[i]==0 and flowerbed[i+1]==0 :
                flowerbed[i]=1
                n-=1
            continue
        # 마지막 요소일 경우 바로 앞 인덱스만 고려하면 된다.
        if i==len(flowerbed)-1 :
            if flowerbed[i]==0 and flowerbed[i-1]==0 :
                flowerbed[i]=1
                n-=1
            continue
        # 앞 뒤 요소 모두 고려해야 한다
        if flowerbed[i]==0:
            if flowerbed[i-1] == 0 and flowerbed[i+1] == 0:
                flowerbed[i]=1
                n-=1
    # n을 모두 소진하지 못한다면 False
    return True if n<=0 else False

 

LeetCode Easy. lemonade change

https://leetcode.com/problems/lemonade-change/

Lemonade Change - LeetCode

def lemonadeChange(bills) :

    changeFive,changeTen = 0,0

    for money in bills :
        if money == 5 :
            changeFive+=5
        elif money == 10 :
            if changeFive == 0 :
                return False
            changeTen+=10
            changeFive-=5
        else:
            if changeTen>0 and changeFive>0:
                changeTen-=10
                changeFive-=5
            elif changeFive >= 15 :
                changeFive-=15
            else :
                return False

    return True

 

 

그리디 알고리즘 문제(Lv2, Medium)

프로그래머스 LV2. 큰수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

def solution(number, k):
    answer = [] # stack(Last in First  out)

    for num in number :
        # 스택이 비였거나 k(빼야하는 숫자)가 0인 경우 append 작업만 가능
        if not answer or k==0 :
            answer.append(num)
            continue

        # 새로운 수가 스택의 마지막 요소보다 크면 스택의 마지막 요소를 pop하고,
        # 마지막에 요소를 넣는 과정을 스택이 비거나 k가 0일 때까지 반복한다.
        while answer[-1] < num :
            answer.pop()
            k-=1
            if not answer or k<=0:
                break

        answer.append(num)

    # 배열을 문자열로 변환
    answer = ''.join(answer)
    # 민액 내림차순으로 잘 정리됐는데, 빼야할 수가 남은 경우를 처리
    answer = answer[:-k] if k > 0 else answer
    
    return answer

 

프로그래머스 Lv2. 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

def solution(people, limit):
    answer = 0
    people.sort()
    left,right=0,len(people)-1

    while len(people) > 0 and left < right :
        sum_weight = people[left]+people[right]
        if sum_weight > limit :
            right-=1
            answer+=1
        else :
            left+=1
            right-=1
            answer+=1
    if left==right:
        answer+=1
            
    return answer

 

LeetCode Medium. Valid Triangle Number 

https://leetcode.com/problems/valid-triangle-number/

Valid Triangle Number - LeetCode

# 투 포인터 사용
def triangleNumber(nums) :
    num=0
    nums.sort()
    
    for idx in range(len(nums)) :
        left,right=0,idx-1
        while left < right :
            if nums[left]+nums[right] > nums[idx] :
                num+=right-left
                right-=1
            else :
                left+=1
            
    return num