(1) 그리디 알고리즘, 탐욕적인 알고리즘

"이것이 코딩테스트다 with 파이썬" 책을 공부하며 작성하는 글입니다. 

3챕터 그리디 알고리즘

 

그리디 알고리즘 Greedy algorithm이란 현재 상황에서 당장 좋은 것만을 선택하는 것이다. 

대부분의 문제에서는 최적의 해를 찾을 수 없을 가능성이 높으나, 탐욕적인 접근이 필요한 문제에서는 효과적이며 직관적이다. 

문제가 어렵다면 먼저 그리디로 접근 ->  다른 알고리즘 해보기 

다익스트라 알고리즘은 그리디 알고리즘에 속하나 암기가 필요하다. 

 

 

-유명한 거스름돈 문제 

1260원을 500원, 100원, 50원, 10원으로 최소 동전갯수로 하기 

-> 

n=1260을 큰 수의 동전부터 나누고, 

나머지를 n으로 갱신하여 반복한다. 

*큰 단위가 항상 작은 단위의 배수여야한다.

ex) n= 800일 때 500, 400, 100원이 있으면 500 100 100 100 보다 400 400 이 더 적은 동전을 사용하나 알고리즘 실행시 전자로 나오게 된다.

 

 

 

3-2 큰 수의 법칙

n, m, k = map(int, input().split()) #정수형으로 여러개 입력

arr=list(map(int, input().split())) #한 줄에 정수 입력받아 배열에 넣는다    
arr.sort() #오름차순 정렬

a= int(m/(k+1)) #작은 수 더하는 횟수
b= m-a

print( arr[n-1]*b + arr[n-2]*a)

이렇게 풀었는데 그리디 알고리즘은 아닌 것 같다. . 😅 

뒤에있는 3-2.py의 답안과는 유사했다. 

그리디 알고리즘으로 푸는 방법은, 

m이 0이 될 때까지 

반복문안에서 k만큼 큰 수를 더하고, m--해준다. m=0이면 종료

k만큼 더했으면 두번째로 큰 수를 더해주고  m--해준다. 마찬가지로 m=0이면 종료

 

이걸 루프로 한다.

 

 

 

 

 

3-3. 숫자 카드 게임 

 

n , m=map(int, input().split()) #정수형 여러 개 입력 n행 m열 배열 카드 생성

arr=[[0]*m for i in range(n)] # m열 n행 2차원 리스트 생성
for i in range(n):
        arr[i]=list(map(int, input().split()))
        arr[i].sort() #오름차순 정렬
        
max=arr[0][0]

for i in range(1, n):
    if(max<arr[i][0]): max=arr[i][0]
        
print(max)

이렇게 풀었는데

더 간단하게 푸는법

1. 파이썬 내장 함수  min()이 있구나

2. 굳이 데이터 입력받을 리스트가 필요없다. (최종 출력값만 있으면 되기 때문 )  

 

그때그때 데이터를 입력받고, 거기서 최소를 찾아 갱신하고, 미리 준비한 result값과 최솟값을 비교하고 

최종 result값을 출력한다. 

백준 문제를 풀 때도 느끼는 거지만 굳이 필요없는 공간들을 선언할 때가 종종 있는데 

이런 점도 많이 풀다보면 늘겠지 ,1! 

 

 

3-4. 1이 될 때까지

n, m= map(int, input().split())
count=0
while(n>1):
    if(n%m==0):
        n/=m
    else:
        n-=1
    count+=1
    
print(count)

 

n>1일때까지 while문으로

n이 m으로 나누어떨어진다면 n=n/m이고 

아니라면 1을 빼준다

매 루프마다 count는 1을 증가한다 

 

 

 

 

 

---

그리디 알고리즘은 탐욕적인 알고리즘으로, 가장 최선의 선택을 한다