알고리즘

괄호의 값 [백준 2504] - python

import sys input = sys.stdin.readline def BOJ2504() : def is_good(args) : stack = [] flag = True for arg in args : if arg == '(' : stack.append('(') if arg == ')' : if not stack: flag = False break if stack[-1] != '(' : flag = False break stack.pop() if arg == '[' : stack.append('[') if arg == ']' : if not stack : flag = False break if stack[-1] != '[': flag = False break stack.pop() if len(stac..

별자리 만들기 [백준 4386] - python

import math import heapq import sys input = sys.stdin.readline def BOJ4386() : def get_dist(x1, y1, x2, y2) : return math.sqrt(math.pow(x1-x2, 2) + math.pow(y1-y2, 2)) n = int(input()) stars = [] for _ in range(n) : stars.append(list(map(float, input().split()))) graph = [[] for _ in range(n+1)] visited = [False for _ in range(n+1)] for i in range(len(stars)) : for j in range(i+1, len(stars)) : ..

전기가 부족해 [백준 10423] - python

import sys input = sys.stdin.readline def BOJ10423() : N, M, K = map(int, input().split()) plants = list(map(int, input().split())) graph = [] parent = [i for i in range(N+1)] for _ in range(M) : graph.append(list(map(int, input().split()))) graph.sort(key = lambda x : x[2]) def find_parent(x) : if parent[x] == x : return x y = find_parent(parent[x]) parent[x] = y return y def union_parent(paren..

stack 두개로 queue 만들기

stack 두개로 queue를 구현하는 법입니다. class Queue: def __init__(self) : self.main = [] self.temp = [] def isEmpty(self, array): return len(array) == 0 def enqueue(self, value) : self.main.append(value) def dequeue(self) : if self.isEmpty(self.temp) : while self.main : self.temp.append(self.main.pop()) return self.temp.pop() # while self.main : # self.temp.append(self.main.pop()) # value = self.temp.pop() ..

도시 분할 계획 [백준 1647] - python

import sys import heapq input = sys.stdin.readline def BOJ1647() : N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] visited = [False for _ in range(N+1)] for _ in range(M) : A, B, C = map(int, input().split()) graph[A].append([C, B]) graph[B].append([C, A]) def prim() : result = [] queue = [] queue.append((0, 1)) while queue : curr_cost, curr_node = heapq.heappop(queue) if visit..

최소 스패닝 트리 [백준 1197] - python

# 크루스칼 알고리즘 import sys import heapq input = sys.stdin.readline def BOJ1197() : V, E = map(int, input().split()) parent = [i for i in range(V+1)] l = [] def find_parent(x) : if parent[x] == x : return x else : y = find_parent(parent[x]) parent[x] = y return y def union_parent(a, b) : parent_a = find_parent(a) parent_b = find_parent(b) if parent_a > parent_b : parent[parent_b] = parent_a else : pa..

네트워크 연결 [백준 1922] - python

import sys input = sys.stdin.readline def BOJ1922() : N = int(input()) M = int(input()) # 각 node에서 처음 부모는 자신 node들 입니다 parent = [i for i in range(N+1)] def find_parent(x): if (x == parent[x]): return x else: y = find_parent(parent[x]) parent[x] = y return y def union_parent(a, b) : parent_a = find_parent(a) parent_b = find_parent(b) if parent_a > parent_b : parent[parent_b] = parent_a else : par..

동전 1 [백준 2293] - python

import sys input = sys.stdin.readline def BOJ2293() : n, k = map(int, input().split()) l = [] for _ in range(n) : l.append(int(input())) dp = [0 for _ in range(k+1)] dp[0] = 1 for i in l : for j in range(1, k+1) : if j - i >= 0 : dp[j] += dp[j-i] print(dp[-1]) BOJ2293() 접근방법 : 1. dp 배열은 가치별 경우의 수를 나타낸다 ex) dp[10]은 주어진 동전들을 이용하여 10을 만들 수 있는 경우의 수 1, 2, 5을 예로 들면 6의 가치를 만드는 방법은 5를 구성했던 경우의 수에서 1을 하..

양팔저울 [백준 2629] - python

import sys input = sys.stdin.readline def BOJ2629() : n = int(input()) weight = list(map(int, input().split())) input() need_check = list(map(int, input().split())) dp = [[0 for _ in range(40001)] for _ in range(n)] dp[0][weight[0]] = 1 for i in range(1, n) : dp[i][weight[i]] = 1 for j in range(40001) : if dp[i-1][j] == 1 : dp[i][j] = 1 dp[i][j + weight[i]] = 1 dp[i][abs(j - weight[i])] = 1 for ..

전깃줄 [백준 2565] - python

import sys input = sys.stdin.readline def BOJ2565() : n = int(input()) l = [] for _ in range(n) : l.append(list(map(int, input().split()))) l.sort() dp = [1 for _ in range(n)] for i in range(n) : for j in range(i) : if l[j][1] < l[i][1] : dp[i] = max(dp[i], dp[j] + 1) print(n - max(dp)) BOJ2565() 접근방법 : 1. A 배열을 기준으로 정렬을 해준다. 예시입력에서는 1 8 2 2 3 9 4 1 6 4 7 6 9 7 10 10 과 같이 정렬이 될것이다. 2. B 배열을 기준으로..