본문 바로가기

분류 전체보기

 (145)
백준 27519 - 소수의 합 (C++) 문제 문제 링크 BOJ 27519 - 소수의 합 문제 요약 함수 $f(n)$을 "$n$을 $0$개 이상의 소수의 합으로 표현하는 경우의 수" 라고 정의하자. $T$개의 $n$이 주어질 때, 각 $n$에 맞는 $f(n)$의 값을 출력해보자. 제한 TL : $3$ sec, ML : $128$ MB $1 ≤ T ≤ 10,000$ $0 ≤ n_i ≤ 100,000$ 알고리즘 분류 수학(math) 정수론(number_theory) 소수 판정(primality_test) 에라토스테네스의 체(sieve) 다이나믹 프로그래밍(dp) 풀이 웰노운스러운 유형 중 하나이다. $dp[n]$을 $f(n)$그대로 정의할 때, 소수들을 매개로 진행하는 $knapsack$ $problem$으로 바라볼 수 있다. $dp[0] = 1$..
백준 20132 - Parity Constraint Minimum Spanning Tree (C++) 문제 문제 링크 BOJ 20132 - Parity Constraint Minimum Spanning Tree 문제 요약 $N$개의 정점과 $M$개의 간선으로 이루어진 무향 그래프가 주어진다. 이 그래프의 스패닝 트리에서, 비용이 홀수인 최솟값과 짝수인 최솟값을 구헤보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $1 ≤ M ≤ 300,000$ $1 ≤ w_i ≤ 1,000,000,000$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 그래프 탐색(graph traversal) 최소 스패닝 트리(minimum spanning tree) 최소 공통 조상(lowest common ancestor) 희소 배열(sparse tabl..
백준 28090 - 특별한 한붓그리기 (C++) 문제 문제 링크 BOJ 28090 - 특별한 한붓그리기 문제 요약 각각 $N$개의 정점으로 구성된 집합 $A$, $B$가 있고, 두 집합은 이분 그래프의 형태로 연결되어 있다. 이제 뉴비와 고인물이 문제에 정의된 규칙대로 게임을 진행하려 한다. 서로 최선의 전략으로 게임을 진행할 때, 결국 승리하게 되는 쪽을 판단해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 450$ $1 ≤ L ≤ min(N^2, 2,000)$ 중복된 간선은 주어지지 않는다. 알고리즘 분류 게임 이론(game_theory) 최대 유량(maximum_flow) 이분 매칭(bipartite_matching) 풀이 뉴비가 선공을 함에 따라, 뉴비가 이길 수밖에 없는 상황을 생각해 보자. 이떤 정점 $A_i..
백준 28092 - 우선순위와 쿼리 (C++) 문제 문제 링크 BOJ 28092 - 우선순위와 쿼리 문제 요약 $N$개의 정점에 대해, 두 유형으로 이루어진 $Q$개의 쿼리를 처리하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 10^5$ 알고리즘 분류 자료 구조(data structures) 트리를 사용한 집합과 맵(tree _ set / map) 분리 집합(disjoint_set) 풀이 그래프끼리의 $Merge$를 빠르게 수행해야 한다. 나아가 각 그래프의 컴포턴트 개수도 관리해 주어야 한다. 이는 분리 집합을 이용해 간단하고 효율적으로 관리할 수 있다. 여기에 추가로, $2$번 쿼리의 조건을 만족하는 트리를 빠르게 구할 수 있어야 한다. 이는 삽입, 탐색, 삭제를 $O(logN)$ 수준으로 지원하는 $std:..
백준 28131 - K-지폐 (C++) 문제 문제 링크 BOJ 28131 - K-지폐 문제 요약 $N$개의 정점과 $M$개의 단방향 간선으로 이루어진 그래프가 주어진다. 정점 $S$에서 $T$까지 가려할 때, 이용료 합이 $K$의 배수이면서 최소가 되는 비용을 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $2 ≤ N ≤ 10,000$ $1 ≤ M ≤ min(100,000, N*(N-1))$ $1 ≤ w ≤ 1000$ $1 ≤ K ≤ 50$ 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 풀이 우선 가중치 있는 유향 그래프에서 최단 거리를 찾아야 하므로 다익스트라를 떠올려볼 수 있다. 이제 어떻게 총 비용이 $K$의 배수가 되게 하냐가 문제인데.. 알다시피 $S$부터 임의의 정점 $i$까지 도달하는 ..
백준 28127 - 숫자탑과 쿼리 (C++) 문제 문제 링크 BOJ 28127 - 숫자탑과 쿼리 문제 요약 $Q$개의 쿼리가 주어진다. 쿼리마다 탑을 쌓는 규칙이 함께 주어질 때, $x$가 적힌 숫자 블록이 몇 번째 층의 몇 번째 숫자인지 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ Q ≤ 500,000$ $1 ≤ a, d, x ≤ 1,000,000$ 알고리즘 분류 수학(math) 이분 탐색(binary_search) 풀이 쿼리마다 탑의 모양이 바뀐다. 즉, 주어지는 변수 $a, d$에 대해 일반화를 시켜야 한다. $A_i$를 $i$번째 층의 제일 왼 쪽에 있는 수라고 정의한 후 초항을 나열해보면, $A_1 = 1$ $A_2 = 1 + (a + d * 0)$ $A_3 = 1 + (a + d * 0) + (a + d ..
백준 25181 - Swap the elements (C++) 문제 문제 링크 BOJ 25181 - Swap the elements 문제 요약 길이 $N$의 수열 $A_n$이 주어진다. 이 수열에 대해, 서로 다른 두 원소를 골라 위치를 바꾸는 연산을 원하는 만큼 수행 후 수열 $B_n$을 만드려고 할 때, 모든 $B_i$에 대해 $A_i ≠ B_i$인 수열 $B_n$을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 5,000$ $1 ≤ A_i ≤ 100,000$ 알고리즘 분류 애드 혹(ad_hoc) 해 구성하기(constructive) 풀이 곰곰이 생각해보면, 수열 $B_n$을 만들 수 없는 조건은 쉽게 도출할 수 있다. 가장 많이 등장한 수를 $x$라 할 때, $count(x) > ⌊ {N \over 2} ⌋$ 라면 조건을 ..
백준 28071 - 승형이의 사탕 사기 (C++) 문제 문제 링크 BOJ 28071 - 승형이의 사탕 사기 문제 요약 $N$개의 사탕 상자에서 최대 $M$개의 사탕을 가져가려 한다. 고른 총 사탕 개수가 $K$로 나누어 떨어져야 할 때, 가져갈 수 있는 최대 사탕 개수를 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, M, K ≤ 300$ $1 ≤ N_i ≤ 300$ 알고리즘 분류 다이나믹 프로그래밍(dp) 배낭 문제(knapsack) 풀이 이 문제 역시 $knapsack$ $DP$로 쉽게 해결할 수 있다. 얼마 전 BOJ 28082 - 기계오리 연구 를 다룰 땐, 각 배터리가 $1$개임에 따라 (현재 시행이 현재 시행에 영향을 주지 않기 위해) 뒤에서부터 조사를 진행 했었다. 그러나 이번엔 각 사탕의 개수가 무한하기 ..

티스토리툴바