현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.
핵심 : "가장 큰, 가장 작은"과 같은 키워드가 존재
** 이 글은 책 '이것이 코딩테스트다' 를 공부하면서 공부한 내용이나 공부한 문제에 대한 나의 풀이를 적은 글이다.
문제 1 - 큰 수의 법칙
내 풀이
N, M, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
print(((M //(K+1)) * a[-1] * K) + ((M // (K+1)) * a[-2]) + ((M % (K+1)) * a [-1]))
- 출력이 가장 큰 수가 나오려면, 배열에서 가장 큰 수가 k번 나온 뒤, 2번째로 가장 큰 수가 1번 나오는 것이 반복되면 된다.
가장 큰 수가 k번 나오고, 2번째 큰 수가 1번 나오는 것을 한 묶음이라고 생각하면, 출력은 M을 (K+1)로 나눈 몫만큼 묶음이 반복되고, M을 K+1로 나눈 나머지만큼 가장 큰 수가 반복되면 된다.
이를 식으로 정리하여 출력하면 정답이 된다.
문제 2 - 숫자 카드 게임
내 풀이
N, M = map(int, input ().split ())
i=0
а = []
for i in range (N):
b=list(map(int, input().split()))
a.append(min(b))
print(max(a))- 열 중에서 가장 작은 수들 중 가장 큰 값이 나오는 열의 값을 출력해야한다. 그러기 위해서 입력받은 변수들을 리스트로 받아서 b라는 변수에 넣는다. 그리고 b에서의 최솟값을 a 리스트에 추가한다.
마지막으로 리스트 a에서 최대값을 출력하면 정답이 된다.
문제 3 - 1이 될 때까지
내 풀이
N, K = map(int, input() .split())
score = 0
while N !=1 :
if N % K == 0:
N = N//K
score = score +1
else:
N = N - K
score = score +1
print(score)- 나누는 것이 -1 하는 것보다 더 빨리 1이 되는 방법이므로, 나눌 수 있을 때는 무조건 나누는 것이 이득이다. 고로 나눌 수 없을 때는 -1을 하고, 나눌 수 있을 때는 나누는 코드를 작성하여 풀면 된다.
문제 4 - 곱하기 혹은 더하기
내 풀이
위의 사진과 같이 풀었지만, 너무 복잡하게 풀었음
다른 스터디원들의 코드를 본 결과
s = input()
result = 0
#초기 result 값을 0으로 설정하고 result 값이 0이거나
i 값이 0 또는 1이면 덧셈 연산
for i in s:
if result == 0 or int(i) == 1 or int(i) == 0:
result += int(i)
else:
result *= int(i)
print(result)위와 같이 풀 수 있음을 확인하였다. 내 코드가 복잡하게 돌아간 이유가 if 문에서 result 값이 0일때로 조건을 한정지으면 되는 것이었는 데, result 값을 조건으로 둘 생각을 못했기 때문이다.
문제 5 - 만들 수 없는 금액
내 풀이
일단, 이 문제에 대한 풀이는 못 푼 문제이기에 자세한 코드는 없다.
이 문제 관련해서 나의 접근 방식을 먼저 설명하자면, 일단 그리디에서 유명한 문제인 거스름돈 주기와 유사하다고 생각했다. a 배열을 받고, 이를 오름차순 정렬한다. 배열 a의 최댓값과 N을 곱한 수를 k라고 하자. t가 k*N 보다 크기 전까지 배열 내에서 t보다 큰 수들을 다 지운다.그리고 배열 a에서 가장 큰 수를 t에서 빼준다.
뺀 수가 만약 0보다 크면 다시 반복하고, 0이면 다음 i 로 넘어간다.
N = int(input())
a= list(map(int, input().split()))
k= a.max()
i=0
t=0
while i < k*N:
while t== 0:
a.append(t)
a.sort()
b= a.index(t)
del a[:t]
a.remove(t)
t= t - max(a)
if t >0:
##이러면 다시 새로운 t로 while 문을 돌리고 싶은데
자세한 코드를 못짜겠음
elif t<=0:
이러면 t는 못만드는 수 임으로 i가 못만드는 수가 됨.
i += 1
print(i)
위에 한글로 쓴 부분을 구현하지 못했고, 만약 하더라도 시간복잡도에서 좋지 않은 코드이며, t가 최댓값으로는 안만들어지지만 다른 수들로 만들어질 경우가 있음을 고려하지 못했으므로, 틀리게 푼 것 같다.
스터디원 코드
n = int(input())
data = list(map(int, input().split()))
data.sort()
target = 1
for i in data:
if i > target:
break
else:
target += i
print(target)어차피 1이 배열 내에 포함되지 않으면 만들지 못하는 수의 최솟값은 1이다.
최솟값부터 하나씩 확인하면서 target값과 비교하여 만들 수 없는 수를 찾는 형식이다.
