알고리즘 기출문제: 그리디

1. 모험가 길드

 

n명의 모험가가 있다

각각의 모험가는 공포도가 있는데,

공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 모험을 떠날 수 있다

최대 몇개의 모험가 그룹을 만들 수 있을까?

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를 세고

현재 모험가의 공포도보다 count가 크거나 같다면 

result+=1, 

count는 초기화 한다

---

 

2. 곱하기 혹은 더하기

 

각 자리가 숫자로만 이루어진 문자열 S가 주어진다.

왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+'연산자를 넣어 결과적으롤 만들어 질 수 있는 가장 큰 수를 구하라.

 

s=input()

result=int(s[0])

for i in range(1,len(s)):
    if result==0 or int(s[i])==0 or result==1 or int(s[i])==1:
        result+=int(s[i])
    else:
        result*=int(s[i])


print(result)

연산중인 숫자가 0,1이거나 다음 연산할 숫자가 0,1인 경우엔 더하고 나머지 경우는 곱한다

 

---

3. 문자열 뒤집기

 

0과1로만 이루어진 문자열 s가 있다.

이 문자열s에 있는 모든 숫자를 전부 같게 만들려 한다.

s에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이 가능하다

뒤집기의 최소 횟수는?

s=input()

result_0=0 #0으로 만드는 경우

idx=0
zero=False
while idx<len(s):
    if int(s[idx])==0 and zero==False:
        zero=True
        result_0+=1

    elif int(s[idx])==1:
        zero=False

    idx+=1

result_1=0 #1로 만드는 경우

idx=0
one=False
while idx<len(s):
    if int(s[idx])==1 and one==False:
        one=True
        result_1+=1

    elif int(s[idx])==0:
        one=False

    idx+=1

print(min(result_1,result_0))

뒤집어서 s를 0으로 만드는 경우와

s를 1로 만드는 경우를 따로 계산해서 그 최솟값을 출력했다

0으로 만드는 경우를 설명하자면

zero=False로 초기화한다. 이 변수는 이전 숫자가 0이었는지를 기록하는 용이다

이제 숫자를 하나씩 확인한다.

이 전 숫자가 0이 아니었고(zero=False) 현재 숫자가 0인 경우에는 한번 뒤집는걸 카운트한다(result_0+=1)

그리고 현재 숫자가 0이므로 zero=True로 바꿔준다

다른경우, 현재숫자가 1이라면 zero=False로 바꿔준다

현재 숫자가0이고 zero=True라면 아무것도 하지 않는다

이렇게 하면 연속된 0이 나오는 경우에도 result는 1만 증가하게 된다

 

이렇게 뒤집는 횟수를 카운트했다.

 

다른 정답코드는 더 간단하니 다른걸 참고하는것도 좋을듯

---

4. 만들 수 없는 금액

N개의 동전이 있다.

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하라

n=int(input())
coins=list(map(int,input()))
coins.sort()

target=1

for coin in coins:
    if target < coin:
        break
    target+=coin

print(target)

동전을 오름차순으로 정렬하고

target을 1로 초기설정한다

 

이후 동전을 하나씩 꺼내 target과 비교한다

꺼낸 동전이 target보다 작다면 target+동전-1까지는 다 만들수가 있다

target보다 동전이 크면..

target의 금액을 만들수가 없으므로 중단