문제링크: [백준] 13306번 트리 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 1. 문제 요약 트리구조에서 부모정점에 대한 정보와 연결경로를 묻는 문제인데요. 집합의 대표요소와 부모정점 비슷한 말 같지않나요? 저번 자료구조 포스팅에서 다뤘던 디스조인트 자료구조와 유니온 파인드 연산을 이용하여 푸는 문제였습니다. N개의 정점이 숫자 1부터 N까지로 표현되고 루트는 항상 1입니다. 트리의 정점 개수 N, 질의의 개수 Q가 주어지고 2번정점 부터 N번 정점까지 부모정점을 나타내는 정수 ..

문제링크 : [백준] 11377번: 열혈강호 3 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 1. 문제 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서..

문제 링크: [백준] 9576번: 책 나눠주기 20년의 마지막 주말 잘 보내셨나요? 연말에 즐거운 시간 보내시고 술은 적당히 먹는게 좋겠습니다.. 같이 문제 풀어볼까요?. 문제백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른..

문제 링크: [백준] 2470번: 두 용액 항상 이분탐색과 upper_bound, lower_bound를 사용할 때면 헷갈리는 것 같습니다. 블로그에 한번 정리를 해야겠다는 생각이 드네요. 같이 문제 풀어봅시다! 문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액..

문제 링크: [백준] 1644번: 소수의 연속합 오늘도 꾸준히 알고리즘을 공부해봅시다! 매일 꾸준히 조금씩 풀다 보면 저도 언젠가 잘해지지 않을까요? 며칠 안 남은 20년, 더욱 힘내봅시다! 문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7..

해당 글은 마이구미님의 글과 위키백과를 참고하며 스스로 공부한 내용을 정리한 것입니다. Disjoint-Set을 같이 공부해봅시다! Disjoint(서로소) Set(집합)는 많은 서로소 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다. 이러한 특징으로 인해 Disjoint Set은 파티션(partitioning) 문제에 주로 이용됩니다. Disjoint Set 자료구조에는 3가지의 중요한 연산이 존재합니다. 서로소 집합이란? 공통 원소가 없는 두 집합, 교집합이 공집합인 집합입니다. 연산 메이크 셋 (MakeSet): 말 그대로 특정 한 원소만을 가지는 집합(들)을 만드는 것입니다. 파인드 (Find): 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환 합니다. 일반적으로 해..