알고리즘7 [백준][파이썬]2805번: 나무 자르기 문제 출처 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 내 풀이 import sys input = sys.stdin.readline n, m = map(int, input().split()) high = list(map(int, input().split())) start = 0 end = max(high) while start 0 else 0 for i in high) if cnt < m: end .. 2021. 6. 1. [백준][파이썬]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. [백준][파이썬]9625번: BABBA 문제 출처 : https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 내 풀이 n = int(input()) a = [1] b = [0] for i in range(n): a.append(b[i]) b.append(b[i] + a[i]) print(a[-1], end = ' ') print(b[-1]) 설명 조건을 보면 B -> BA, A -> B로 바뀐다. 이는 곧 a[i] 의 A의 개수는 a[i - 1]의 B의 개수 B의 개수는 (a[i - 1]의 A.. 2021. 5. 13. 이전 1 2 다음