링크 : acmicpc.net/problem/1003
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
n = int(input())
dp = [ [1, 0], [0, 1] ]
for i in range(2, n+1):
dp.append([ (dp[-1][0] + dp[-2][0]), (dp[-1][1] + dp[-2][1]) ])
print(*dp[n])
링크 : https://www.acmicpc.net/problem/1012
from sys import stdin
from collections import deque
input = stdin.readline
T = int(input())
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def bfs(x, y):
visited[x][y] = True
q = deque([(x, y)])
while q:
px, py = q.popleft()
for k in range(4):
mx = px + dx[k]
my = py + dy[k]
if 0 <= mx < n and 0 <= my < m:
if land[mx][my] == 1 and not visited[mx][my]:
visited[mx][my] = True
q.append((mx, my))
for _ in range(T):
m, n, k = map(int, input().split())
answer = 0
land = [ [0] * m for _ in range(n) ]
visited = [ [False] * m for _ in range(n) ]
for _ in range(k):
a, b = map(int, input().split())
land[b][a] = 1
for i in range(n):
for j in range(m):
if land[i][j] == 1 and not visited[i][j]:
bfs(i, j)
answer += 1
print(answer)
링크 : https://www.acmicpc.net/problem/1074
from sys import stdin
input = stdin.readline
n, r, c = map(int, input().split())
cnt = 0
def div_and_con(x, y, l):
global cnt
if x == r and y == c:
print(cnt)
exit(0) # return을 해주면 안되는게 내부적으로 분할정복이 계속 돌고있어 조건을 만족하면 강제종료 해줘야 함
if l == 1: # 더이상 분할정복 할 필요가 없는 경우
cnt += 1
return
if not (x <= r <= x+l and y <= c <= y+l): # 4사분면으로 나누었을때 찾고자 하는 r, c행렬이 해당 사분면 안에 없을 때 사분면 건너뛰기
cnt += l * l
return
l //= 2
div_and_con(x, y, l)
div_and_con(x, y+l, l)
div_and_con(x+l, y, l)
div_and_con(x+l, y+l, l)
div_and_con(0, 0, 2**n)
print(cnt)
링크 : https://www.acmicpc.net/problem/1107
move = int(input())
n = int(input())
if n: # 고장난게 있을 경우에만 값을 입력받음
broken = list(input().split())
else:
broken = []
res = abs(100 - move) # 버튼을 누르지 않고 + or - 로 일일이 찾아가는 방법 (최대값)
# 작은수에서 큰수로 이동할땐 500,000 까지만 보면 되지만
# 반대로 큰수에서 작은수로 내려오는 경우가 더 최소가 될 수 있으므로 1,000,000 까지 봐야함
for i in range(1000001):
for j in str(i):
if j in broken: # 해당 숫자를 번호를 눌러서 만들 수 없는 경우는 스탑
break
else: # 번호를 만들 수 있는 경우
# min(기존답, len(str(i)) + abs(i-move))
res = min(res, len(str(i)) + abs(i-move))
print(res)
링크 : https://www.acmicpc.net/problem/1260
from sys import stdin
from collections import deque
input = stdin.readline
n, m, v = map(int, input().split())
graph = [ [] for _ in range(n+1) ]
answer_bfs = []
answer_dfs = []
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in graph: # 정점 번호가 작은 것 부터 탐색하기 위해 미리 정렬
i.sort()
def bfs(x): # 일반적인 BFS 방식
visited = [False] * (n+1)
visited[x] = True
answer_bfs.append(x)
q = deque([x])
while q:
node = q.popleft()
for i in graph[node]:
if not visited[i]:
visited[i] = True
answer_bfs.append(i)
q.append(i)
def dfs(x): # 일반적인 DFS 방식
visited[x] = True
answer_dfs.append(x)
for i in graph[x]:
if not visited[i]:
dfs(i)
# BFS는 함수 1번 호출에 내부 반복문 에서 visited를 쓰기 때문에 함수 내부에 visited를 생성해도 상관 없지만
# DFS는 함수를 여러번 호출 하므로 함수 외부에 visited를 생성해서 방문 여부를 체크해주는 식으로 해야 한다.
visited = [False] * (n+1)
dfs(v)
print(*answer_dfs)
bfs(v)
print(*answer_bfs)