개발왕 양선규

# DFS/BFS로 모든 노드 탐색 # visited 목록 만들어서 True 갯수 세면 될듯 !! import sys N = int(sys.stdin.readline()) # 노드의 개수 E = int(sys.stdin.readline()) # 간선의 개수 graph = [[] for _ in range(N + 1)] # 노드번호와 동기화 하기 위해 N + 1 for _ in range(E): root, edge = map(int, sys.stdin.readline().split()) # [1,2] 형태로 입력된다. 1번과 2번에 연결되어 있다는 뜻 graph[root].append(edge) # 무방향(양방향) 그래프이기 때문에 대칭되게 입력해 준다 graph[edge].append(root) for ..

분할 정복(Divide and Conquer) - 여러 알고리즘의 기본이 되는 해결 방법, 엄청나게 크고 방대한 문제를 작은 단위로 쪼개어, 결과적으로 큰 문제를 해결하는 방법 - 퀵 정렬, 병합 정렬, 이분 탐색 등이 대표적 예시이다. - Divide를 제대로 나누면 Conquer은 자동으로 쉬워지기 때문에 Divide를 잘 설계하는 것이 매우 중요하다. - 분할 정복에서는 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복의 효율을 깎아내릴 수 있다. 분할 정복의 설계 1. Divide(분할) - 원래의 문제를 분할하여, 비슷한 유형의 하위 문제로 더 이상 분할이 불가능할 때 까지 나눈다. 2. Conquer(정복) - 각 하위 문제를 재귀적으로 해결한다. 더 이상 나눌 수 없는 단위일 때의 탈..

from collections import deque import sys def DFS(graph, v, visited): # 인접노드리스트, 시작 노드, 방문목록 visited[v] = True print(v, end=' ') for i in graph[v]: # 현재 노드의 인접 노드로 재귀 if visited[i] == False: # 아직 안 갔으면 가기 DFS(graph, i, visited) def BFS(graph, start, visited): # 인접노드리스트, 시작 노드, 방문목록 queue = deque([start]) # 큐에 시작 노드 넣기 visited[start] = True while queue: v = queue.popleft() # 큐에서 노드 빼고 출력 print(v, ..

import sys sys.setrecursionlimit(10**9) # 재귀호출 최대 깊이를 늘려준다 pre = [] # 전위순회 순서 입력받기 while True: try: n = int(sys.stdin.readline()) pre.append(n) except: break def postOrder(nodeList): # 전위순회 결과를 입력받는다 생각지 말고, 그냥 노드 리스트를 입력받는다 생각하면 이해가 편함 if len(nodeList) == 0: # 빈 리스트라면 return return left, right = [], [] root = nodeList[0] # root노드 기준으로 작은값, 큰값으로 나눈다 for i in range(1, len(nodeList)): # root노드 다음값..

import sys n = int(sys.stdin.readline()) tree = {} for _ in range(n): root, left, right = sys.stdin.readline().split() tree[root] = [left, right] # {'root' : ['left', 'right']} 형태로 저장한다 def preorder(root): # 전위 순회 if root != '.': print(root, end='') preorder(tree[root][0]) preorder(tree[root][1]) def inorder(root): # 중위 순회 if root != '.': inorder(tree[root][0]) print(root, end='') inorder(tree[r..

n = input() if len(n) == 1: # n이 한자릿수 라면 앞에 0을 붙인다 n = '0' + n cnt = 0 # 횟수를 세는 변수 num = n while True: num = num[1] + str(int(num[0]) + int(num[1]))[-1] # 새로운 수 제작 cnt += 1 # 제작할 때마다 카운트 + 1 if num == n: # n과 같아지면 break break print(cnt) n으로 새로운 수를 제작하여, 몇 번 새로운 수를 만들어야 다시 n으로 돌아오는지 출력하는 문제이다. n은 1~99 의 범위에서 주어진다. 예를 들어 26이 주어졌다면, 26의 오른쪽 자리인 "6", 그리고 각 자리를 합한 수의 오른쪽 자리인 2+6="8" 두개를 더하여 "68"을 만들어..

n = int(input()) # 변의 길이 board = [list(map(int, input().rstrip())) for _ in range(n)] # rstrip() 하면 개행문자 제거해서 한번에 입력할 수 있게 해준다 def quadTree(x, y, n): # x, y좌표와 변 길이를 입력받는다, 첫 호출은 0,0을 입력 color = board[x][y] for i in range(x, x+n): for j in range(y, y+n): # 현재 사각형의 모든 칸을 검사한다 if color != board[i][j]: # 색깔이 다른 칸이 하나라도 있다면 4등분 재귀호출 한다 print('(', end='') # 출력 양식에 맞게 괄호 입력 quadTree(x, y, n//2) # 출력 양..

n, s = map(int, input().split()) # 숫자의 개수, 목표 숫자 numList = list(map(int, input().split())) # 숫자 리스트 number = [] # 계산에 사용할 리스트 cnt = 0 # 경우의 수 저장할 변수 def back(start): # 시작 인덱스 입력받기 global cnt if sum(number) == s and len(number) > 0: # 합이 s와 같고, 원소가 1개 이상일 때 ( 공집합 제외 해야 하니까 ) cnt += 1 # 찾았으니 경우의 수 + 1 for i in range(start, len(numList)): # 입력받은 인덱스부터, numList의 끝까지 진행한다 number.append(numList[i]) # ..

def dac(a, b, c): # a^b % c if b == 1: return a % c elif b % 2 == 0: # b가 짝수일 때 return (dac(a, b//2, c)**2) % c else: return ((dac(a, b//2, c)**2)*a) % c a, b, c = map(int, input().split()) print(dac(a, b, c)) 분할 정복 알고리즘이 사용되며, (a ^ b) % c 의 결과를 출력하기만 하면 되는 문제이다. 그러나 주어지는 입력값이 int의 최대값인 21억 정도로 매우매우 크다. 시간 제한도 0.5초로 매우 짧기 때문에 일반적인 연산으로는 시간 초과가 뜬다. 때문에 수학 공식을 이용하여 작은 단위로 분할하여 연산 횟수를 줄여서 계산해야 한다. ..

import sys n = int(sys.stdin.readline()) # 탑 개수 towerList = list(map(int, sys.stdin.readline().split())) # 탑 목록 result = [0] * n # 결과 리스트 stack = [] # 후보 탑을 저장할 스택 for i in range(n): while stack: if towerList[stack[-1][0]]