본문 바로가기

백준

 (223)
[ICPC] 백준 3860 - 할로윈 묘지 https://www.acmicpc.net/problem/3860 힌트 더보기 이 문제는 그래프를 제대로 모델링하지 않으면 틀리는 문제다. 다음 요소를 점검해보자. 1. 도착지에서 이동을 불허하는지? 2. 도착 여부보다 음의 사이클 검출 여부가 우선이다. 3. 귀신 구멍에 대한 처리를 제대로 한 게 맞는지? 다음 TC에 대해 답이 Never가 나와야 한다. 확인해보자. 3 3 2 2 1 1 2 1 1 0 1 0 -1 0 0 솔루션 더보기 겉으로 보기엔 벨만포드 알고리즘을 적용하기만 하면 되는 문제로 보인다. 다만 주어진 규칙에 따라 가중치 그래프를 제대로 만들지 않으면 틀린 답을 얻게 된다. 규칙을 다시 정리하면 도착하는 즉시 빠져나와야 하고 귀신 구멍에 들어가면 지정한 위치로 이동하며 묘비로는 갈 수 ..
[USACO] 백준 6002 - Job Hunt https://www.acmicpc.net/problem/6002 힌트 더보기 어떤 도시를 도착하든 D원을 벌어야 나갈 수 있다. 시작 도시도 예외는 아니다. 풀이 더보기 도시를 잇는 도로와 비행기 노선이 제공될 때 어떻게 하면 큰돈을 벌 수 있을까? 비행기를 타는데 소비되는 비용을 음수 가중치라 생각하면 이 문제는 음수 가중치가 있는 그래프에서 최장 경로를 찾는 문제가 된다. C도 220 이하이므로 벨만포드 알고리즘의 사용을 적극 고려해볼 수 있다. 다만 돈을 버는 행위는 간선이 아닌 정점에서 일어난다는 것에 유의해야 한다. 문제의 상황을 벨만포드로 모델링하기 위해 기존 알고리즘의 구현에서 두 가지 조치를 행하면 된다. 1. 시작점의 초기값을 0이 아닌 D로 둔다. D만큼 벌어야 도시를 나갈 수 있기 ..
백준 13548 - 수열과 쿼리 6 https://www.acmicpc.net/problem/13548 모스 알고리즘의 연습 문제 중 하나이다. $O((N + M) \sqrt M)$으로 처리를 하되, 다음을 이용해야 한다. 포인터가 한 index 움질일 때마다 구간에 속한 수의 출현 빈도의 변화량 d는 $-1 \leq d \leq 1$ 이므로 $O(1)$에 출현 횟수의 변화를 계산할 수 있다. 이를 구현하기 위해 어떤 수를 index로 하여 그 출현 횟수를 저장하는 배열 mp와 어떤 출현 횟수를 index로 하여 그 출현 횟수의 횟수를 저장하는 배열 counter를 둔다. 이렇게 되면 구간이 1씩 길어질 때마다 새로 포함된 값 x를 mp에 반영하기 전에 기존 구간에서 x의 출현 횟수를 저장한 counter를 바꿔줘야 한다. counter의..
백준 16978 - 수열과 쿼리 22 https://www.acmicpc.net/problem/16978 힌트 더보기 x번째 원소 갱신을 하기 전 x - 1번째 원소 갱신을 한 세그먼트 트리의 구간합을 구할 수 있다. 각 쿼리를 보존하여 적절한 시기에 처리하도록 한다. 풀이 더보기 특정 시점까지 갱신이 적용되었을 때의 구간 합을 구하는 문제이다. 조금만 생각해보면 구간 합은 원소의 갱신에 미치는 영향이 없다는 사실을 깨달을 수 있다. 그렇다면 0번째 원소 갱신을 수행 후 구간 합 연산 -> 1번째 원소 갱신 수행 -> 1번째 원소 갱신을 수행 후 구간 합 연산 -> 2번째 원소 갱신 수행 ->... 이처럼 계산하면 질의마다 올바른 값을 얻을 수 있다. 그런데 어떻게 구현해야 될까? 세그먼트 트리를 초기화만 해주고 입력받는 쿼리들에 대해 바로..
[ICPC] 백준 4803 - 트리 https://www.acmicpc.net/problem/4803 힌트 더보기 주어진 포레스트에 어떤 상태들이 존재할 수 있는지 생각해보자. 풀이 더보기 주어진 포레스트에서 트리의 개수를 찾는 문제이다. 포레스트에 트리와 그래프 둘 다 있을 수 있다는 사실을 유의해야 한다. 이를 간과하지 않으면 예상치 못한 오답을 받게 된다. 각 노드를 돌면서 그래프가 트리인지 확인하여 개수에 따라 올바른 문자열을 출력하면 된다. 노드의 개수가 500 이하이기 때문에 DFS로 사이클 찾기를 하던지 유니온 파인드로 사이클 감지를 하던지 상관없다. 유니온 파인드를 사용할 때는 그래프와 트리가 연결되는 경우를 조심하도록 한다. 전체 코드 - 유니온 파인드로 구현했다. #pragma GCC target("avx,avx2,fma..

티스토리툴바