본문 바로가기

분류 전체보기

 (145)
백준 24520 - Meet In The Middle (C++) 문제 문제 링크 BOJ 24520 - Meet In The Middle 문제 요약 $N$개의 마을이 트리 형태로 주어지고 $Q$개의 약속이 마을 쌍의 형태로 주어진다. 각 약속마다, 두 마을에서 정확히 같은 거리만큼 떨어진 마을의 위치를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ w ≤ 10^9$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 최소 공통 조상 (lowest common ancestor) 희소 배열 (sparse_table) 풀이 $dist[x]$ : 루트로부터 $x$까지의 거리. $dp[x][y]$ : $x$의 $2^y$번째 부모 정점. 라고 할 때 $O(NlogN)$의 전처리를 통해 어떤 두..
백준 29261 - 소수 세기 (C++) 문제 문제 링크 BOJ 29261 - 소수 세기 문제 요약 소수 $P$가 주어진다. 아래의 과정을 반복할 때, 지워진 수를 포함하여 한별이가 소수를 적는 최대 횟수를 구해보자. 칠판에 적힌 수 중, $p_1 + p_2 + 1$$($단, $p_1, p_2$는 소수$)$ 꼴로 표현되는 수가 있으면 그러한 수 중 하나를 골라 지우고, 대신에 $p_1$과 $p_2$를 적는다. 만약 고른 수에 대해서 가능한 $(p_1, p_2)$ 쌍이 여러 개 있으면 그런 쌍 중 하나를 고른다. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ P < 3,000,000$ 알고리즘 분류 수학 (math) 정수론 (number_therory) 소수 판정 (primality_test) 풀이 식에서 $1$을 제하면 골드..
백준 25549 - 트리의 MEX (C++) 문제 문제 링크 BOJ 25549 - 트리의 MEX 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $mex(i)$의 정의가 아래와 같을 때, $mex(1), mex(2), ... mex(N)$을 출력하자. $mex(i)$ : $i$번 정점을 루트로 하는 서브 트리의 정점에 적혀 있지 않은 수 중에서 가장 작은 음이 아닌 정수. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 200,000$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 트리를 사용한 집합과 맵 (tree _ set / map) 작은 집합에서 큰 집합으로 합치는 테크닉 (smaller_to_larger) 풀이 어떤 정점의 서브트리에 포함되는 $v_i$들은 집합을 통해 쉽게 ..
백준 28472 - Minimax Tree (C++) 문제 문제 링크 BOJ 28472 - Minimax Tree 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리로 $Minmax$ $Tree$를 구성할 때, 각 정점의 답을 묻는 $Q$개의 쿼리에 답해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $1 ≤ Q ≤ 10^5$ $0 ≤ t_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 트리 (trees) 트리에서의 다이나믹 프로그래밍 (dp_tree) 풀이 기본적인 $TreeDP$ 문제이다. 문제에서 친절하게 규칙을 나열해주므로, 이를 그대로 코드에 옮겨주면 되겠다. 구체적으로 루트의 깊이를 $1$이라고 할 때, 리프 노드를 향해 내려가며 현재 깊이가 홀수라면 자식 노드의 최댓값을 현재..
백준 29447 - Выборы (C++) 문제 문제 링크 BOJ 29447 - Выборы 문제 요약 길이 $N$의 수열과 $Q$개의 구간 쿼리가 주어진다. 각 쿼리마다, 해당 구간에서 가장 많이 등장하는 수가 몇 번 등장했는지 출력하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ a_i ≤ 10^9$ 알고리즘 분류 오프라인 쿼리 (Offline Query) 좌표 압축 (Coordinate_Compression) mo's (mo's Algorithm) 풀이 BOJ 13548 - 수열과 쿼리 6 을 풀어 봤다면 이 문제역시 푼 거나 다름 없다. 단지 차이점은, $1 ≤ a_i ≤ 10^9$ 라는 것. 하지만 이 역시 $N ≤ 100,000$ 임에 따라 좌표 압축을 해주면 되기 때문에, ..
백준 28467 - Spell Cards (C++) 문제 문제 링크 BOJ 28467 - Spell Cards 문제 요약 $N$장의 카드가 단 하나만 남을 때까지 인접한 두 카드에 대해 마법을 시전한다. 최종적으로 소모하는 총 마력의 최솟값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 400$ $1 ≤ a_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 BOJ 11049 - 행렬 곱셈 순서 와 비슷한 느낌을 받았다면 충분하다. 식 정의에만 조금 차이가 있을 뿐, 본질적으로 비슷한 형태로 풀 수 있다. $dp[p][q]$ : 구간 $[p, q]$ 에서의 답. 어떤 구간에 대해, $p == q$ 가 아닌 이상 반드시 두 연속 부분 수열로 나누어 답을 구할 수 있다. 구체적으로 구간 $[p, q]$의 답..
백준 28707 - 배열 정렬 (C++) 문제 문제 링크 BOJ 28707 - 배열 정렬 문제 요약 길이가 $N$인 배열 $A = [A_1, A_2, ... A_N]$와 $M$가지의 조작 정보가 주어진다. 조작을 순서, 횟수에 상관없이 원하는만큼 적용할 수 있을 때, $A$가 비내림차순이 되도록 하는 데에 드는 최소 비용을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 8$ $1 ≤ M, A_i,c_i ≤ 10$ 알고리즘 분류 자료 구조 (data_structures) 그래프 이론 (graphs) 트리를 사용한 집합과 맵 (tree _ set / map) 다익스트라 (dijkstra) 풀이 오랜만에 참신한 문제를 만났다. 범위가 굉장한 힌트를 주지만 뭔가 구현이 답답할 수 있는데, 한 번 이렇게 생각해보자...
백준 28433 - 게리맨더링 (C++) 문제 문제 링크 BOJ 28433 - 게리맨더링 문제 요약 길이 $N$의 수열이 주어질 때, 이 수열을 원하는 개수의 연속된 구간으로 나누어 각 구간의 합을 계산한다. 이때, 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과하도록 할 수 있을까$?$ 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 2*10^5$ $-10^9 ≤ N_i ≤ 10^9$ $1 ≤ T ≤ 10^4$ 입력에서 주어지는 $N$의 합은 $2*10^5$를 넘지 않는다. 알고리즘 분류 그리디 알고리즘(greedy) 풀이 다음의 일반적인 두 사항은 관찰을 통해 쉽게 알아낼 수 있다. 연속된 음수는 반드시 하나로 합치는 것이 최선이다. 연속된 양수는 반드시 별개로 보는 것이 최선이다. 이를 바탕으로 풀이를 ..

티스토리툴바