알고리즘 (138) 썸네일형 리스트형 [알고리즘] 백준 12865 평범한 배낭 / python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 전형적인 DP문제! 이해하느라 애먹었다 ㅠ D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치 점화식으로 표현하면, D[i][j] = D[i - 1][j] ( j < w ) D[i][j] = max( D[i - 1][j], D[i - 1][j - w].. [알고리즘] 백준 1904 01타일 / python n = int(input()) _list = [0] * n _list[0] = 1 _list[1] = 2 for i in range(2, n): _list[i] = (_list[i-1] + _list[i-2]) % 15746 print(_list[n-1]) DP문제는 점화식을 세우자 f(n) = f(n-1) + f(n-2) [알고리즘] 백준 1766 문제집 / 위상정렬, python import heapq n, m = map(int, input().split(' ')) num_list = [ [] for _ in range(n+1) ] indegree = [ 0 for _ in range(n+1) ] heap = [] result = [] for _ in range(m): a, b = map(int, input().split(' ')) num_list[a].append(b) indegree[b] += 1 for i in range(1, n+1): if indegree[i] == 0: heapq.heappush(heap, i) while heap: temp = heapq.heappop(heap) result.append(temp) for i in num_list[temp]: indeg.. [알고리즘] 백준 1715 카드정렬하기 / python import heapq n = int(input()) heap = [] for _ in range(n): num = int(input()) heapq.heappush(heap, num) result = 0 while len(heap) != 1: num1 = heapq.heappop(heap) num2 = heapq.heappop(heap) _sum = num1 + num2 result += _sum heapq.heappush(heap, _sum) print(result) 제일 작은 수끼리 비교할수록 최소가 되므로 최소힙을 이용한다 [알고리즘] 백준 1927 최소힙 / python import heapq import sys n = int(input()) h = [] for _ in range(n): num = int(sys.stdin.readline()) if num == 0: if not h: print(0) else: print(heapq.heappop(h)) else: heapq.heappush(h, num) heapq라이브러리를 이용해 힙을 구현 import heapq heapq.heappush(heap, item) heapq.heappop(heap) 시간초과 당해서 sys.stdin.readline()으로 바꿔씀! [알고리즘] 백준 1991 트리순회 / python class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node def pre_order(node): print(node.data, end='') if node.left_node != '.': pre_order(tree[node.left_node]) if node.right_node != '.': pre_order(tree[node.right_node]) def in_order(node): if node.left_node != '.': in_order(tree[node.left_node]) print(node.data, end=''.. [알고리즘] 백준 1939 중량제한 / python from collections import deque n, m = map(int, input().split(' ')) def bfs(c): queue = deque() queue.append(start) visited = [False] * (n+1) visited[start] = True while queue: x = queue.popleft() for y, weight in adj[x]: if not visited[y] and weight >= c: queue.append(y) visited[y] = True return visited[end] adj = [ [] for _ in range(n+1) ] max_weight = 1 min_weight = 1000000000 for _ in range(m).. [알고리즘] 이진 탐색 (Binary Search) 이진 탐색 이란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 오름차순으로 정렬되어 있어야 한다 파이썬 코드 구현 def binary_search(data, search): print(data) if len(data) == 1 and search == data[0]: return True if len(data) == 1 and search != data[0]: return False if len(data) == 0: return False medium = len(data) // 2 if search == data[medium]: return True else: if search > data[medium]: return binary_search(data[medium+1:], sea.. 이전 1 ··· 11 12 13 14 15 16 17 18 다음
