2021.06.13 정리
<1> 당장 좋은 것만 선택하는 그리디
- 그리디Greedy(탐욕법) 알고리즘은 단순하지만 강력한 문제 해결 방법
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
- 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
- 그리디 알고리즘은 기준에 따라 좋은 것만 선택하는 알고리즘으로 주로 정렬 알고리즘과 짝을 이룸
- 그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아님
- 대부분의 문제는 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 다분함
- 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 함
<2> 큰 수의 법칙
주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
입력조건
- 배열의 크기 N
- 숫자가 더해지는 횟수 M
- 연속해서 더해질 수 있는 횟수 K내가 작성한 코드
# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))
#####code#####
result = ((sorted(data)[-1] * k + sorted(data)[-2])) * (m // (k + 1))
+ (sorted(data)[-1] * (m % (k + 1)))
print(result)답안 예시
# 답안 예시
# 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] # 두 번째로 큰 수
# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)
result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기
print(result) # 최종 답안 출력<3> 숫자 카드 게임
N * M 형태로 놓은 카드 중 행에서 가장 낮은 숫자를 뽑음
뽑은 숫자 중 가장 큰 숫자를 뽑아야 함내가 작성한 코드
# 행의 개수와 열의 개수 입력
n, m = map(int, input().split())
##### code #####
min_data = []
for row_number in range(1, n+1):
data = list(map(int, input().split()))
min_data.append(min(data))
print(max(min_data))답안 예시 01
# 답안 예시 01 - min() 함수 이용
# N, M을 공백으로 구분하여 입력받기
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)답안 예시 02
# 답안 예시 02 - 이중 반복문 이용
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
data = list(map(int, input().split()))
# 현재 줄에서 가장 작은 수 찾기
min_value = 10001
for a in data:
min_value = min(min_value, a)
# 가장 작은 수 중에서 가장 큰 수 찾기
result = max(result, min_value)
print(result)<4> 1이 될 때까지
어떠한 수 N이 1이 될 때까지 반복
- N에서 1을 뺀다.
- N을 K로 나눈다.내가 작성한 코드
# n, k 입력
n, k = map(int, input().split())
count = 0
while n > 1 :
if n % k == 0:
n = n // k
count += 1
else:
n = n - 1
count += 1
if n == 1:
break
print(count)답안 예시 01
# 답안 예시 01
n, k = map(int, input().split())
result = 0
# N이 K 이상이라면 K로 계속 나누기
while n >= k:
# N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
while n % k != 0:
n -= 1
result += 1
# k로 나누기
n //= k
result += 1
# 마지막으로 남은 수에 대해서 1씩 빼기
while n > 1:
n -= 1
result += 1
print(result)답안 예시 02
# 답안 예시 02
n, k = map(int, input().split())
result = 0
while True:
# (n == K로 나누어떨어지는 수)가 될 때까지 1씩 빼기
target = (n // k) * k
result += (n - target)
n = target
# N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# k로 나누기
result += 1
n //= k
# 마지막에 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)이런 코딩을 제대로 공부해본적이 없어 코드를 짜는데 생각보다 시간이 걸렸다.
하지만 시간가는줄 모르고 집중하고 고민하게 되는게 꽤 재밌었다.
내가 작성한 코드가 좋은 접근방법인지 아닌지에 대한 피드백을 받아보고 싶은데 그럴 수 없다는 점이 아쉽다.
