본문 바로가기

분류 전체보기

 (172)
[알고리즘] 백준 11053 가장 긴 증가하는 부분수열 / python https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net n = int(input()) arr = list(map(int, input().split(' '))) dp = [1] * n for i in range(1, n): for j in range(0, i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j]+1) print..
[알고리즘] 백준 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)..

티스토리툴바