본문 바로가기

Problem Solving

 (145)
백준 1623 - 신년 파티 (C++) 문제 문제 링크 BOJ 1623 - 신년 파티 문제 요약 사장을 포함한 직원들의 정보가 트리 형태로 주어진다. 사장이 신년 파티에 포함 될 때 / 되지 않을 때 각각 "날라리 분위기"의 최댓값 및 그 과정을 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $2 ≤ N ≤ 200,000$ $N_i ≤ |10,000|$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 BOJ 27501 - RGB트리 BOJ 2213 - 트리의 독립집합 위 두 문제들이랑 별반 다를게 없다. 풀이 흐름 역시 동일하므로 간단하게만 적고 넘어 가겠다. $dp[p][q]$ : $p$번 사람을 루트로 하는 서브 트리에서, $p$번 사람의 신년 파티 참석 유..
백준 26077 - 서커스 나이트 (C++) 문제 문제 링크 BOJ 26077 - 서커스 나이트 문제 요약 돌고래 $N$마리의 $ID$가 주어진다. $2 ≤ gcd(i, j)$를 만족하는 돌고래들끼리만 메시지 전파가 가능할 때, 메시지를 전달받을 수 있는 돌고래 수의 최댓값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 1,000,000$ $2 ≤ N_{ID} ≤ 1,000,000$ 알고리즘 분류 수학(math) 정수론(number_theory) 자료 구조(data structures) 분리 집합(disjoint_set) 소수 판정(primality_test) 에라토스테네스의 체(sieve) 풀이 $N$의 범위를 보자. 모든 쌍을 돌아보며 $gcd()$를 돌려보면 큰일날 것 같다. 문제의 중요한 조건을 정리해..
백준 23840 - 두 단계 최단 경로 4 (C++) 문제 문제 링크 BOJ 23840 - 두 단계 최단 경로 4 문제 요약 $N$개의 정점으로 이루어진 그래프와 $P$개의 중간 정점이 주어진다. 출발 정점에서 $P$개의 중간 정점 모두를 거친 후 도착 정점에 도달하는 최단 거리를 구해보자. 제한 TL : $7$ sec, ML : $1024$ MB $10 ≤ N ≤ 100,000$ $10 ≤ M ≤ 300,000$ $1 ≤ w ≤ 1,000,000$ $3 ≤ P ≤ min(20, N - 3)$ 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 다이나믹 프로그래밍(dp) 비트필드를 이용한 다이나믹 프로그래밍(dp_bitfield) 비트마스킹(bitmask) 외판원 순회 문제(tsp) 풀이 출발 정점으로부터 $P$개의 정점을 모두 거친 후 ..
백준 26262 - 트리 더하기 1 (C++) 문제 문제 링크 BOJ 26262 - 트리 더하기 1 문제 요약 $N$개의 정점과 $N$개의 양방향 간선으로 이루어진 그래프가 주어진다. 순서쌍 $(x_i, y_i)$ 가 $Q$개 주어질 때, 각 쿼리마다 정점 $x_i$와 $y_i$를 잇는 최단 경로의 길이를 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $2 ≤ N ≤ 2 * 10^5$ $1 ≤ Q ≤ 2 * 10^5$ $1 ≤ d_i ≤ 10^9$ $i$ $≠$ $j$ 이고 $(u_i, v_i) = (u_j, v_j)$ 인 중복 간선이 입력으로 주어질 수 있다. 알고리즘 분류 그래프 이론(graphs) 트리(trees) 최소 공통 조상(lowest common ancestor) 누적 합(prefix_sum) 풀이 이 글 에서 한..
백준 28018 - 시간이 겹칠까? (C++) 문제 문제 링크 BOJ 28018 - 시간이 겹칠까? 문제 요약 학생 $N$명의 $S_i, E_i$가 주어진다. $Q$개의 쿼리에 대해 선택할 수 없는 좌석 수를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ S_i, E_i ≤ 10^6$ 알고리즘 분류 누적 합(prefix_sum) 풀이 이제 어느정도 웰노운 테크닉이 돼버린, $imos$법 기본 문제이다. 무지성 $Lazy$ $Propagation$을 박아도 되겠지만 업데이트 쿼리가 앞 쪽에 몰려 있고 출력 쿼리가 나중에서야 나온다면, 이제부터 $imos$법 사용 가능성을 고려해보자. 여기선 $1$차원이지만 $2$차원에서의 사용을 연습해보고 싶다면 이 문제 를, 트리와 곁들여보고 싶다면 이 문..
백준 14554 - The Other Way (C++) 문제 문제 링크 BOJ 14554 - The Other Way 문제 요약 $N$개의 정점으로 이루어진 그래프와 출발지, 목적지가 주어진다. 출발지에서 목적지까지 최단 경로로 가는 경우의 가짓수를 구해보자. 제한 TL : $2$ sec, ML : $256$ MB $2 ≤ N ≤ 100,000$ $N - 1 ≤ M ≤ 300,000$ 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 다이나믹 프로그래밍(dp) 풀이 $S$에서 $E$까지의 최단 경로는 다익스트라를 이용해 쉽게 구할 수 있다. 넓게 보면 $S$가 중간 정점 $X$를 거치고 $E$로 도달할 때, $S$ 에서 $X$로 가는 경우의 수 $*$ $X$에서 $E$로 가는 경우의 수 가 답이 된다. (단, 최단 거리로 이동할 때 기준)..
백준 25462 - Inverzije (C++) 문제 문제 링크 BOJ 25462 - Inverzije 문제 요약 길이 $N$인 수열과 $Q$개의 구간 쿼리가 주어진다. 각 쿼리에 맞는 답을 출력하자. 제한 TL : $4$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ a_i, b_i, P_i ≤ N$ 알고리즘 분류 자료 구조(data structures) 세그먼트 트리(segment tree) 오프라인 쿼리(offline_queries) mo's(mo's algorithm) 풀이 수쿼 $23$ 을 풀어 봤다면 보자마자 솔루션이 떠올랐을 것이다. 쿼리 내용 보자. $Q :$ $[a, b]$ 에 대해, $a ≤ i P_j$ 인 $(i, j)$ 쌍의 개수. 전형적인 $mo's$ 문제 형..
백준 27501 - RGB트리 (C++) 문제 문제 링크 BOJ 27501 - RGB트리 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 인접한 정점 간 색이 겹치지 않도록 $3$가지 색을 이용해 칠할 때, 구할 수 있는 합의 최댓값과 그 과정을 구해보자. 제한 TL : $1.5$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ $1 ≤ r_i, g_i, b_i ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 문제 유형 자체는 아주 친숙한 유형이다. 단지 트리 위에서 진행할 뿐이다. 임의의 정점이 가질 수 있는 상태는 결국 $3$가지 중 하나가 될테니, 다음과 같이 점화식을 정의해보자. $dp[p][q]$ : $p$번 정점을 루트로하는 서..

티스토리툴바