이것이 취업을 위한 코딩 테스트다 with 파이썬
이것이 취업을 위한 코딩 테스트다 with 파이썬의 내용
시간 복잡도
알고리즘을 위해 필요한 연산의 횟수
공간 복잡도
알고리즘을 위해 필요한 메모리의 양
그리디 알고리즘
현재 상황에서 지금 당장 좋은 것만 고르는 방법
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
n = 1260 # 돈
count = 0 # 동전 개수
# 큰 단위의 화폐부터 차례대로
list = [500, 100, 50 ,10]
for coin in list:
count += n // 500
n %= coin
print(count)
5
화폐의 종류가 K개라고 할 때 위 코드의 시간 복잡도는 O(K)
이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받는다.
거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다
실전 문제
큰 수의 법칙
내 코드
import copy
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse=True)
result = 0
temp = copy.deepcopy(k)
for _ in range(m):
if temp == 0:
result += data[1]
temp = copy.deepcopy(k)
elif temp > 0:
result += data[0]
temp -= 1
else:
print(-1)
break
print(result)책의 단순한 풀이
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse=True)
first = data[0]
second = data[1]
result = 0
while True:
for i in range(k):
if m == 0:
break
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result)내 개선코드
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse=True)
first = data[0]
second = data[1]
# k+1번까지 덩어리로 묶음
lump = first * k + second
mul = lump * (m // (k+1)) # m // (k+1)번 덩어리가 나올 수 있으므로 곱함
plus = first * (m % (k+1)) # m을 k로 나눈 나머지만큼 first가 나올 수 있다.
print(mul + plus)책 개선코드
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse=True)
first = data[0]
second = data[1]
# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k+1)) * k
count += m % (k+1)
result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - k) * second # 두 번째로 큰 수 더하기
print(result)책의 코드가 더 깔끔하다.!
숫자 카드 게임
내 코드
n, m = map(int, input().split())
result = 0
for i in range(n):
data = min(list(map(int, input().split())))
if result < data:
result = data
print(result)책의 코드
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)내 코드에서 if 부분을 max(result, data)로 바꾸면 더 깔끔할 것 같다
1이 될 때까지
내 코드
n, k = map(int, input().split())
count = 0 # 횟수
while True:
if n == 1: # n이 1이라면 break
break
elif (n % k) > 0: # (n % k)를 n이 1이 되거나 (n % k)가 0이 될 때 까지 n을 1씩 빼준다.
count += 1
n -= 1
else: # n % k가 0이 아니라면
n /= k
count += 1
print(count)책의 코드
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)첫 번째 while문의 조건 while n > k를 활용하면 더 깔끔해지지 않을까
n이 100억 이상의 큰 수가 되는 경우를 가정했을 때에도 빠르게 동작하려면, n이 k의 배수가 되도록 한 번에 빼는 경우를 작성할 수 있다.
구현
완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
실전 문제
상하좌우
내 코드
n = int(input())
x, y = 1, 1
plans = input().split()
for plan in plans:
if plan == 'L' and 0 < x-1 < n+1: # Left, 이동했을 때 좌표가 범위를 벗어난다면 수행하지 않음
x = x - 1
elif plan == 'R' and 0 < x+1 < n+1: # Right, 이동했을 때 좌표가 범위를 벗어난다면 수행하지 않음
x = x + 1
elif plan == 'U' and 0 < y-1 < n+1: # Up, 이동했을 때 좌표가 범위를 벗어난다면 수행하지 않음
y = y - 1
elif plan == 'D' and 0 < y+1 < n+1: # Down, 이동했을 때 좌표가 범위를 벗어난다면 수행하지 않음
y = y + 1
print(x, y)시각
코드
n = int(input())
count = 0
for h in range(n+1): # 0시부터 n시
for m in range(60): # 0분부터 59분
for s in range(60): # 0초부터 59초
if '3' in str(h) + str(m) + str(s): # 문자열로 변환한뒤 더하여 3이 있는지 체크
count += 1 # 있다면 횟수 1증가
print(count)왕실의 나이트
내 코드
start = str(input())
dic = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8}
if start[0] not in dic.keys():
print(-1)
x = dic[start[0]]
y = int(start[1])
count = 0
# 이동 할 수 있는 모든 경우 체크
if 0 < (x+2) < 8 and 0 < (y+1) < 9:
count += 1
if 0 < (x+2) < 8 and 0 < (y-1) < 9:
count += 1
if 0 < (x-2) < 8 and 0 < (y+1) < 9:
count += 1
if 0 < (x-2) < 8 and 0 < (y-1) < 9:
count += 1
if 0 < (x+1) < 8 and 0 < (y+2) < 9:
count += 1
if 0 < (x+1) < 8 and 0 < (y-2) < 9:
count += 1
if 0 < (x-1) < 8 and 0 < (y+2) < 9:
count += 1
if 0 < (x-1) < 8 and 0 < (y-2) < 9:
count += 1
print(count)이 문제에서 이동할 수 있는 경우의 수가 적기 때문에 8가지 경우를 if문으로 적어도 상관이 없었으나 이동할 수 있는 경우가 많을 때에는 책의 코드처럼 이동하는 경우에 대한 Set을 만들고 반복문을 돌리는게 더 좋은 코드
https://github.com/minhaaan