본문 바로가기

분류 전체보기

 (402)
[백준 2166번] 다각형의 면적 (Python3) import sys input = sys.stdin.readline N = int(input()) xy = [] for i in range(N): xy.append(tuple(map(int,input().split()))) result = 0 for i in range(N-1): x1,y1 = xy[i] x2,y2 = xy[i+1] result += (x1*y2-x2*y1)/2 x1,y1 = xy[-1] x2,y2 = xy[0] result += (x1*y2-x2*y1)/2 print(abs(round(result,1))) 수학적인 배경지식이 조금 있어야 풀 수 있는 문제. 두 벡터의 외적이 평행사변형의 넓이라는것을 알면 쉽게 풀 수 있다. 0,0을 기준점으로 잡고 처음점과 두번째 점까지의 벡터를 외적하..
[백준 12852번] 1로 만들기 2 (Python3) import sys input = sys.stdin.readline from collections import deque INF = 10**9 N = int(input()) DP = [INF]*(N+1) last = {} dq = deque() dq.append(1) DP[1] = 0 while dq: n = dq.popleft() if n*3 DP[n]+1: DP[n*3] = DP[n]+1 last[n*3] = n dq.append(n*3) if n*2 DP[n]+1: DP[n*2] = DP[n]+1 last[n*2] = n dq.append(n*2) if n+1 DP[n]+1: DP[n+1] = DP[n]+1 last[n+1] = n dq.append(n+1) print(DP[N]) while 1: ..
[백준 1918번] 후위 표기식 (Python3) import sys input = sys.stdin.readline from collections import deque eq = input().strip() N = len(eq) stack = deque() symbol = deque() co = deque() def postfix(n): global x if n == N: if symbol: stack.append(symbol.pop()) return if eq[n] == "(": symbol.append("(") postfix(n+1) postfix(co.pop()) return elif eq[n] == ")": s = symbol.pop() if s != "(": stack.append(s) symbol.pop() if symbol: if symb..
[백준 13172번] Σ (Python3) import sys input = sys.stdin.readline MOD = 1000000007 M = int(input()) def cal(N,x): if x == 1: return N v = cal(N,x//2) if x%2 == 0: return v*v%MOD else: return v*v*N%MOD count = 0 for i in range(M): N,S = map(int,input().split()) rN = cal(N,MOD-2) count = (count + rN*S%MOD)%MOD print(count) 지문을 읽다가 멀미나는 문제 mod는 대체 뭐고 모듈러는 뭔데 모듈러 역원이 튀어나오더니 페르마의 소정리 어쩌고 저쩌고 하는데 정말 읽다가 어지러워진다. 지문 읽기가 싫어서 며칠을 묵혀..
[백준 2263번] 트리의 순회 (Python3) 트리 문제는 언제 풀어도 어려운 것 같다. 전위순회 중위순회 후위순회 뭔 어려운 말들이 많은지... 그래도 지난번에 이진 검색 트리 문제를 풀었기에 그때의 기억을 살려서 풀 수 있었다. 가장 중요한 포인트는 인오더와 포스트오더 둘다 왼쪽 트리를 먼저 순회한다는 점, 그리고 포스트오더의 가장 마지막 지점이 부모노드라는 점, 그리고 인오더는 부모노드를 기준으로 왼쪽트리와 오른쪽트리로 나누어진다는 점이다. 따라서 포스트오더의 마지막 값인 부모노드가 인오더에서 위치한 지점을 찾고, 그 점을 기준으로 리스트를 둘로 나누어 재귀함수를 돌아주면 된다. 애먹었던 부분은 리스트를 나누어 주다가 리스트의 길이가 0 또는 1이 될 때 어떻게 처리해주어야 할지였는데, 0일때는 return, 1일때는 값을 추가하고 return..
[백준 11444번] 피보나치 수 6 (Python3) 문제의 압도적인 n의 제한범위 (n은 1,000,000,000,000,000,000보다 작거나 같은 자연수)를 보자마자 분할정복 거듭제곱으로 푸는거구나 를 깨닫긴 했는데, 어떻게 풀어야 할지 막막했다. 그렇게 끄적끄적 고민하다가 놀라운 사실을 발견했는데, 바로 피보나치 수가 피보나치 수를 피보나치 수의 곱으로 나타낼 수 있다는 것이었다. 발견하게된 이유는 3은 1+2인데, 5는 2+3이다. 그런데 5는 2+(1+2)이므로 1이 1번 2가 2번 쓰인다. 8은 5+3이므로 2+3+3이고, 이는 2+(1+2)+(1+2) 이다. 2가 3번, 1이 2번 쓰인다. 규칙이 보이지 않는가? 작은 숫자들의 개수도 똑같이 피보나치 수열인 것이다. 이 규칙을 이용해 조금 만지다 보면 이런 식을 발견할 수 있다. n이 홀수일..
[백준 1167번] 트리의 지름 (Python3) import sys input = sys.stdin.readline from collections import deque import heapq INF = sys.maxsize N = int(input()) graph = [[] for i in range(N+1)] for i in range(N): data = list(map(int,input().split())) for j in range(1,len(data)-1): if j%2 == 0: continue graph[data[0]].append((data[j],data[j+1])) hq = [] distance = [[-INF]*(N+1) for i in range(2)] def Dijkstra(node,distance): heapq.heappush(..
[백준 11779번] 최소비용 구하기 2 (Python3) import sys input = sys.stdin.readline from collections import deque import heapq INF = sys.maxsize N = int(input()) M = int(input()) graph = [[] for i in range(N+1)] money = [INF]*(N+1) route = [[] for i in range(N+1)] for i in range(M): x1,x2,w = map(int,input().split()) graph[x1].append((x2,w)) start,goal = map(int,input().split()) hq = [] heapq.heappush(hq,(0,start,0)) while hq: w,x,last = he..

티스토리툴바