그리디 & 구현

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법

거스름 돈 문제

import sys
# 시간복잡도는 O(n)
n = 1260
cnt = 0
li = [500,100,50,10]

for i in li:
    cnt += n // i
    n %= i
print(cnt)

1이 될때까지 문제

import sys

n,k = map(int,sys.stdin.readline().split())


cnt = 0

while True:
    if n == 1:
        break
    elif n % k !=0:
        n -= 1
        cnt +=1
    else:
        n = n // k
        cnt +=1
print(cnt)

곱하기 혹은 더하기 문제

import sys

li = list(map(str,input()))

result = 0
for i in li:
    if int(i) == 0 or int(i) == 1 or result <=1:
        result +=int(i)
    else:
        result *=int(i)
print(result)

모험가 길드 문제

import sys

n = int(sys.stdin.readline())

li = sorted(list(map(int,sys.stdin.readline().split())))

result = 0
cnt = 0
for i in li:
    cnt +=1
    if cnt >=i:
        result +=1
        cnt =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)

상하좌우 문제

import sys

n = int(sys.stdin.readline())

li = list(map(str,input().split()))
x = 0
y = 0
for i in li:
    if i == 'R':
        x += 1
    if i == 'U':
        y -= 1
        if y < 0:
            y = 0
    if i == 'L':
        x -= 1
        if x < 0:
            x = 0
    if i == 'D':
        y += 1
print(y+1,x+1)

시각 문제

import sys

n = int(sys.stdin.readline())

cnt = 0

for i in range(n+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) or '3' in str(j) or '3' in str(k):
                cnt +=1
print(cnt)

왕실의 나이트 문제

import sys

s = list(map(str,input()))

column = int(ord(s[0])-int(ord('a'))+1) # 가로
row = int(s[1]) # 세로

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

cnt = 0
for i in range(8):
    nx = column + dx[i]
    ny = row + dy[i]
    
    if 0 < nx <= 8 and 0 < ny <= 8:
        cnt +=1
print(cnt)

문자의 재정렬 문제

import sys

s = input()
result = []

sum = 0
for i in s:
    if i.isalpha():
        result.append(i)
    else:
        sum +=int(i)

result.append(str(sum))
print(''.join(result))

출처 : https://freedeveloper.tistory.com/272?category=888096