99클럽 코테 스터디 19일차 TIL + 탐욕법(Greedy)

오늘의 문제 - 탐욕법(Greedy)

프로그래머스 - 구명보트

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

---

탐욕법(Greedy)

최적의 해를 구하는 데에 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 최적이라고 생각되는 것을 선택해 나가는 방식

탐욕 알고리즘 적용 가능한 문제들은 지역적 최적이 전역적 최적인 문제들이다.

 

그리디 알고리즘 예시 - 주어진 동전을 사용하여 가장 적은 개수로 거스름돈 거슬러주기

500원 100원 50원 10원이 있을 경우, 가장 큰 금액의 동전을 먼저 선택하여 거스름돈에서 빼주는 방식으로 해결

---

내 풀이 및 접근 방식

먼저 구명보트를 타는 2명의 몸무게 합이 limit과 근접한 경우가 많을수록 가장 최소의 구명보트를 사용할 수 있을 것이라고 생각했다.

limit이 100이고 사람들의 몸무게가 [10, 10, 20, 30, 40, 90] 으로 주어질 경우, (10,10)을 태우는 것보다 (10, 90)으로 최대한 몸무게의 합이 limit과 가까운 값을 찾아서 태우는 것이다.

앞에서부터 작은 것끼리 짝지어서 태우는 경우에는 (10, 10), (20, 30), (40), (90) 으로 총 4개의 보트가 필요하지만,

각 단계에서 최소와 최대를 더해서 limit 이하인 경우에 태우는 경우에는 (10, 90), (10, 40), (20, 30) 으로 총 3개의 보트가 필요하다.

 

풀이는 아래와 같다.

from collections import deque
def solution(people, limit):
    answer = 0

    people.sort()
    queue = deque(people)
    while queue:
        p = queue.popleft()
        
        for i in range(len(queue)-1, -1, -1):
            if p + queue[i] <= limit:
                queue.remove(queue[i])
                break
            
        answer += 1    
        
    return answer

 

풀이

1. 사람들의 몸무게를 오름차순으로 정렬한다.
2. deque 자료구조를 사용해 가장 가벼운 사람을 popleft로 꺼낸다.
3. queue에 남아 있는 사람들 중 가장 무거운 사람부터 반복문으로 비교하여, 무게 합이 limit을 넘지 않으면 그 사람을 queue에서 제거하고 보트에 태운다.
4. 반복문이 종료되면 보트 수(answer)를 증가시킨다.

실행 결과 정확성 테스트는 다 맞는데, 효율성 테스트에서 0점이다.

 

시간 복잡도

• people.sort()는 O(N log N)
• 각 루프에서 queue.popleft()는 O(1)
• queue.remove(queue[i])는 O(N) (중간 요소를 제거하는 연산이므로)
• 내부 반복문은 최악의 경우 리스트의 길이만큼 반복하므로, O(N)

그럼 최악의 경우 O(N)이 3번 중첩되어 있는 건가..

---

다른 풀이

투 포인터 풀이

몸무게 정렬 후, 처음과 끝 인덱스를 이동시켜 해를 구하는 풀이다.

def solution(people, limit):
    first = 0
    last = len(people) - 1
    answer = 0

    people.sort(reverse = True)

    while first <= last:

        if people[first] + people[last] <= limit:
            last -= 1

        first += 1
        answer += 1


    return answer

 

풀이

1. 사람들의 몸무게를 내림차순으로 정렬합니다.
2. 가장 무거운 사람과 가장 가벼운 사람을 비교합니다.
3. 두 사람의 무게 합이 limit 이하이면, 둘 다 보트에 태우고, last 포인터를 감소시킵니다.
4. 무거운 사람만 보트에 태울 수 있다면, 그 사람만 태우고 first 포인터를 증가시킵니다.
5. 보트 수(answer)를 증가시키면서 이 과정을 반복합니다.

시간 복잡도

• people.sort(reverse=True)는 O(N log N)
• while first <= last: 루프는 O(N)
• 루프 내의 연산은 O(1)이므로, 전체 시간 복잡도는 O(N log N)

---

회고

투 포인터 알고리즘

• 배열이나 리스트와 같은 데이터 구조에서 특정 조건을 만족하는 부분 배열을 찾거나, 두 요소의 합, 특정 값을 찾는 문제 등을 해결하기 위해 사용되는 기법
• 보통 배열을 정렬한 후, 두 개의 포인터를 이용해 효율적으로 문제를 해결하는 것에 유용
• 암튼 두 개의 포인터를 사용해 양방향으로 움직이며 데이터를 스캔하는 것이 핵심
• 주요 문제 유형
  • 두 요소의 합 (Two Sum 문제): 주어진 배열에서 두 숫자의 합이 특정 목표값(target)과 일치하는 두 숫자를 찾는 문제.
  • 가장 긴 부분 배열 찾기: 특정 조건을 만족하는 부분 배열 중 가장 긴 것을 찾는 문제.
  • 특정 조건을 만족하는 쌍 찾기: 배열에서 두 요소의 곱이나 차가 특정 값을 만족하는 쌍을 찾는 문제.