구사과

1. Arrays 두 행과 열을 바꾼다는 것이 무슨 뜻인지 먼저 생각해 보자. 각각의 행과 열에 대해서 순열 P[i]와 Q[i]를 정의하자. P[i] = (현재 i번 행의 원래 위치), Q[i] = (현재 i번 열의 원래 위치) 라고 하면, 두 행을 바꾸는 것은 단순히 P[i]와 P[j]를 바꾸고, 열을 바꾸는 것은 단순히 Q[i]와 Q[j]를 바꾸는 것이다. 고로 우리가 주어진 연산으로 할 수 있는 것은 P와 Q를 임의의 순열로 섞는 것이니, A와 B가 닮았다 (alike) 는 것은 A[P[i]][Q[j]] = B[i][j] 를 만족하는 순열 P, Q가 존재한다는 것과 동치이다. 모든 수가 다르니, 각 수가 A에서 어떤 위치, B에서 어떤 위치에 있는지를 유일하게 결정할 수 있다. 즉 P[i] = j,..

1. 전구편의상 왼쪽 스위치와 오른쪽 전구의 번호가 1 2 3 4.. 처럼 순서대로 되어 있다고 하자. p[i] = (왼쪽 i번 스위치를 눌렀을 때 켜진 오른쪽 전구의 번호) 라 하자. 전선이 교차하지 않게 왼쪽에서 {i1, i2, i3, ... ik} 스위치를 켰다는 것은, p[i1] < p[i2] < p[i3] < ... < p[ik] 라는 것과 동치이다. 이렇게 최대 개수의 스위치를 켜는 것은, 최장 증가 부분 수열 (LIS) 문제와 동일하다. 이는 동적 계획법으로 O(N^2)에 찾고 역추적도 할 수 있다. (만약 방법을 모른다면, dp[i] = i번 수에서 끝나는 최대 길이의 LIS라 정의하고 생각해 보자.)왼쪽 스위치와 오른쪽 전구의 번호가 실제로 1 2 3 4가 아니라는 것이 문제인데, 그냥 ..

1. 생존자이 문제를 푸는 데 있어서 아주 중요한 아이디어는, 바로 이것이 스케줄링 문제라는 것을 발견하는 것이다. 다음과 같은 문제를 생각해 보자. * N개의 작업이 있다. 각 작업은 S_i 시간 동안 연속적으로 해야 하며, P_i + S_i 시간 내에 완수해야 한다. 작업이 돌아가는 시간을 최대화하여라.이 문제는 원래 문제랑 완전히 동일한 문제일까? 한번 문제의 조건들을 다시 잘 살펴보자. * S_i 시간 만큼 허기를 채울 수 있고 (작업을 돌릴 수 있고), P_i 시간 전에 시작해야 한다는 것은 P_i + S_i 시간 전에 끝내야 한다는 것과 동치이다. * 허기를 채울 수 있는 시간동안은 먹지 않는다. 즉 두 개의 작업을 동시에 하지 않는다. * 지금부터 음식을 먹는다 / 허기를 채우지 않으면 바로..