0 matrix

gistfile1.txt

0-1 매트릭스 문제..


우선 1d 에서 생각을 해보자.
1d 의 길이가 n 이라고 하자 

마지막이 1 이면 그 1 을 뒤집어 가는 방식으로 모두 0 으로 만들 수 있다.
그런데 과연 이방법이 최선의 방법인가?


Q. 앞의 수들을 먼저 flip 하다가, 마지막 1을 중간에 바꾸는 방식으로 더 optimal 한 방법을 찾을 수는 없다는 것을 어떻게 알 수 있는가?

A 를 주어진 배열이라고 하고
A 전체를 flip 한 배열을 B라고 하자
A 의 모든 수를 0 으로 만드는 cost 가 C 라면
B 의 모든 수를 1 로 만드는 cost 도 마찬가지로 C 이다 

예를들어 
100101 을 0 으로 만드는 것이나 (X00X0X 를 모두 0)
011010 을 1 로 만드는 것은 같은 cost 로 할 수 있다.  (X11X1X 을 모두 1)

A[:n-1] + [1] 을 flip 하면
B[:n-1] + [0] 이 된다. 

그런데 
A 를 1 로 만드는 cost 나 B 를 0 으로 만드는 cost 는 같다. 
따라서 
마지막 1 을 남겨둔 A 를 1로 만들고나서, 마지막 1까지 모두 flip 하는 벙법을 택한다면 cost + 1 이 들고
마지막 1 을 flip 한 후 B 를 0 으로 만드는 방법을 택해도 cost +1 이 든다. 

그래서 마지막 1 을 처음에 flip 하거나 마지막에 flip 하거나, optimal 한 cost 는 같다.


Q. 마지막 1을 처음이 아니라, 중간에 flip 하는 permutation 이 더 optimal 한 cost 를 찾아낼 수 없다는 것을 알 수 있나?

I th 를 flip 하는 것과 j th 를 flip 하는 두 flip 의 순서를 바꿔도 flip 의 결과는 같다. 
즉 I < j 라고 할때, i 이하의 것들은 2번 flip 이 되고, 
I 보다 큰 것들은 1번만 flip 이 된다. 

따라서, 마지막 1을 처음이나 마지막이 아닌 중간에 flip 하는 permutation 이더라도, flip 의 순서를 바꿔를 바꿔 처음이나 마지막에 마지막 1을 flip 하는 것으로 permutation 을 변경할 수 있다. 
그렇기 때문에, 중간에 flip 하는 것이, 더 optimal 한 cost 를 찾아낼 수는 없다. 

이렇게 생각하면, 
마지막 1 부터 0 으로 만들어 오는 방법 외에도,
앞에서 부터 바꿔가는 방법도 가능하고, 중간에서 바꿔 가는 방법도 가능하다. 


맨 앞부터 처리해 나간다면, 
그다음 수와 같게 앞의 수들을 바꿔 나가는 방법을 쓸 수 있다.

100101
000101 (1번째 1 을 두번째 0 과 같게 만듬)
111101
000001
111111
000000

뒤에서 부터 처리해 나간다면, 

100101
011010
100100
011000
100000
000000


또는 어느 index 에서든, 1 을 0 으로 만드는 방식이든
index+1 과 같게 만드는 전략을 써도 된다
100101
000101 (index 1 을 0 으로 바꿈)
111001 (index 4 를 0 으로 바꿈)
000111 (index 5 를 index 6 와 동일하게끔 바꿈)
111111 (index 3 을 index 4 와 동일하게끔 바꿈)
000000


또는, 1 과 0 을 alternate 하는 숫자 만큼 flip 하고, 마지막 수가 1 이면 한번 더 flip 해야 하는 방식으로 최소 flip 의 수를 찾아낼 수도 있다.

100101
1=>0=>1=>0=>1 + 1 = 5 번의 flip


여기서 다시 생각해보자
Q. 마지막 1 들을 0 으로 바꿔가는 방식으로 optimal 한 방법을 찾을 수 있다는 것을, 확신할 수 있는 다른 방법이 있는가?


아마도 일반적인 접근 방법은 다음과 같다.
마지막 n 번째와 n-1 번째 수를 생각해보자. N 번째 수는 1이다.
마지막 1 을 flip 해야 되니, optimal 한 방법에는 마지막 1을 flip 하는 과정이 포함되어 있다. 
그렇다면, n-1 번째가 n 과 같이 1 이라면, n-1 번째는 더이상 flip 할 필요가 없고,
N-1 번째가 0 이라면 n 의 1 을 flip 하기 위해 n-1 이 1이 되니, 이 1 을 뒤집기 위해 flip 해야 한다.

따라서 
c(n-1) = c(n) +1 (if num[n-1] != num[n])
c(n-1) = c(n) (if num[n-1] == num[n]

dynamic programming 방식으로 답을 찾게 해준다.


그런데, 위 생각에는 다음의 가정이 포함되어 있다고 볼 수 있다.
마지막 1 을 먼저 뒤집는 것이 아니라 
마지막이나 중간에 뒤집는 방식으로 더 좋은 방법을 찾아낼 수는 없다. 

Q. 이 가정을 확인하는 것이 필요해 보이는데.. 직관이 떨어져서 저 가정을 떠올려보고 의심하게 되는건지 잘 모르겠다..
당황하면 이것을 의심하고 있다는 것을 자각하기도 어렵다.
아마도 내가 DP 에 좀 더 익숙다면, 일단 저 방식으로 문제를 풀어보고, 그 생각이 맞다는 것을 확신하는 쪽으로 생각을 유도하지 않을까


그렇게 생각해보면,
배열의 마지막 1 의 자리 관점에서, 자신을 바꾸기 위해 필요한 flip 수는 1 이다
그리고 어느 optimal 한 flip permutation 에서든지 이 수를 0 으로 만들기 위한 1 flip 이 필요하다. (마지막 부터 바꿔나간다는 관점에서 생각하는 것이 아니라, 자리수의 관점에서 생각한다는 것이 다르다)
그리고 그 전 수는 DP 관계에 따라 최소 flip 카운트가 필요하다. 
그래서 optimal 한 flip 카운트를 DP 관계로 찾아낼 수 있다.
그리고 그 관계식을 보면 0-1 을 alternate 하는 수를 구하는 공식과 같게 된다.

역시.. 내가 DP 에 익숙하지 않아서, 어려운 쪽으로 생각을 가져갔나보다.


인터뷰를 목적으로 한다면, 
1. dynamic programming 에 좀 더 익숙해져서, 이런 의심을 안하고, 그 쪽 solution 이 머리에 잘 떠오르도록 한다.
2. 내가 현재 고민하고 있는 것이 무엇인지 명확하게 자각한다. 그리고 전달한다.
3. 내가 알고 있는 것과 모르는 것을 명확히 하고 해결해 나가야 하는데, 그것이 안된다면, 너무 공부가 부족하거나, 내가 해결할 수 없을정도로 너무 어려운쪽으로 가서 당황한 것인지 판단해보자
4. 아마도 나는 좀 과도하게 '증명' 할만한 것 쪽으로 관심을 두고 문제를 풀어가는 것 같으니, 조심해야 할 것 같다.



2d 로 넘어가서도 비슷한 생각들이 반복되어 필요할 것 같다. 

'자리수' 의 관점에서 보면, flip 의 permutation 순서와 상관없이, dp 관계가 최적의 flip 수를 찾아낸다는 것 추가..