[백준][24416] 알고리즘 수업 - 피보나치 수 1
동적 프로그래밍 (DP) - 타뷸레이션 (Tabulation)
이 문제는 문제에서 제시한 재귀호출과 동적 프로그래밍 함수를 그대로 사용하면, 시간초과가 뜨는...
사악한 문제였다.
결국 재귀호출의 코드1은 n번째의 피보나치 수만큼 1을 더하는, 즉 30번째 피보나치 수가 832040 이면, 1을 832040번 더한 것이므로, 그냥 n번째의 피보나치 수를 구하면 되는 거였고,
동적 프로그래밍의 코드2는 동적 프로그래밍에서 해당 수를 구하기 위해,
n번째면 n-2 만큼 코드가 수행되는 것이므로,
구태여 계산하지 않고 n-2 를 구하면 되는 문제였다.
결국 코드1의 수행 횟수는 동적 프로그래밍을 이용해 구한 피보나치 수를 제시하고,
코드2의 수행 횟수는 n-2 로 구해서 제출하였더니 겨우겨우 통과..!
단순히 내 머리 속에서 나온 건 아니고, 팀원의 도움을 받았다.. so smart.. 🧐
import sys
from collections import deque
# n 의 피보나치 수를 구한다.
n = int(sys.stdin.readline())
# 재귀호출
f = [0, 1, 1]
def fib(n):
if n <= 2:
return 1
for i in range(3, n+1):
f.append(f[i-1] + f[i-2])
return f[n]
# 코드 1은 피보나치 수만큼 1을 더할 것이므로, 결국 원하는 값은 피보나치 수 그 잡채!
# 코드 2는 결국 n에서 -2만큼 수행하는 것이므로, 구태여 계산할 필요가 없다!
sys.stdout.write(f"{fib(n)} {n-2}")[백준][2748] 피보나치 수 2
동적 프로그래밍 (DP) - 타뷸레이션 (Tabulation)
이 문제는 위에서 푼 코드를 재활용하면 쉽게 해결 가능!
import sys
from collections import deque
n = int(sys.stdin.readline())
def fib(num):
f = [0, 1]
if num == 1:
return f[1]
for i in range(1, num):
f.append(f[i] + f[i-1])
return f[num]
print(fib(n))[백준][9095] 1, 2, 3 더하기
동적 프로그래밍 (DP) - 타뷸레이션 (Tabulation)
문제에서 n 이 11보다 작은 양수라고 조건이 주어졌길래,
그냥 cases 리스트를 만들어서, 해당 리스트에 10까지의 경우의 수를 모두 담아줬다.
n=3 일 때까지는 내가 경우의 수를 담아줬고,
n=4 부터는 n-1, n-2, n-3 일 때의 경우의 수의 합이 된다.
그렇게 해서 반복문 돌리면 끝!
import sys
from collections import deque
# 테스트 케이스의 개수 t
t = int(sys.stdin.readline())
cases = [0, 1, 2, 4]
for i in range(4, 11):
cases.append(cases[i-1] + cases[i-2] + cases[i-3])
for _ in range(t):
# 정수 n 은 양수이며, 11보다 작음
n = int(sys.stdin.readline())
print(cases[n])[백준][1463] 1로 만들기
동적 프로그래밍 (DP) - 타뷸레이션 (Tabulation)
이 문제는 팀원이랑 코드 리뷰 하면서 팀원이 풀어서, 푸는 방법은 이미 알고 있는 상태에서 시작했다.
처음에 단순히 if, else 로 3과 2로 나눠지는 경우에 무지성으로 나누었더니,
10처럼 3으로 나눠지진 않지만, 1을 빼서 9로 만든 후, 3을 두번 나누는 게 최소 횟수가 되는 경우도 있어서, 코드를 수정했다.
우선 before 함수에 n-1의 경우의 수를 담아준 후,
n이 3 또는 2로 나눠진다고 하더라도,
n을 3 또는 2로 나눈 수의 몫이 가지는 경우의 수가 before보다 작은 경우에,
before를 바꿔줬다.
만약 그럼에도 n-1의 경우의 수가 작다면, before 값을 유지했다.
그리고 before 값에 1을 더해주면, 최소 경우의 수가 나오게 된다.
import sys
from collections import deque
# 정수 n (1 이상 10의 6승 이하)
n = int(sys.stdin.readline())
make1 = [0, 0]
if n >= 2:
for i in range(2, n+1):
before = make1[i-1]
if i % 3 == 0 and make1[i//3] <= before:
before = make1[i//3]
if i % 2 == 0 and make1[i//2] <= before:
before = make1[i//2]
make1.append(before + 1)
print(make1[n])[백준][7576] 토마토 🍅
BFS(너비 우선 탐색)
너비 우선 탐색을 이용하는 문제였다.
며칠째 BFS만 주구장창 했더니, 이런 종류는 도가 튼듯..
거기다 오전에 팀원이 코드 리뷰에서 이걸 발표해서, 더 쉽게 풀었다 ㅎㅎ
import sys
from collections import deque
# sys.stdin = open("sample_input.txt", "r")
# m : 상자 가로 칸의 수, n : 상자 세로 칸의 수
m, n = map(int, sys.stdin.readline().split())
# 토마토 정보 받기
graph = list(list(map(int, sys.stdin.readline().split())) for _ in range(n))
# [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1]]
# 나만의 x, y 좌표는 이번엔 이렇게!
# (0,0), (0,1), (0,2), ...
# (1,0), (1,1), (1,2), ...
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(queue):
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if graph[nx][ny] == 0:
queue.append((nx, ny))
graph[nx][ny] = graph[x][y] + 1
day = float("-inf") # 음의 무한
for g in graph:
if 0 in g:
return -1
if max(g) > day:
day = max(g)
return day - 1
tomato = deque()
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
tomato.append((i, j))
print(bfs(tomato))[백준][1260] DFS와 BFS
DFS(깊이 우선 탐색), BFS(너비 우선 탐색)
문제 제목에서 알 수 있듯이, DFS와 BFS를 연습하는 문제였다.
함수 구현 자체는 빠르게 했으나, 테스트 케이스를 돌려보니 안 맞는 것들이 나와서 코드 수정을 했다.
문제가 된 부분이 한 노드에 여러 노드가 연결되어 있을 경우에는 작은 수부터 방문하는데,
내가 처음에 짠 코드는 가장 높은 수의 노드는 방문하지 리스트에 추가가 안 되게 되어 있었다.
그래서 sort() 함수를 적용했다.
import sys
from collections import deque
# sys.stdin = open("sample_input.txt", "r")
# n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작하는 정점 번호
n, m, v = map(int, sys.stdin.readline().split())
pairs = list(sorted(list(map(int, sys.stdin.readline().split())))
for _ in range(m))
# 예시 : [[4, 5], [2, 5], [1, 2], [3, 4], [1, 3]]
pairs_list = list([] for _ in range(n+1))
for p in pairs:
if p[1] not in pairs_list[p[0]]:
pairs_list[p[0]].append(p[1])
if p[0] not in pairs_list[p[1]]:
pairs_list[p[1]].append(p[0])
# 예시 : [[], [2, 3], [5, 1], [4, 1], [5, 3], [4, 2]]
for p in pairs_list:
p.sort()
# 예시 : [[], [2, 3], [1, 5], [1, 4], [3, 5], [2, 4]]
dfs_visited = []
bfs_visited = []
def dfs(v):
dfs_visited.append(str(v))
for d in pairs_list[v]:
if str(d) not in dfs_visited:
dfs(d)
return ' '.join(dfs_visited)
def bfs(v):
queue = deque()
queue.append(v)
while queue:
v = queue.popleft()
bfs_visited.append(str(v))
for p in pairs_list[v]:
if str(p) not in bfs_visited and p not in queue:
queue.append(p)
return ' '.join(bfs_visited)
print(dfs(v))
print(bfs(v))[SWEA][5174] [파이썬 SW 문제해결 기본] 8일차 - subtree
# 테스트 케이스의 수 t
t = int(input())
def preorder(n):
global count
if n: # n이 0이 아닐 때만
count += 1
preorder(left[n])
preorder(right[n])
for case in range(1, t + 1):
# e : 부모-자식 노드 쌍의 개수, n : 기준이 되는 노드
e, n = map(int, input().split())
input_list = list(map(int, input().split()))
left = [0] * (e+2)
right = [0] * (e+2)
count = 0
for i in range(0, len(input_list), 2):
parent, child = input_list[i], input_list[i+1]
if left[parent] == 0:
left[parent] = child
else:
right[parent] = child
preorder(n)
print(f"#{case} {count}")[SWEA][5658] [모의 SW 역량테스트] 보물상자 비밀번호
from collections import deque
# import sys
# sys.stdin = open("sample_input.txt", "r")
# 테스트 케이스의 수 T
T = int(input())
for t in range(1, T+1):
# n : 숫자의 개수 , k : 크기 순서
n, k = map(int, input().split())
# 16진수
numbers = deque(list(input()))
# 비밀번호 길이 (n은 4의 배수, 8 이상, 28 이하)
length = n // 4
# 회전의 경우의 수는 length 만큼!
# 비번 후보 담기
combinations = []
# 회전 수만큼 반복
for l in range(length):
# 이번 회전에 나온 비번 개수만큼 가져오기
for i in range(4):
password = ''
for j in range(length):
password += numbers[length * i + j]
if password not in combinations:
combinations.append(password)
num = numbers.popleft()
numbers.append(num)
# 16진수로 쓰기 int("문자열", 16)
result = list(map(lambda x: int(x, 16), combinations))
result.sort(reverse=True)
print(f"#{t} {result[k-1]}")[SWEA][2930] 힙
최대 힙 문제!
import heapq
# import sys
# sys.stdin = open("input.txt", "r")
# T : 테스트 케이스의 수
T = int(input())
for t in range(1, T+1):
# N : 수행해야 하는 연산의 수
N = int(input())
max_heap = []
heapq.heapify(max_heap)
delete = []
for _ in range(N):
op_num = list(map(int, input().split()))
if op_num[0] == 1:
heapq.heappush(max_heap, -op_num[1])
elif op_num[0] == 2:
if max_heap: # 힙에 값이 있으면
delete.append(str(-heapq.heappop(max_heap)))
else: # 힙이 비어있으면
delete.append(str(-1))
print(f"#{t} {' '.join(delete)}")