그리디

동전 예시

n = 1260
count = 0
array = [500, 100, 50, 10]

for coin in array :
  count += n // coin
  n %= coin

print(count) 

 

화폐 종류가 k일 때, 시간복잡도 O(k) = 금액과 무관

 

 

1이 될 때까지

n = 25
k = 5

count = 0
while n != 1 :
  if n % k != 0 :
    n -= 1
    count += 1
  else :
    n = n // k
    count += 1

print(count)

내 풀이

 

n,k = map(int, input().split())

result = 0

while True :

  target = (n//k) * k
  result += (n - target)
  n = target

  if n < k:
    break
  
  result += 1
  n //= k

result += (n-1)
print(result)
  

최적화

 

곱하기 혹은 더하기

str = "02984"

if str[0] == "0" :
  result = 0
else :
  result = int(str[0])

for i in range(1,len(str)) :
  if int(str[i-1]) <= 1 or int(str[i]) <= 1 :
    result += int(str[i])
  else :
    result *= int(str[i])

print(result)

내 풀이 : 틀린 게 많음

 

data = input
result = int(data[0])

for i in range(1, len(data)) :
  num = int(data[i])
  if num <= 1 or result <= 1 :
    result += num
  else : 
    result *= num

print(result)

최적화

 

모험가 길드

res = []
res[arr[0]] = 1

for i in range(1, len(arr)) :
  res[arr[i]] += 1

count = 0
for i in range(1, len(res)) :
  if i <= arr[i] :
    count += 1

print(count)

내 코드 -> 오류

 

n = int(input())
data = list(map(int, input().split()))
data.sort

result = 0
count = 0

for i in data :
  count += 1
  if count >= i :
    result += 1
    count = 0

print(result)

최적화

 

---

방향 벡터

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

x, y = 2, 2

for i in range(4) :
	nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

 

상하좌우 문제

n = int(input())
x, y = 1, 1
plans = input().split()

dx = [0,0,-1,1]
dy = [-1,1,0,0]
types = ['L', 'R', 'U', 'D']

for plan in plans :
  for i in range(len(types)):
    if plan == types[i] :
      nx = x + dx[i]
      ny = y + dy[i]
  if nx == 0 or ny == 0 or nx > n or ny > n :
    continue
  x, y = nx, ny
  
print(x, y)

 

---

시각

h = int(input())

count = 0
for i in range(h+1) :
  for j in range(60) :
    for k in range(60) :
      if '3' in str(i)+ str(j) + str(k) : 
        count += 1
print(count)

 

왕실의 나이트

ord() : 특정한 한 문자를 아스키 코드로 바꿔줌

chr() : 아스키 코드 값을 문자로 바꿔줌

 

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

steps = [(-2,-1),(-2,1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2)]

result = 0
for step in steps : 
  next_row = row + step[0]
  next_column = column + step[1]
  if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8 :
    result += 1
print(result)

 

 

문자열 재정렬

list = str.split() : 문자열 => 리스트, 공백시 스페이스 기준

data = input()
result = []
value = 0

for i in data :
  if i.isalpha() :
    result.append(i)
  else :
    value += int(i)
result.sort
if value != 0 :
  result.append(str(value))
print(''.join(result))