이동식 저장소

17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 �� www.acmicpc.net 쿼리 문제의 특징은 쿼리가 매우 많다는 점이다. 보통은 쿼리를 선형 시간보다 더 빠르게, 즉 로그 시간이나 상수 시간에 처리해야 한다. 이 문제 역시 쿼리의 수 Q가 20만, 합성 횟수 N이 50만으로 O(QN) 시간에 해결할 수 없다. 내가 지금까지 풀었던 쿼리 문제는 보통 쿼리를 로그 시간에 처리했다. 이번에도 로그 시..

몇 달 동안 프로젝트와 과제에 치여 살다가, 시험기간을 맞아 오랜만에 백준 문제를 풀었다. 분명 시험기간인데 평소보다 더 여유로운 건 뭐지..? 이것이 오픈북 효과인가? 3665번: 최종 순위 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 �� www.acmicpc.net 작년 순위와, 올해 순위가 바뀐 팀의 쌍이 주어진다. 이때 올해 순위를 결정할 수 있을까? 순위라는 말에서 위상 정렬을 생각해 내야 한다. 기존에 주어진 순위에서 두 팀간의 순위 관계를 알 수 있고, 올해 변경된 순위 관계를 반영하여 위상 정렬을 하면 된다. 위상 정렬을 하기 위해 먼..

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 숫자의 배치 순서를 바꿔서 수를 최대로 만들어야 하는 문제이다. 무식하게 풀어보기 모든 가능한 $(i, j)$ 쌍을 바꿔 보는 방법을 생각해 볼 수 있다, 그러나 경우의 수가 최대 $\left(\begin{array}{c}7\\ 2\end{array}\right)^{10}=16,679,880,978,201$개나 있으므로 완전 탐색으로는 문제를 풀 수 없다. 그렇다면 기억해 보자 메모이제이션을 활용하여 중복 계산을 줄여 보자. 다음을 정의한다. $ans(n, dep) = dep$번 교환하여 얻은 수가 $n$일 때, 교환을 완료하여 얻..

이 문제의 대회 데이터가 공개되어 있으니 사용해 보자. 원문 제목은 labudovi이다. 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 얼음을 녹이면서 백조가 만날 수 있는지 확인해야 한다. 물과 인접한 얼음이 녹는다는 설명에서 BFS를 적용해야..

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다. www.acmicpc.net 게임판을 탐색하는 전형적인 동적 계획법 문제이다. 어떤 칸에서 시작하여 게임을 진행할 수 있는 최대 횟수는 정해져 있으며, 그러한 횟수가 변하지 않기 때문에 한번 계산한 결과를 계속해서 써먹을 수 있고, 그래야만 한다. 메모이제이션 없는 완전 탐색의 시간복잡도는 $O(4^{nm})$이다. 실제로는 구멍에 빠지는 등의 종료로 인해 더 작겠지만 전체적으로 보면 지수 꼴의 시간 복잡도를 갖는다. 단 여기서 사이..