이것저것 기록 블로그

뭐야 문제가 무슨 뜻인지 알기 어려웠던 문제..ㅎ stack에 1부터 차례로 넣을 수 있고, 주어진 수열을 만들기 위해 push, pop 해야하는 경우를 +,-로 표현하는 것이었다. 즉, 예제를 보면 8 4 3 6 8 7 5 2 1 주어진 수는 8개이고 4, 3, 6, 8, 7, 5, 2, 1 순으로 stack에서 pop해야한다. 즉, 4를 뽑기 위해선, 1, 2, 3, 4를 stack에 push하고 pop을 해야한다. (push 4번, pop 1번) 그다음, 3을 뽑기 위해선 바로 pop을 하면 된다. 현재 stack의 상태가 1, 2, 3 이었으므로. 그 다음 6을 뽑기 위해선, 5, 6을 stack에 추가로 Push해주고 pop을 해야한다. 이런식으로 pop 해서 주어진 수열을 만드는 문제였다. 문..

while True: stack = [] sentence = str(input()) count = 0 if sentence == '.': break for char in sentence: count = count + 1 if char == '(': stack.append(char) elif char == '[': stack.append(char) elif char == ')': if stack and stack[-1] == '(': stack.pop() else: break elif char == ']': if stack and stack[-1] == '[': stack.pop() else: break if len(stack) == 0 and count == len(sentence): print("yes..

n = int(input()) case = [] for _ in range(n): case.append(int(input())) d = [[] for _ in range(max(case)+1)] d[0] = [1, 0] d[1] = [0, 1] for i in range(2, len(d)): d[i] = [d[i-2][0] + d[i-1][0], d[i-2][1] + d[i-1][1]] for i in case: print(d[i][0], d[i][1])

import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [] visited = [[0 for _ in range(m)] for _ in range(n)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for _ in range(n): graph.append(list(map(int, input().split()))) def dfs(y, x, count): if visited[y][x] == 0: visited[y][x] = 1 if graph[y][x] != 0: graph[y][x] = count for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

[나중에 다시 풀기] 그냥 하던대로 거리 구해서 모든 간선을 추가하면 메모리 초과가 난다. from itertools import combinations import sys input = sys.stdin.readline n = int(input()) xyz_ = [[0,0,0]] for _ in range(n): xyz_.append(list(map(int, input().split()))) pair_ = list(combinations([i for i in range(1, n+1)], 2)) edges = [] answer = 0 parent = [0] * (n+1) for i in range(1, n+1): parent[i] = i def distance(a, b): return min(abs(a[..

바로 앞 문제인 별자리만들기와 같은 방식이다. https://happy-dohee.tistory.com/170 [백준] 4386번 별자리 만들기 얘는 직접 간선의 가중치를 만들어줘야 하는 문제. 각 정점을 1, 2, 3, ... 번 정점이라고 생각하고 그 둘을 잇는 거리를 구해서 다른 문제들과 마찬가지로 (정점1, 정점2, 가중치) 형태로 간선을 저 happy-dohee.tistory.com 다만 다른 한가지 점은, 이미 두 점이 연결된 간선이 이미 하나 이상 존재한다는 것. 이는 최소신장트리를 만드는 과정을 하기 전에, 미리 직접 연결시켜주면 된다. union_node 함수 이용. from itertools import combinations n, m = map(int, input().split()) ..

얘는 직접 간선의 가중치를 만들어줘야 하는 문제. 각 정점을 1, 2, 3, ... 번 정점이라고 생각하고 그 둘을 잇는 거리를 구해서 다른 문제들과 마찬가지로 (정점1, 정점2, 가중치) 형태로 간선을 저장한 다음에 일반적인 최소신장트리 풀 듯 풀면 된다. from itertools import combinations import sys input = sys.stdin.readline n = int(input()) edges = [] parent = [0] * (n+1) for i in range(1, n+1): parent[i] = i xy_ = [[0, 0]] for _ in range(n): x, y = map(float, input().split()) xy_.append([x, y]) # par..

n, m = map(int, input().split()) edges = [] parent = [0] * (n+1) def find_parent(x): if parent[x] != x: parent[x] = find_parent(parent[x]) return parent[x] def union_node(a, b): a = find_parent(a) b = find_parent(b) if a < b: parent[b] = a else: parent[a] = b for i in range(1, n+1): parent[i] = i for _ in range(m): a, b, c = map(int, input().split()) edges.append((a, b, c)) edges = sorted(edges,..

최소신장트리를 연습하기 위한 좋은 문제. 최소신장트리는 크루스칼 알고리즘으로 보통 이어지지만. 이는 간선에 비용이 없음. 단순한 최소신장트리를 구하면 된다. T = int(input()) import sys input = sys.stdin.readline for _ in range(T): n, m = map(int, input().split()) # Initiate a parent table parent = [0] * (n + 1) for i in range(1, n+1): parent[i] = i edges = [] for _ in range(m): a, b = map(int, input().split()) edges.append((a, b)) def find_parent(x): if parent[x]..

플로이드-워셜 알고리즘의 전형적인 예제 마지막 출력에 길 없으면 0 출력한다 구현하는 걸 잊지 말아야한다. 채점 진짜 오래걸렸다. 5분 걸림... 왜지? n = int(input()) m = int(input()) INF = int(1e9) graph = [[INF] * (n+1) for _ in range(n+1)] for _ in range(m): a, b, c = map(int, input().split()) graph[a][b] = min(graph[a][b], c) for i in range(n+1): for j in range(n+1): if i == j: graph[i][j] = 0 for k in range(n+1): for a in range(n+1): for b in range(n+1)..