devbelly

문제 www.acmicpc.net/problem/3392 알고리즘 Sweeping 문제 사각형을 구성하는 좌표들이 주어질 때, 모든 사각형의 면적을 구하는 문제입니다. 단 겹치는 좌표는 한 번만 계산해야 합니다. 각 직사각형을 두 개의 선분으로 분리한 후, x좌표를 기준으로 정렬합니다. 두개의 선분이란 직사각형을 놓았을 때 가장 왼쪽에 있는 선분, 가장 오른쪽에 있는 선분을 의미합니다. 예를 들어 직사각형을 이루는 좌표 (10,10), (20,20)을 받았다면 두 직선은 (10,10,20), (20,10,20)입니다. 앞에서부터 x좌표와 y좌표들입니다. 그리고 순차적으로 각 간선들을 살펴나가며 만약 왼쪽에 있는 선분이라면 그 선분이 가리키는 y좌표들을 업데이트해주고, 오른쪽에 있는 선분이라면 그 선분이 ..

문제 www.acmicpc.net/problem/18877 알고리즘 binary search 풀이 COWVID-19의 영향으로 사회적 거리두기를 실천하는 소들의 수가 주어집니다. 목초지의 범위가 주어지고 해당 범위안에 소를 배치하되, 가장 가까운 소의 거리가 최대가 되도록 하는 문제입니다. 소들을 임의의 거리 $d$로 배치할 수 있다면, $d$이하의 거리로 소를 배치할 수 있음이 자명합니다. 이분탐색으로 범위를 좁혀나갈 수 있다는 뜻과 동치입니다. $solve$함수는 거리$d$로 $N$마리의 소를 배치할 수 있는가를 리턴하는 함수입니다. $cur$은 가장 최근에 소를 배치한 지역을 의미합니다. 맨 처음에는 당연히 소를 배치하지 않았으므로 가장 작은 수로 초기화를 합니다. 다음의 $cur$이 될 수 있는 ..

문제 www.acmicpc.net/problem/1517 알고리즘 펜윅트리 풀이 $N$제한이 50만이고 배열의 inversion들을 카운트 하는 문제입니다. 버블소트에서의 교환횟수는 inversion의 수와 동일합니다. inversion이란 $i$$A[j]$ 인 상황을 의미합니다. inversion을 찾으면 swap을 진행하고 inversion의 수가 하나 줄어들고 inversion이 0이 되면 소트가 종료됩니다. 이중포문을 통해 $O(N^2)$에 inversion의 수를 구할 수 있지만 $N$제한이 50만이므로 더 빠른 알고리즘이 필요합니다. 이 문제와 비슷하다고 생각되어 좌표압축 + 세그먼트 트리로 해결하여 풀었지만 좀더 간단하게 푸는 방법을 설명해드리겠습니다. inversion을 카운트 하기 위해선..

문제 www.acmicpc.net/problem/3584 알고리즘 DFS, LCA 풀이 그래프가 주어지고 두개의 정점이 주어졌을 때, LCA를 구하는 문제입니다. LCA를 나이브하게 처리하는 방법은 루트 정점을 구한 후 그 정점으로부터 다른정점들의 깊이를 구합니다. 그리고 처리해야할 두 정점 $u$,$v$를 입력받으면 두 정점이 같아질 때까지 깊이를 기준으로 하나씩 정점을 위로 보내면 됩니다. 깊이를 처리해야하는 시간복잡도는 $O(N)$이고 worst case 또한 모든 간선을 다 탐색하는 것이므로 $O(N)$입니다. 이 문제는 Testcase의 수가 적어 $O(T*N)$에 처리됩니다. 코드 #include #define rep(i,n) for(int i=0;i tc; while (tc--) { cin ..

문제 www.acmicpc.net/problem/12014 알고리즘 LIS, 이분 탐색 풀이 $N$일 동안의 주가가 주어졌을 때, $K$일 동안 첫날을 제외하고 직전 날 산 주가보다 비싸게 구매할 수 있는지를 묻고 있습니다. 유명한 Longest Increasing Subsequence 문제입니다. 다이나믹 프로그래밍으로 $O(N^2)$에 해결 가능합니다. 하지만 주어지는 테스트케이스가 100개에 $N$제한이 1만이므로 해당 알고리즘을 사용하면 시간 초과가 발생합니다. 처음에 정렬된 배열을 하나 갖고 시작합니다. 처음이므로 정렬된 빈 배열을 갖고 있습니다. $N$개의 값을 순차적으로 보며 해당 값을 정렬된 배열 어디에 위치한지 찾습니다. 정렬된 배열에서 위치를 찾는 것이므로 이분 탐색으로 찾을 수 있습니..

문제 www.acmicpc.net/problem/10573 알고리즘 DP 풀이 해당 수가 증가하는 수 인지 판별하고, 증가하는 수라면 그 수보다 작은 증가하는 수를 찾는 문제입니다. 증가하는 수를 판별하는 건 어렵지 않으니 다음 문제인 개수를 찾는 문제를 생각해봅시다. 증가하는 수의 구조는 최적 부분 구조를 만족하게 됩니다. 현재의 수가 증가하는 수라면 맨 앞자리 하나를 제거한 수 또한 증가하는 수를 만족하기 때문입니다. $cache [i][j]$= j부터 증가하는 수를 i자리 만들었을 때, 가능한 개수 $cache [i][j]$를 갖고 갱신할 수 있는 상태는 j이하의 수를 맨 앞자리에 붙이는 것입니다. 즉 다음 상태는 $cache [i+1][k]$ (단, k는 j이하의 수이다) 입니다. 나머지의 아이디..

문제 www.acmicpc.net/problem/17365 알고리즘 트라이 + DP 풀이 문래빗어 사전에 적혀있는 단어수와 그 단어들이 주어졌을 때, 해석하려는 문자열의 가능한 경우의 수를 묻고 있습니다. 해석하려는 문자열을 $str$이라 하겠습니다. (아래에서 언급하는 $str [a:b]$ 는 $str$ a번째 인덱스부터 b번째 인덱스까지의 부분 문자열입니다) $cache [i]$= i+1번째 문자열까지 해석했을 때, 가능한 경우의 수 $cache [i+1]$은 다음 상태들의 합입니다. $cache [i]$에서 가능한 개수 * 단어들 중 $str [i+1]$와 매칭 가능한 개수 , cache [i-1] * 단어들 중 $str [i:i+1]$와 매칭 가능한 개수... (매칭이 가능하다는 것은 문래빗어 정..

문제 www.acmicpc.net/problem/17291 알고리즘 DP 풀이 기준년도 1년 2월에 개체가 +1 생겼을 때, $N$년도후의 개체수를 묻고 있습니다. 홀수년도에 태어난 개체는 3번 분열 후 죽고, 짝수년도에 태어난 개체는 4번 분열 후 죽습니다. DP는 최적해를 구할 때(최댓값, 최솟값)뿐만 아니라 순차적으로 진행해나가는 문제에서도 사용할 수 있습니다. $cache[i]$=$i$년도에 존재하는 개체수 위와 같이 설정하고 풀어나가면 됩니다. 코드 #include #define rep(i,n) for(int i=0;i N; cache[0]=cache[1] = 1; for (int i = 1;i < N;++i) { cache[i + 1] = cache[i] * 2; //cache[i-3], ca..