https://www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net #내코드 from collections import deque n = int(input()) lst = list(map(int, input().split())) lst.sort() lst = deque(lst) while len(lst) > 1: first = lst.popleft() second = lst.pop() lst.append(first/2 + second) print(lst[0]) #..
코테/코딩테스트 대비 Python
def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b v, e = map(int, input().split()) parent = [0] * (v+1) for i in range(1, v + 1): parent[i] = i for i in range(e): a, b = map(int, input().split()) union_parent(pa..
O(n3) INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF]*(n+1)for _ in range(n+1)] for a in range(1, n+1): for b in range(1, n+1): if a == b: graph[a][b] = 0 for _ in range(m): a,b,c = map(int, input().split()) graph[a][b] = c for k in range(1, n+1): for a in range(1, n+1): for b in range(1, n+1): graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
시간복잡도: O(ElogV) E: 간선, V: 노드 갯수 E
Dynamic Programming (동적 계획법) array = [5, 2, 1, 4, 3, 5] dp = [1 for _ in range(len(array))] for i in range(1, len(array)): for j in range(i): # array의 처음부터 i-1번째 인덱스까지 if array[i] > array[j]: # 숫자의 크기를 비교하여 현재 값이 더 크면 dp[i] = max(dp[i], dp[j] + 1) # dp 배열의 값을 더 큰 값으로 갱신 Binary Search (이분 탐색) from bisect import bisect_left array = [5, 2, 1, 4, 3, 5] dp = [1] x = [array[0]] for i in range(1, len(a..
