[그리디] 01 모험가 길드

01 모험가 길드

그리디란?

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다.
• 정확한 답을 도출하지 못할 수도 있지만 코딩테스트에서는 대부분 ‘최적의 해’를 찾는 문제가 출제되므로 그리디 알고리즘의 정당성을 고민하면서 문제 해결 방안을 떠올려야한다.
• 다양한 그리디 알고리즘
  • 다익스트라 최단 경로 알고리즘
    • 암기가 필요한 알고리즘이다. 팀 노트 필요!
    • 특정 노드까지의 최단 거리 계산한 다음 메모리에 저장하고 나중에 필요할 때 다시 꺼내 본다는 점에서 다이나믹 프로그래밍으로 분류하기도 한다.
  • 크루스칼 알고리즘
    • 우선순위 큐 (최소 힙, 최대 힙)
    • 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

---

문제

한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데, 공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.

동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는 지 궁금하다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 모험가의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
• 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분한다.

출력 조건

• 여행을 떠날 수 있는 그룹 수의 최댓값을 출력한다.

---

사고 과정

• 공포도가 작은 모험가로 그룹을 만들 수록 더 많은 그룹을 만들 수 있다.

  ⇒ 정렬하기

• 그룹원 수 ≥ 공포도이면, 그룹 수를 증가하고, 그룹원 수를 초기화한다.

  그룹원 수 < 공포도 이면, 그룹원 수를 증가시킨다.

---

풀이

나의 코드

# 모험가의 수와 모험가의 공포도 입력받기
n = int(input())
n_list = list(map(int, input().split())) # 둘 다 괄호가 필요하다.

# 여행을 떠날 수 있는 그룹 수의 최댓값 출력

# 1. 정렬
n_list.sort() # 1 2 2 2 3
# 2. 그룹원 수 >= 공포도이면, result +1, 그렇지 않으면 그룹원 수 증가
g = 1 # 그룹원 수 1명으로 초기화
result = 0 # 그룹 개수
for i in n_list:
  if g >= i:
    result += 1
    g = 1
  else:
    g += 1

print(result)

책의 코드

n = int(input())
data = list(map(int, input().split())
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
	count += 1 # 현재 그룹에 해당 모험가를 포함시키기
	if count >= i:
		result += 1 # 총 그룹 수 증가시키기
		count = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(result) # 총 그룹의 수 출력

---

💡사고 과정 흐름을 공식화하자

• 그리디는 최소, 최대가 중요하므로 정렬을 한다.

• 원소의 개수가 특정 조건을 충족하면 어떤 일을 시행하는 경우가 반복될 때

  ⇒ (리스트 원소의 개수) 변수를 생성하고 하나씩 변형해가면서, 특정 조건이 충족되면 초기화하는 방식을 반복한다.

    count = 0 # 원소의 개수 변수 생성
      
    for i in data: 
    	count += 1 # 1을 더해감, 변형
    	if count >= i: # 원소의 개수가 특정 수 이상이면
    		result += 1 # (어떤 일 시행)
    		count = 0 # 원소의 개수 변수 초기화