본문 바로가기

분류 전체보기

 (145)
백준 23792 - K번째 음식 찾기 2 (C++) 문제 문제 링크 BOJ 23792 - K번째 음식 찾기 2 문제 요약 $x$ $y$ $z$ $k$ : 한식 $[1..x]$, 양식 $[1..y]$, 중식 $[1..z]$ 중에 $k$번째로 맛있는 음식 $?$ 한식, 양식, 중식 각각 $N$개의 음식에 대한 맛이 주어진다. 위의 쿼리가 $Q$개 주어질 때, 각각에 맞는 답을 출력하자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ A_x, B_y, C_z ≤ 2^{31} - 1$ $3N$개 음식의 맛은 모두 서로 다르다. 알고리즘 분류 이분 탐색(binary search) 매개 변수 탐색(parametric search) 풀이 K번째 음식 찾기 1 을 처음 보고 무지성 $merge$-$sort$ $tree$..
백준 13038 - Tree (C++) 문제 문제 링크 BOJ 13038 - Tree 문제 요약 $1$ $x$ $y$ : 정점 $x$부터 정점 $y$까지 이르는 경로의 길이를 출력한다. $2$ $x$ : 정점 $x$를 제거한다. 이때, 정점 $x$의 자식들은 $x$의 부모 정점으로 전이된다. $N$개의 정점으로 이루어진 트리와 위와 같은 $Q$개의 쿼리가 주어진다. $1$번 쿼리가 주어질 때마다 그에 맞는 답을 출력하자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^6$ 반드시 올바른 트리가 입력으로 주어지며, 트리의 루트$(1)$는 제거되지 않음이 보장된다. 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할 (heavy-light decomposition..
백준 28425 - 점수 계산하기 (C++) 문제 문제 링크 BOJ 28425 - 점수 계산하기 문제 요약 $r$ $v$ $:$ $r$번 노드가 루트일 때 $v$번 직원의 점수$?$ $N$개의 노드로 이루어진 트리와, 위 내용의 $Q$개의 쿼리가 주어진다. 각 쿼리에 맞는 답을 계산하여 출력하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 10^5$ $0 ≤ score ≤ 10^4$ 알고리즘 분류 트리(trees) 다이나믹 프로그래밍(dp) 트리에서의 다이나믹 프로그래밍(dp_tree) 최소 공통 조상(lowest common ancestor) 풀이 쿼리 없이 루트 노드를 $1$로 잡고 정적인 상태에서의 답을 계산해보자. 이는 트리$DP$로 간단히 계산할 수 있다. $dp[i] :$ $i$번 노드를 루트로 하는 ..
백준 28421 - 곱하기와 쿼리 (C++) 문제 문제 링크 BOJ 28421 - 곱하기와 쿼리 문제 요약 $1$ $x$ : 수열에서 서로 다른 두 수 $A_i, A_j$를 곱하여 $x$를 만들 수 있으면 $1$, 없으면 $0$을 출력한다. $2$ $i$ : $A_i$를 $0$으로 바꾼다. 길이 $N$의 수열과 위의 두 유형으로 이루어진 $q$개의 쿼리가 주어진다. $1$번 쿼리가 주어질 때마다 그에 맞는 답을 출력하자. 제한 TL : $1.5$ sec, ML : $1024$ MB $0 ≤ x ≤ 10^8$ $1 ≤ N ≤ 10^5$ $1 ≤ A_i ≤ 10^4$ $1 ≤ Q ≤ 5*10^3$ 알고리즘 분류 수학(math) 정수론(number_theory) 풀이 $1$번 쿼리가 주어질 때마다 $x$를 인수 분해한다고 생각해보자. 이때 여러 인수 쌍..
백준 28277 - 뭉쳐야 산다 (C++) 문제 문제 링크 BOJ 28277 - 뭉쳐야 산다 문제 요약 $N$개의 집합 $S_1, S_2,$ $...$ $S_N$이 주어질 때, 두 종류로 이루어진 $Q$개의 쿼리를 처리하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 500,000$ $1 ≤ ΣN_i ≤ 500,000$ $1 ≤ S_{i,j} ≤ 1,000,000,000$ 알고리즘 분류 자료 구조(data_structures) 트리를 사용한 집합과 맵(tree _ set / map) 작은 집합에서 큰 집합으로 합치는 테크닉(small_to_large) 풀이 $Small$_$To$_$Large$ 테크닉 그 자체인 문제이다. 최근에 만들어진 문제라 솔브수가 적어서 그렇지, 머지 않아 위 테크닉의 대표 예제로 꼽힐 ..
백준 4787 - Covered Walkway (C++) 문제 문제 링크 BOJ 4787 - Covered Walkway 문제 요약 커버해야 하는 $n$개의 지점과 상수 $c$가 주어진다. 지점 $[x, y]$를 커버한다면 $c + (y - x)^2$의 비용이 발생할 때, 모든 지점을 커버하는 최소 비용을 구해보자. 제한 TL : $10$ sec, ML : $128$ MB $1 ≤ n ≤ 10^6$ $1 ≤ c, n_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex-hull trick) 풀이 우선 나이브하게 접근해보자. $dp[i] :$ 첫번째 지점부터 $i$번째 지점까지 커버하는 데에 드는 최소 비용. 임의의 지점 $V_i$와 $1 ≤ j ≤ i$인 $V_j$에 대해 $dp[i] = min((V[i] - V[j..
백준 28426 - 더하기와 나누기 (C++) 문제 문제 링크 BOJ 28426 - 더하기와 나누기 문제 요약 수열의 원소는 모두 다르고 $2$ 이상 $10^6$ 이하의 정수이다. $1$ 이상 $N$ 이하의 모든 정수 $i$에 대해서, $A_i$가 $A_1 + A_2 + ... + A_N$의 약수가 되는 정수 $i$는 정확히 $1$개이다. $N$이 주어지면, 위 조건을 만족하는 수열을 아무거나 하나 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ 알고리즘 분류 해 구성하기 (constructive) 풀이 홀수와 짝수에 집중해보면 된다. $N-1$개의 짝수와, $1$개의 홀수로 수열을 구성하는 것을 생각하자. 홀수의 기준을 $3$으로 잡으면, 다음과 같이 진행되는 수열을 만들어 볼 수 있다. $3$ $2$..
백준 28422 - XOR 카드 게임 (C++) 문제 문제 링크 BOJ 28422 - XOR 카드 게임 문제 요약 $1.$ 한 번에 가져가는 카드들에 적혀있는 번호를 $XOR$ 연산한다. $2.$ $1$에서 구한 값을 이진수로 변환했을 때, $1$의 개수만큼 점수를 획득한다. $N$장의 카드 더미가 위에서부터 주어진다. 위 획득 기준으로 카드를 두 장 혹은 세 장씩 가져갈 때, 획득할 수 있는 최고 점수를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ $2^0 ≤ A_i ≤ 2^{10}$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 간단한 $dp$ 문제이다. $dp[i] :$ 지금까지 $i$장의 카드를 가져갔을 때, 이후 획득할 수 있는 최고 점수. 문제에서 제시하는 분기 방향 그대로, 임의의 $i$에..

티스토리툴바