:현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
, 매 순간 가장 좋아보이는 것만을 선택, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야함
바로 문제 유형을 파악하기 어려우면 그리디 알고리즘인지 의심
--> 해결하기 어렵다면
--> 다이나믹 프로그래밍, 그래프 알고리즘 등으로 해결할 수 있는지 고민
예제 3-2
#배열을 이용하여 가장 큰 값을 만들어내야함 M개의 값을 이용하나, K번 연속 사용할 수 없음
#첫째 줄에 N(2~1,000), M(1~10,000), K(1~10,000) 각 수는 공백으로 구분
#둘때 줄에 N개의 자연수(1~10,000), 공백으로 구분
#K <= M
1) 처음엔 (K+1)을 for, while문을 이용해 M번 반복하지만
M이 커지면 비효율적임
2) 규칙을 찾아내서 연산화함
책 -> 가장 큰 수가 나오는 횟수를 계산하여 횟수 * 큰 수, 작은 수도 횟수에 맞게 곱한 후 더해줌
3-2코드 (책)
n, m ,k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
first = data[n-1]
second = data[n-2]
count = int(m /(k + 1)) * k
count += m % (k + 1)
result = 0
result += (count) * first
result += (m - count) * second
print(result)**
-파이썬은 간단한 코드를 짤 때만 사용했어서 파일 입출력이 익숙했고 사용자 입력은 한 가지 값만 받는 input()만 알고 있었음
그래서 입력으로 여러 값을 한번에 받는건 첨 봄
예제 코드보고 저자 방식인건지 보통 다들 저렇게 하는지 궁금해서
"파이썬 여러값 입력"을 구글링해서 나온 블로그에서도 map(int, input().split()) 쓰길래
익혀둬야겠다 싶었음 바로 list로 만드는 것도 흥미롭삼 ㅎ
-sort()함수 쓰는 것도 내가 바로 코드 짰다면 저렇게 안했을텐데 보고 감탄...
-data[n-1] 이랑 data[-1]이랑 다르게 작동되나?
책에서 사용한 방식은 가장 큰 수와 두번째로 큰 수가 나오는 횟수를 계산한 후 곱해서 더해줬었음
나도 생각나는 방식으로 다시 짜봤다~!
n, m ,k = map(int, input().split())
data = list(map(int, input().split()))
first = data[-1]
second = data[-2]
temp = first * k + second
result = (m // (k + 1)) * temp + (m % (k + 1)) * k
print(result)시간 측정해보니까 둘 다 0.0이었다
ㅇvㅇ
예제 3-3
n, m = map(int, input().split())
result = 0
for i in range(n):
data = list(map(int, input().split()))
min_value = min(data)
result = max(result, min_value)
print(result)책에선 min함수 쓰는 코드와 이중 반복문을 사용하는 코드 두 가지를
제공했는데 min함수 쓰는게 난 더 좋았삼
문제 이해가 좀 안된 것 빼곤 간단했삼
예제 3-4
정수 N이 1이 될 때까지 1을 빼거나, K로 나눠지는 경울 K로 나눈다.
1이 되는 최소 횟수 구하기
-뭔가 내가 풀어볼 수 있을 것 같았다!
코드를 보기 전에 짠 코드
n, k = map(int, input().split())
cnt = 0
while n != 1:
if n % k == 0:
n //= k
cnt += 1
else:
n -= 1
cnt += 1
print(cnt)제공하는 코드를 본 후 조금 수정을 해봤다
n, k = map(int, input().split())
cnt = 0
while n != 1:
while n % k == 0:
n //= k
cnt += 1
if n < k:
cnt += (n - 1)
break
n -= 1
cnt += 1
print(cnt)입력을 423423434 7로 했을 때
시간은 time: 4.0663 --> time: 1.0029로 줄었다
풀었다고 좋아하고 있었는데 더 좋은 해결법이 있다니 ㅎ
풀고나서도 생각을 좀 더 해봐야겠다,,,
코딩은 재밌어 😎
