차곡차곡

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 정답 code #트리의 순회 import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) n = int(input()) inorder = list(map(int,input().split())) postorder = list(map(int,input().split())) #후위순회에서 최상위노드를 찾은후 중위순회에서 찾기위해 인덱스번호 부여 nodenum = [0] ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 정답 code #벽부스고 이동하기 from collections import deque dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(x,y,z): queue = deque() queue.append((x,y,z)) while queue: a,b,c = queue.popleft() #끝에 도달한경우 결과값 반환 if a == n-1 and b ==..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 정답 code #내려가기 import sys input = sys.stdin.readline n = int(input()) score = list(map(int,input().split())) maxdp = score mindp = score for _ in range(n-1): a,b,c = map(int,input().split()) maxdp = [a+max(maxdp[0], maxdp[1]), b+max..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 정답 code #트리 순회 import sys input = sys.stdin.readline #전위 순회 def preorder(root): if root != '.': print(root, end='') preorder(tree[root][0]) preorder(tree[root][1]) #중위 순회 def inorder(root): if root != '.': inorder(tre..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 정답 code #정수 삼각형 import sys input = sys.stdin.readline n = int(input()) t = [] for _ in range(n): num = list(map(int,input().split())) t.append(num) for i in range(1,n): # 층수 (0층은 한개의 값) for j in range(i+1): #가로줄 선택 (층수+1)개만큼 존재 # 가장 왼쪽 값일때 위의 값 if j == 0: t[i][j] ..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 정답 code # 후위 표기식 pn = input() stack = [] res = '' #결과값 저장 for p in pn: #알파벳일때, 결과값에 추가 if p.isalpha(): res += p else: # ( 일때 if p =='(': stack.append(p) # *, / 인경우 같은 우선순위인 *, / 가 있으면 결과값에 추가 elif p == '*' or p == '/': wh..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 정답 code # 최소비용 구하기 import heapq import sys input = sys.stdin.readline INT = int(1e9) def dijkstra(start): q = [] heapq.heappush(q,(0,start)) visit = [INT] * (n+1) visit[start] = 0 while q: dist, node = he..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 정답 code #웜홀 import sys input = sys.stdin.readline INF = int(1e9) def bellma_ford(start): visit = [INF]*(n+1) visit[start] = 0 #정점 개수만큼 반복 for i in range(n): for j in range(1,n+1): for next_node , time in roads[j]: #다..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 정답 code #최단경로 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start): q = [] heapq.heappush(q,(0,start)) visit = [INF] * (v+1) visit[start] = 0 while q: dist , node = heap..

정답 code # 곱셈 import sys input = sys.stdin.readline a,b,c = map(int,input().split()) def power(a,b): if b == 1: return a%c else: tmp = power(a,b//2) if b%2 == 0: return tmp * tmp % c #b가 짝수 else: return tmp*tmp* a % c #b가 홀수 print(power(a,b)) solution 이 문제는 단순하게 모두 곱한후 나누면 시간초과가 난다. 따라서 분할정복을 통해 나눠서 계산해줘야되는데 10 ^ 11 = 10^5 * 10^5 * 10 이런식으로 분할하여 시간을 줄여주는 것이다. 만약 b가 짝수라면 a를 한번더 곱해주지 않고 10 ^ 10 = 1..