목록Algorithm/Problem Solving (95)
블로그 옮겼습니다
boj.kr/9426 \(1\leq{N}\leq{250000}\) \(1\leq{K}\leq{5000}\) \(K\leq{N}\) \(0\leq{a_i}\leq{65535}\) 이 문제는 N개의 수와 구간의 길이 K가 주어졌을 때 N-K+1 개의 연속된 구간의 중앙값을 모두 더하여 출력하는 문제이다. 중앙값의 정의는 (K+1)/2 번째로 작은 수이다. naive 하게 생각해보면 O(N)개의 구간에 대해 정렬하여 가운데값을 구하는데 O(NlgN) 이므로 O(N^2lgN)이 든다. 근데 O(N^2)도 시간안에 돌아가기 힘들다. 어떻게할까? 펜윅트리에 수가 현재 길이 K의 구간안에 하나 들어갈 때마다 수 자체를 인덱스로 1업데이트하고 구간에서 사라지면 -1업데이트하는식으로 생각해보자. 그럼일단 0번째인덱스부터..
\(2\leq{len}\leq{2500}\) 이 문제는 길이 len 의 correct parentheses sequence 가 주어졌을 때 왼쪽에 있는 '열린 괄호'를 하나와 임의의 위치에 있는닫힌 괄호 하나, 총 두개를 지우는 행위를 빈 문자열이 될 때 까지 반복하는 방법의 수를 구하는데, 지울 때 마다 지운 직후에도 correct paranthese sequence 이도록 지우는 방법의 수를 구하는 문제이다. 우선 이 문제를 좀 더 간단하게 바꿔보자. 왼쪽에서부터 열린괄호 하나와 닫힌괄호 하나를 지워나가는 것은 결국열린괄호 하나와 닫힌괄호 하나를 매칭시키는 것과 같다고 볼 수가 있다. 물론 한 쌍을 지워도correct parentheses sequence 이도록 말이다. 그럼 주어진 제약조건을 만족하..
문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{c}\leq{10^9}\) 노드의 개수 N, 엣지의 개수 M, 각 엣지에는 색 c 가 부여된다. 색은 정수로 주어진다. 엣지는 양방향이다.두 노드 사이에 엣지는 여러개 있을 수 있다.출발점은 1번노드, 도착점은 N번노드이다. 출발점에서 도착점까지 갈 때 지나는 통로의 색을 순서대로 적는다.출발점부터 도착점까지 최단경로로 갈 때의 색의 sequence 를 구하는 문제. 만약 최단경로가 여러개라면사전순으로 앞서는 sequence 를 구하는 문제이다. 우선 priority_queue 를 사용해 다익스트라를 하듯이 거리와 색의 우선순위에 따라 도착지까지 가면서색의 seqeunce 를 구해주면 될..
문제 링크 이 문제는 일단 모빌이 주어진다. 모빌이란, 막대기가 있고 막대기의 양쪽에 모빌또는 물체가 달린다.모빌의 깊이는 최대 16이다. 이때 각 모든 막대기의 양옆에 달린 덩어리 두개가 균형을 이루게 만들기 위해최소 몇개의 물체나 무게를 변경해야 하는지 구하는 문제이다.예를들어,이런 모빌이 있다면 7을 3으로 만들면 모든 막대기에서 균형이 맞게되므로 답은 1이다.3을 7로, 6을 14로 바꿔도 균형을 이루지만 최소의 개수가 아니기 때문에 답이 아니다. 그러면 결국 전체 모빌의 무게를 x로 만들려고 할때 각 덩어리의 무게는 다음과 같이 만들어 주어야 한다. 그렇다면 x를 정해주고 재귀적으로 따라 내려가면서 각각의 덩어리에 대해 되어야 하는 무게와 현재 물체의 무게가같다면 바꾸어 주어야하는 것이기 때문에..
문제 링크 \(1\leq{V}\leq{10^3}\)\(1\leq{E}\leq{V\cdot(V-1)/2}\)\(1\leq{T}\leq{10}\) 도시의수 V와 검사해야 할 도로의 수 E가 주어지고, E개의 줄에 대해 도로가 잇는 두 도시 a b 가 주어진다.모든 두 도시 간에는 도로가 있으며, 각 도로를 지나는데 드는 시간은 T이다. 도로를 검사하는 검사자가 주어진 E개의 도로를 모두 지나야 한다. 이 때 최소 시간을 구하는 문제이다. 모든 엣지의 가중치가 T로 같은 것이기 때문에 이 문제는 결국 최소의 간선을 지나면서 주어진 간선을 모두 지나는문제를 풀고 T를 곱하면 된다. 최소의 간선을 지나려면 주어진 간선들을 딱 한번씩만 지나고주어진 간선 외의 간선은 가능한한 지나지 않으면 될 것이다. 주어진 간선만..
문제 링크 \(N\leq{2\cdot{10^5}}\)\(1\leq{a_i}\leq{10^4}\)\(Q\leq{10^4}\)\(1\leq{l_i},\,{r_i}\leq{N}\) (\(l_i= 10000 일때는무조건 0을 출력, 그 외의 경우에는 그냥 직접 정렬을 해서 순회하며 답을 찾으면된다.그러면 각 쿼리마다 최악의 경우 O(KlgK) (K
문제 링크 \(1\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{x,y}\leq{10^6}\) 2차원 좌표평면상에 도시의 개수 N이 주어지고 N개의 줄에 각 도시의 x,y 좌표가 주어진다.그리고 쿼리의 수 M이 주어지는데 각 쿼리의 동작은 두가지다. road a b : 도시 a와 b 사이에 직선 도로를 이어 하나의 state 로 만든다.line c : x축에 평행하게 y = c 직선을 그어 한 도로라도 이 직선에 교차되는 state 들의 수와그 state 들의 도시 수의 합을 출력한다. c는 무조건 1.5, 5.5 등 ~~.5 의 형태이며 도로들은 서로 교차하지 않는다. \(0\lt{c}\lt{10^6}\) 서로다른 state 가 도로에 의해 하나의 ..
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3138 정말 좋은 문제인것 같다. 풀이
https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=4075 해석이 너무 안돼서 제대로 이해하는데 엄청 오래걸렸다.. \(5\leq{N}\leq{2\cdot{10^4}}\)\(0\leq{M}\leq{2\cdot{10^5}}\)N은 회사의 수, M은 쿼리의 수N개의 회사는 각각 센터를 가지고 있다. 이 회사들의 일부를 병합을 하여 하나의 더 큰 덩어리로 만드는 동시에센터는 하나로 유지를 하려고 한다. 병합을 할 때에는 하나의 덩어리의 센터에서 나머지 덩어리의 아무 회사로도로를 놓으면서 병합을 한다. 도로의 길이는 회사 a와 b를 이을 때 | a - b| mod 10..
https://community.topcoder.com/stat?c=problem_statement&pm=11514 \(1\leq{N}\leq{50}\)\(1\leq{C}\leq{N}\)\(1\leq{L}\leq{50}\)문자열의 개수 N개와 N개의 알파벳 소문자로만 이루어진 문자열이 주어지고,C와 L이 주어지는데, 길이 L의 문자열을 만들고 싶은데, 이 만들어진 문자열 내에 N개의 문자열들 중딱 C가지만 등장하도록 만드는 모든 문자열의 가짓수를 구하는 문제이다.우선 N가지의 문자열들 중 딱 C가지만 등장하는지 여부를 판단하려면 N개의 문자열을 동시에 하나의 긴 문자열에서등장하는지 찾아주는 알고리즘인 아호코라식 알고리즘이 필요하다는 것을 느낄 수가 있으며,N가지 중 지금까지 몇가지가 등장했는지를 알아야 ..