본문 바로가기

분류 전체보기

 (145)
백준 28082 - 기계오리 연구 (C++) 문제 문제 링크 BOJ 28082 - 기계오리 연구 문제 요약 배터리 $N$개와 장착할 수 있는 최대 배터리 개수 $K$, 각 배터리의 전력량이 주어진다. $K$개를 넘지 않는 배터리들을 적절히 조합하여 전력량을 표현할 때, 표현 가능한 종류를 모두 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, I_i ≤ 500$ $1 ≤ K ≤ min(N, 100)$ 알고리즘 분류 다이나믹 프로그래밍(dp) 배낭 문제(knapsack) 풀이 각 배터리의 포함 유무로 표현할 수 있는 전력량의 모든 경우를 구해야 한다. 문제의 제한을 보면, 표현할 수 있는 최대 전력량은 $500 * 100 = 50,000$ 이다. 이는 결국 각 배터리가 $1$개임에 따라, 뒤에서부터 보는 $1$차원 $..
백준 17831 - 대기업 승범이네 (C++) 문제 문제 링크 BOJ 17831 - 대기업 승범이네 문제 요약 트리 형태의 회사 구조와, 각 직원의 실력 정보가 주어진다. 사수 - 부사수 관계에 놓인 직원들끼리 적절히 묶어 멘토링 관계를 만들어 줄 때, 모든 멘토링 관계에서 발생하는 시너지 합의 최댓값을 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $2 ≤ N ≤ 200,000$ $0 ≤ A_i ≤ 100$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 직접적인 사수 - 부사수 관계에서만 멘토링 관계의 여부를 따질 수 있으므로, 임의의 노드(직원) $p$가 가질 수 있는 상태는 둘 중 하나다. 부모 노드(사수)와 멘토링 관계에 놓인 경우 $(q = 1)$ 부모 노드..
백준 27892 - 특별한 큰 분수 (C++) 문제 문제 링크 BOJ 27892 - 특별한 큰 분수 문제 요약 분수의 $0$초일 때 높이가 주어진다. 문제에 정의된 규칙을 따라 높이가 변화할 때, $N$초에서의 분수의 높이를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $0 ≤ x_0, N ≤ 10^{18}$ 알고리즘 분류 수학(math) 자료 구조(data structures) 해시를 사용한 집합과 맵(hash _ set / map) 풀이 브루트포스로 이런저런 $x_0$에 대해 $N=1,000$으로 잡고 그 변화를 출력해 보니, 한가지 사실을 관찰할 수 있었다. 모든 수들이 빠른 속도로 감소 하다가 임의의 사이클로 수렴 하게 되는 것이었다. 그렇게 믿음을 갖고 제출해 $AC$를 받았다. 엄밀한 풀이는 에디토리얼 을 참고하자. ..
백준 21695 - Школа танцев (C++) 문제 문제 링크 BOJ 21695 - Школа танцев 문제 요약 남학생, 여학생이 구분 없이 일렬로 서있다. 남학생과 여학생의 수가 같은 부분 일렬의 수를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N ≤ 10^6$ 알고리즘 분류 자료 구조(data structures) 해시를 사용한 집합과 맵(hash _ set / map) 누적 합(prefix_sum) 풀이 두 가지의 상태가 동일한 비율인 연속 부분 수열의 개수를 세야 한다. 결국 $a = 1, b = -1$ 로 가중치를 메길 때, 이 문제 에서 $K = 0$ 일 때로 환원 시킬 수 있다. 전체 코드 123456789101112131415161718#include#define ll long longusing n..
백준 4966 - Cards (C++) 문제 문제 링크 BOJ 4966 - Cards 문제 요약 $N$개의 카드 집합과 $M$개의 카드 집합이 주어진다. 주어진 규칙에 따라 카드 쌍을 제거하려 할 때, 카드 쌍이 가장 많이 제거되는 경우를 찾아보자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, M ≤ 500$ $2 ≤ N_i, M_i ≤ 10^7$ 알고리즘 분류 수학(math) 정수론(number_theory) 유클리드 호제법(euclidean) 이분 매칭(bipartite_matching) 풀이 $gcd(x, y) > 1$ 인 카드끼리 사이 좋게 제거할 수 있을 때, 가장 많이 제거 되도록 하는 경우를 찾으라고 한다. 파란색 카드 집합과 빨간색 카드 집합, 서로를 향해 간선을 세팅할 수 있고 $1 ≤ N, M ≤ 5..
백준 26159 - 트리와 수열 (C++) 문제 문제 링크 BOJ 26159 - 트리와 수열 문제 요약 $N$개의 정점으로 이루어진 트리와 $N - 1$개의 수열이 주어진다. 간선에 수열의 원소들을 하나씩 대응시켜 가중치를 매길 때, $min(Σdist(i, j))$ $mod$ $1000000007$ 의 값을 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $1 ≤ a_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리(trees) 다이나믹 프로그래밍(dp) 트리에서의 다이나믹 프로그래밍(dp_tree) 그리디 알고리즘(greedy) 정렬(sorting) 풀이 척 보면 드는 생각이, "가장 인기 없는 간선일수록 큰 가중치를 부여 하는 것이 이..
백준 25498 - 핸들 뭘로 하지 (C++) 문제 문제 링크 BOJ 25498 - 핸들 뭘로 하지 문제 요약 정점마다 알파벳이 메겨진 트리가 주어진다. 문제의 정의데로 알파벳을 이어 붙일 때, 사전상 가장 마지막에 오는 문자열을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ 알파벳은 소문자만 등장한다. 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 트리(trees) 그리디 알고리즘(greedy) 풀이 $N$이 작았다면 모든 리프 노드에서 답을 갱신해도 됐을 테지만, $N ≤ 500,000$ 이므로 풀이를 개선해야 한다. 다음을 관찰하자. 루트에서 임의의 깊이까지 서로 다른 경로를 통해 나열되는 문자열들의 길이는 모두 같다. 깊이가 같..
백준 15060 - Imperial roads (C++) 문제 문제 링크 BOJ 15060 - Imperial roads 문제 요약 $N$개의 정점으로 이루어진 그래프가 주어진다. $Q$개의 쿼리로 정점 쌍들이 주어지는데, 이 정점 쌍을 직접적으로 잇는 간선을 포함한 $MST$의 비용을 출력하자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $N − 1 ≤ R ≤ 2 * 10^5$ 알고리즘 분류 그래프 이론(graphs) 트리(trees) 최소 스패닝 트리(minimum spanning tree) 최소 공통 조상(lowest common ancestor) 풀이 주어진 그래프에 대해, 최소 비용만을 따진 채 모든 정점을 연결 시켜야 하므로 우선 $MST$를 구축해보자. $(G)$ 이제 $G$에 임의의 정점 쌍 $(i, j)..

티스토리툴바