알고리즘 with 파이썬 (4) - 그리디

그리디: 지금 당장 좋은것을 고르는 방법. 현재의 선택이 나중에 미칠 영향을 고려하지 않을때 사용

 

Ex ) 큰 수의 법칙 예제

입력받은 숫자들을 M 번 더해 가장 큰 수를 만들어라

 

첫줄에 숫자 세개를 입력받는다 = 배열 크기 N, 숫자 더해지는 횟수 M, 연속더하기 가능한 수 K
# 2<= N <=1000
# 1<= M <= 10000
# 1<= K <=10000
둘째 줄에 더하기를 실행할 자연수 N개를 입력받는다

 

#N, M, K 를 공백으로 구분하여 입력받기
n,m,k = map(int, input("숫자 세개 입력").split())
#N개의 수를 공백으로 구분하여 입력받기
data = list(map(int,input("숫자배열입력").split()))

data.sort() # 입력받은 수들 정렬하기
first = data[n-1] #가장큰수
second = data[n-2] # 두번쨰로 큰수

result = 0

while True:
    for i in range(k): # 가장 큰 수를 K번 더하기
        if m==0: #m이 0이면 반복문 탈출
            break
        result+=first
        m-=1
        if m==0:
            break
        result+=second
        m-=1

print(result)

 

알고리즘은 맞았지만, 입력받고 정렬하는데에서 시간을 많이 쏟았다

파이썬의 문법에 아직 약해서그런 것 같다. 입출력을 숫자로 받는건 자주 사용될 것 같으니 꼭 기억할 것

 - split(): str 값을 매개변수를 기준으로 쪼갠다. 

 - list(): 쪼개진 값들을 배열 인자로 받는다 (사실 split 한채로만 넣어도 배열로 들어가는데, map이 먹질 않는다)

 - map(자료형, 자료) : 자료들을 특정 자료형으로 바꾼다.

 - sort 로 숫자 배열을 빠르게 정렬할 수 있다 (나는 모르고 크기 비교하는 함수를 만들어버렸다)

 

알고리즘을 공부하다보니 파이썬 문법에 대한이해가 시간단축의 key가 될것 같다