본문 바로가기

전체 글65

[백준][파이썬]1620번: 나는야 포켓몬 마스터 이다솜 문제 출처 : https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 내 풀이 import sys input = sys.stdin.readline n, m = map(int, input().split()) dict = {} for i in range(1, n + 1): a = input().rstrip() dict[i] = a dict[a] = i for i in range(m): quest = input().rstrip(.. 2021. 6. 1.
서로소 집합 서로소 집합 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다. 그래서 이를 union-find 자료구조라고도 한다. union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 서로소 집합 자료구조는 구현할 때 트리 자료구조를 이용하여 집합을 표현한다. 서로소 집합 계산 알고리즘은 다음과 같다. 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. -I. A와 B의 루트 노드 A', B'를 .. 2021. 5. 30.
[백준][파이썬]14496번: 그대, 그머가 되어 문제 출처 : https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 2021. 5. 18.
[백준][파이썬]18352번: 특정 거리의 도시 찾기 문제 출처 : https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 내 풀이 import sys import heapq input = sys.stdin.readline INF = int(1e9) n, m, k, x = map(int, input().split()) graph = [[] for i in range(n + 1)] distance = [INF] * (n + 1) ch.. 2021. 5. 18.

티스토리툴바