devbelly

문제 www.acmicpc.net/problem/15589 알고리즘 Sweeping 풀이 $N$명의 라이프가드가 있습니다. 한 명을 해고했을 때, 가장 긴 시간을 커버하도록 해야 합니다. 다른 사람과 근무시간이 겹치지 않는 시간을 고유 시간이라고 정의하겠습니다. 해고하지 말아야할 사람은 고유시간이 큰 사람들입니다. 자신의 가치가 높다는 뜻입니다. 반대로 해고해야할 사람은 고유시간이 가장 작은 사람입니다. 사람마다의 고유시간을 구할 수 있다면 이 문제에서 푼 것과 같이 $N$명의 총 근무시간에서 고유시간이 가장 짧은 사람을 해고하면 될 일입니다. 첫 번째 단계로 모든 사람의 총 근무시간을 구해봅시다. #include #define rep(i, n) for (int i = 0; i < n; ++i) #def..

문제 www.acmicpc.net/problem/12877 알고리즘 union find 풀이 N개의 동물들과 각 관계를 설명하는 K개의 정보가 주어질 때, 모순이 되는 정보들의 갯수를 세는 문제입니다. 문제가 되는 것은 2번 타입의 정보입니다. 동물들마다 3개의 노드를 갖도록 합시다 . 각각은 $i$번째 동물의 타입을 가리키게 됩니다. 구체적으로 $i$번째 동물이 A종류일때는 배열 $i$번이 정보를 갖고 있고 B, C 종류일때는 각각 $i+N$, $i+2*N$ 배열이 정보를 담고 있습니다. 이제 $union$함수를 통해 묶인 그룹은 해당 정보가 동시에 발생한다는 의미를 담는다고 합시다. 이렇게 되면 2번 정보또한 처리가 가능해집니다. 2 X Y가 입력으로 들어왔다면 아래 세 정보를 유니온 해주면 됩니다...

문제 www.acmicpc.net/problem/15590 알고리즘 greedy 풀이 $N$마리의 소, $M$명의 우유 구매자, $R$명의 대여 희망자가 주어질 때, 얻을 수 있는 최대 수익을 구하는 문제입니다. 소를 우유 생산량에 따라 정렬해놨을 때, $i$번 소까지는 대여를 하고, 그 이후의 소들은 젖을 짜 우유를 판매하는 것이 최적이므로 우리는 어느 소까지만 대여를 해줄지 구해야합니다. 일단 모든 소를 대여해준 후 가장 가치가 높은 소(우유 생산량이 가장 많은 소)부터 우유를 짜서 가장 비싸게 사는 사람에게 판매합니다. 대여 희망자에 대한 누적합을 구해놓았다면 $i$번째 사람까지 대여를 했을 때 벌 수 있는 돈을 $O(1)$에 구할 수 있습니다. 이때 정답이 더 크게 갱신이 된다면 계속 진행을 하고..

문제 www.acmicpc.net/problem/14245 알고리즘 fenwick 풀이 구간 업데이트와 점 쿼리를 처리하는 문제입니다. 일반적인 펜윅트리는 점 갱신과 구간 쿼리를 처리하는 용도로 많이 사용됩니다. 구간 갱신을 사용하기 위해서는 일반적으로 lazy propagation을 떠올리기 쉽습니다. 하지만 구간 갱신을 처리하더라도 쿼리가 구간 쿼리가 아닌 점 쿼리만 이루어진다면 일반적인 펜윅트리의 변형으로도 가능합니다. 일반적으로 펜윅트리에서 배열 $A$에 대해 우리가 하는 연산은 다음과 같습니다. $update(i,v)$ = $A[i]$에 $v$만큼 더하기 $query(i)$ = $A[1]$~$A[i]$까지 합 구하기 다음과 같은 $B$배열을 만들면 구간 갱신과 점 쿼리가 가능합니다. $B[i]$..

문제 www.acmicpc.net/problem/2302 알고리즘 DP 풀이 극장좌석 $N$개가 주어질 때, 앉을 수 있는 경우의 수를 묻는 문제입니다. VIP가 아닌 좌석은 좌우로 자리를 바꾸어 앉을 수 있습니다. $i$번째 자리가 양 옆자리와 바꿀 수 있다고 생각하면 조금은 헷갈리는 문제입니다. $i$번째 자리가 오른쪽과 바꿔 앉는 것은 $i+1$번째 자리가 왼쪽과 바꿔앉는 경우와 일치하므로 왼쪽 좌석과 바꿀 수 있다고 문제를 생각하겠습니다. $cache[i]$= $i$번째 자리까지 고려했을 때 앉을 수 있는 경우의 수 이는 자리를 바꿀 때 $cache[i-2]$와 자리를 바꾸지 않았을 때인 $cache[i-1]$의 합으로 나타낼 수 있습니다. 코드 #include #define rep(i, n) f..

문제 www.acmicpc.net/problem/20191 알고리즘 이분탐색 풀이 문자열 S와 T가 주어집니다. $T^n$을 문자열 T를 n회 반복한 문자열이라고 정의할 때, n번 반복하여 줄임말 S를 만들기 위한 최소 n을 구하는 문제입니다. 줄임말을 만들 때, 순서를 유지한다는 점에서 투포인터 전략을 떠올릴 수 있습니다. 각각을 $pt, ps$라고 해봅시다. 각 포인터가 가리키는 문자열이 일치할 때는 둘 다 1씩 더해서 다음 문자를 확인하고 다르다면 $pt$만을 증가시키고 문자열 T가 끝에 다다랐다면 다시 $pt$를 0으로 초기화 해줍니다. 이렇게 할 경우 다음과 같은 예시에서 비효율적으로 작동하게 됩니다. zzzz aaaz 즉 z가 나타나는 위치를 찾기 위해 일일이 T문자열을 탐색하는 대신, 다른 ..

문제 www.acmicpc.net/problem/13309 알고리즘 HLD 풀이 트리에서 두 노드를 잇는 경로가 존재하는지 묻는 문제입니다. 추가적으로 조건에 따라 간선을 끊어주기도 합니다. 트리에서 부모 노드는 유일합니다. 즉 부모 노드로 가는 간선은 유일하므로 모든 간선은 루트를 제외한 모든 노드들로 표현이 가능합니다. HLD를 통해 트리를 일자 형태인 배열로 나타낸 후, 세그먼트 트리를 이용해 구간의 최솟값을 구하면 경로가 존재함을 알 수 있습니다. 최솟값이 1이라면 경로가 존재, 0이라면 끊어져 있는 것입니다. 간선을 끊을 때, 세그먼트 트리에 0 값을 업데이트하면 됩니다. 세그먼트 트리에 접근할 때는 $idx$배열을 통해 접근해야 함을 유의하도록 합시다 코드 #include #define rep..

문제 www.acmicpc.net/problem/20647 알고리즘 DFS 풀이 $N$개의 목장이 트리 형태로 주어집니다. 1번 목장에 감염된 소가 있을 때, 모든 목장의 소가 감염되기 까지 최소일수를 구하는 문제입니다. 그리디 문제인데 자세한 관찰을 하지 못해 많이 틀렸습니다. 제 잘못된 관찰은 1번 목장에서 거리가 2이하인 목장들은 1번 목장에서 감염 후 이동해야한다고 생각했습니다. 이렇게 해야 복제시간에서 이득을 본다고 생각했기 때문입니다. (거리가 1인 노드를 무시한 채 거리가 2인 노드들만 고려해서 계산했음. [복제(1번노드)-이동-이동] 과 [복제(1번노드)-이동-복제(2번노드)-복제] 로 비교를 했지만 이는 거리가 1인 노드들을 처리하며 갈 수 있음을 무시한 계산이므로 틀렸음) 올바른 해는 ..