그리디 알고리즘

그리디=탐욕법, 욕심쟁이 

문제해결에 최소한의 아이디어를 요구 

예) 최단경로

동적계획: 모든 경로(경우의 수)를 탐색

탐욕법: 현재 갈 수 있는 가장 가까운 길만을 사용 

 

문제1: 문제 : N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택 수행하는 방법은? 최소값을 출력하시오.

입력예)

25 5

출력 예)

2

n,k=map(int,input().split())

result=0

while True:
    target=(n//k)*k    //k로나누어 떨어지는 수를 구함    
    result+=(n-target)
    n=target  
    if n<k:
        break
    result+=1
    n//=k
result+=(n-1)
print(result)

-> 나누기 빼기의 기준은 k로 나누어 떨어지지 않으면 -1 , 나누어떨어지면 나누기

 

---

문제: 마을에 모험가 N명을 대상으로 공포도를 측정했다. 공포도가 높으면 던전 입장이 어렵다. 공포도가 X인 모험가는 반드시 X명 이상으로 모험가 그룹에 참여해야 던전 입장이 가능하다. 최대 몇 개의 모험가 그룹을 만들 수 있는지 출력하라.

입력 예)

5

2 3 1 2 2 

출력 예)

2

해결책? 공포도를 확인하면서, 현재 모험가수를 확인한다. 공포도보다 크거나 같으면 그룹으로 생성함.

또한 낮은 모험가부터 확인 sort정렬 

n=int(input())
x=list(map(int,input().split()))
x.sort()
result=0 #총 그룹의 수  
count=0 #현재 그룹에 포함된 모험가의 수 

for i in x:
    count+=1
    if count>=i:
        result+=1 
        count=0 #현재 그룹에 포함된 모험가의 수 초기화
print(result)

->내가 출력에 오류난 이유? count=0을 하지 않음. 현재 그룹에 포함된 모험가의 수 초기화하지 않았기 때문에.

 

---

문제 : 여러 개의 카드 중에서 가장 높은 숫자가 쓰인 카드를 뽑자. N X M 형태로 나열되어 있다. N은 행의 개수, M은 열의 개수이다. 각 행 마다 작은 카드를 고른 후 그 중 가장 큰 카드의 값을 출력한다.

입력 예) 

3 3

3 1 2 

4 1 4

2 2 2

출력 예)

2

n,m=map(int,input().split())
result=0
for i in range(n):
    a=list(map(int,input().split()))
    min_data=min(a)
    result=max(result,min_data)
print(result)

-> min,max 로 가장 작은 수 중 최댓값 찾기