꼭 알아야하는 코딩 테스트 유형: 6) #Greedy

• 이번에는 코딩 테스트에서 중요한 유형인 'Greedy(그리디)'에 대해 알아보겠습니다. 그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다. 현재 상황에서 가장 이익이 되는 선택을 하여 전체적인 결과를 도출합니다.

 

그리디 알고리즘의 개념

 

• 그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 방식으로 문제를 해결합니다. 매 순간 최적인 선택을 한다고 해서 전체적으로도 최적해를 구할 수 있는 것은 아니지만, 많은 경우에 그리디 접근법이 최적해에 근사한 결과를 제공합니다.
•  일반적으로 그리디 알고리즘은 다음과 같은 특징을 가지고 있습니다.

 

1. 탐욕적 선택: 각 단계에서 가장 좋아 보이는 선택을 합니다.
2. 지역 최적해: 각 단계의 선택이 지역적으로는 최선이지만, 전체적인 관점에서는 항상 최선이 아닐 수 있습니다.
3. 최소한의 조건: 일반적으로 그리디 알고리즘은 추가 조건 없이 현재 상태에서의 최선의 선택을 합니다.

 

그리디 문제 접근법

 

• 그리디 알고리즘은 코딩 테스트에서 다양한 문제 유형에 활용되며, 문제 해결에 필요한 직관력과 판단력이 요구됩니다. 아래는 코딩 테스트에서 그리디 문제를 해결하기 위한 일반적인 접근 방법입니다.

 

1. 문제 이해와 목표 설정: 주어진 문제를 정확하게 이해하고, 명확한 목표를 설정합니다.
2. 탐욕적인 선택 기준 정의: 각 단계마다 어떤 기준으로 탐욕적인 선택을 할 것인지 정의합니다.
3. 정당성 분석과 증명: 탐욕스러운 선택들이 항상 전체 결과에 대해서도 옳다는 것을 분석하고 증명합니다.
4. 구현과 시뮬레이션: 정의된 탐욕스러운 선택 기준에 따라 구현을 진행하고, 문제에서 요구하는 결과를 얻기 위해 시뮬레이션을 수행합니다.
5. 정렬과 그리디의 결합: 그리디 알고리즘은 종종 정렬과 함께 사용됩니다. 입력 데이터를 정렬하여 그리디 접근법을 더욱 효율적으로 적용할 수 있습니다.
6. 탐색 범위 축소: 문제의 제약 조건이나 특성에 따라 탐색 범위를 축소함으로써 시간 복잡도를 줄일 수 있습니다.
7. 예외 처리와 최적화: 일부 예외적인 경우에 대해서는 탐욕적인 선택이 최선이 아닐 수 있으므로, 예외 처리를 고려해야 합니다. 또한, 중복되는 계산을 피하기 위한 최적화 기법을 적용할 수 있습니다.
8. 시간 복잡도 분석과 최적화: 그리디 알고리즘은 일반적으로 간단하면서도 빠른 시간 복잡도를 가지지만, 경우에 따라 최악의 경우가 발생할 수 있습니다. 따라서 알고리즘의 시간 복잡도를 분석하고 필요한 경우 최적화하는 것이 중요합니다.
9. 출력 형식과 결과 확인: 문제에서 요구하는 출력 형식에 맞게 결과를 출력하고, 정답 여부를 확인합니다.
10. 테스트 케이스 작성과 검증: 주어진 예제나 추가적인 테스트 케이스를 작성하여 구현한 코드의 정확성을 검증합니다.

 

거스름돈 문제

 

• 거스름돈 문제는 주어진 금액에 대해 가장 적은 개수의 동전으로 거스름돈을 주는 것입니다.

def give_change(n, coins):
    count = 0
    
    for coin in coins[::-1]:
        count += n // coin
        n %= coin
    
    return count

• 위 코드는 n 원에 대해 coins 리스트 내의 동전들로 거스름돈을 주는 예시입니다. coins 리스트에는 거스름돈으로 사용 가능한 동전의 종류와 가치가 담겨있습니다. 코드는 가장 큰 가치의 동전부터 차례대로 사용하여 거스름돈을 주고, 필요한 동전의 개수를 세는 방식으로 구현되었습니다.

 

회의실 배정 문제

 

• 주어진 회의 일정 중 겹치지 않게 최대한 많은 회의를 진행하는 문제입니다.

def max_meetings(meetings):
    meetings.sort(key=lambda x: x[1])  # 끝나는 시간을 기준으로 정렬
    count = 0
    end_time = 0
    
    for meeting in meetings:
        if meeting[0] >= end_time:  # 현재 회의 시작 시간이 이전 회의 종료 시간보다 크거나 같으면 선택
            count += 1
            end_time = meeting[1]  # 선택된 회의 종료 시간 갱신
    
    return count

• 위 코드는 meetings 리스트에 각 회의의 시작과 끝나는 시간이 담겨있다고 가정하고, 겹치지 않게 최대한 많은 회의를 선택하는 예시입니다. meetings 리스트를 끝나는 시간을 기준으로 오름차순 정렬하고, 현재 선택된 회의가 이전에 선택된 회의와 겹치지 않도록 조건을 확인하여 최대 개수를 세는 방식으로 구현되었습니다.

 

1026번: 보물

  문제  
 

• 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
• 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

 

• S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
• S의 최솟값을 출력하는 프로그램을 작성하시오.

 

  해결 방법  
 

• 이 문제는 두 배열 A와 B가 있을 때, A의 모든 원소와 B의 원소를 곱하여 더한 값이 최소가 되도록 만드는 문제입니다.
• 그래서 가장 큰 수와 가장 작은 수를 곱하면서 진행한다면 결과값이 최소가 됩니다. 따라서 배열 A는 오름차순으로, 배열 B는 내림차순으로 정렬한 후에 각 위치의 수를 곱해 더하면 됩니다.

n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())), reverse=True)

print(sum(a[i] * b[i] for i in range(n)))

 

11000번: 강의실 배정

  문제  
 

• 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 
• 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
• 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
• 수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

  해결 방법  
 

• 이 문제는 강의가 시작하고 끝나는 시간이 주어졌을 때 필요한 최소 강의실의 수를 구하는 문제입니다.
• 강의를 시작 시간 순으로 정렬한 후에 각각의 강의에 대해 이미 사용중인 강의실 중에서 가장 먼저 빌 예정인 것과 비교하여 현재 강의가 그 이후에 시작한다면 해당 강의실을 사용하고 그렇지 않다면 새로운 강의실을 사용합니다.
• 이를 위해 우선순위 큐를 사용하여 현재 진행중인 모든 강의들 중에서 가장 먼저 끝나는 것을 항상 알 수 있도록 하였습니다.

import heapq
import sys; input=sys.stdin.readline

n = int(input())
st = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

rooms = []
heapq.heappush(rooms, st[0][1])

for i in range(1, n):
    if rooms[0] > st[i][0]: heapq.heappush(rooms, st[i][1])
    else:
        heapq.heappop(rooms)
        heapq.heappush(rooms, st[i][1])

print(len(rooms))

 

• 그리디 알고리즘은 많은 문제에서 효과적으로 활용될 수 있는 방법인데, 특히 '매 순간 최적이라고 생각되는 선택'을 하는 경우에 유용합니다. 하지만 항상 최적해를 보장하지는 않으므로 주어진 문제가 그리디 알고리즘으로 해결 가능한지 잘 판단하는 것이 중요합니다.
• 그리디 알고리즘 문제는 종종 정렬 등 다른 기본적인 알고리즘이 함께 활용되므로 이러한 기본 개념들도 잘 이해하고 있어야 합니다.