문제링크: [백준] 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..

방향성이 없는 그래프에서 1번 정점에서 N번 정점으로 가되 반드시 V1,V2 정점을 지나는 최단 거리를 구하는 문제였습니다.출발 지점과 도착지점은 1번 정점과 N번 정점으로 고정되어 있으므로 1 - V1 - V2 - N 1 - V2 - V1 - N 이 두 가지 경우만 체크하면 문제에서 요구하는 최단 거리를 구할 수 있습니다. 정점과 간선의 최대 개수를 감안하여 시간 복잡도 O(|V|*log|E|)인 다익스트라 알고리즘을 사용했습니다. 그래프는 이중벡터를 사용해 인접리스트 형태로 구현했고 최단거리의 합이 가능한 최대값을 넘거나 INF의 합으로 인해 오버플로우 될 경우를 생각하여 조건문을 작성했습니다. #include using namespace std; typedef pair pii; const int M..