fccva   2년 전

인터넷을 뒤져보아도 왜 최적해인지, 왜 변환할 수 없는지 나오지 않아서 고민해보았습니다.

전공이 이 쪽이 아니라 틀린 내용이 있을 수도 있습니다.

도움이 되길 바랍니다.

1. 알고리즘 정리

A와 B의 row, col 크기는 3이상이라고 하겠습니다.

(row, col 중 하나가 3보다 작다면, 변환을 할 수 없으므로 성분이 모두 같거나 하나라도 다른 경우만 고려하면 됩니다.)

boolean[][] check 배열을 하나 만들어서, check[i][j] = A[i][j] != B[i][j] 라고 하겠습니다.

뒤집을 3 by 3 부분행렬을, 가장 맨 왼쪽 위의 인덱스로 나타내겠습니다.

즉 flip(rowIdx, colIdx) 라는 것은, check[rowIdx + i][colIdx + j] 를 모두 뒤집는 함수입니다. (i, j = 0, 1, 2)

그 다음에 check 배열을 왼쪽 위부터 순회하면서 check[i][j]가 true이면 flip(i, j)를 합니다.

for (int i = 0; i < row - 2; i++) {

    for (int j = 0; j < col - 2; j++) {

        if (check[i][j]) {

            flip(i, j);

        }

    }

}

check 배열의 0 <= i < row - 2 && 0 <= j < col - 2 부분은 위의 과정을 통해 모두 false가 됩니다.

이 과정을 모두 거쳤을 때 check[][] 배열은 두 가지 상태가 됩니다.

1) 0 <= i < row - 2 && 0 <= j < col - 2 "이외"의 부분도 모두 false.

2) 이외의 부분에 true가 적어도 하나 있음.

1)의 경우에는 A에서 B로의 전환이 성공한 경우로, flip이 호출된 횟수를 세서 출력하면 됩니다.

2)의 경우에는 A에서 B로의 전환이 실패한 경우입니다.

2. 두 가지 의문점

1) 1-1)에서, 이것이 진짜 최적해일까?

2) 1-2)에서, 다시 잘 뒤집으면 check배열 성분이 모두 false가 될 수도 있지 않을까?

Lemma1) G를 flip 함수들의 집합이라고 하고 g1, g2를 G의 원소라고 하면

(1) g1g2 = g2g1

(2) g1g1 = identity (항등함수)

pf) (1) 모든 i, j에 대해 (g1g2A)[i][j] = (g2g1A)[i][j]임을 체크하면 됩니다.

(i, j)는 g1의 flip 영역에만 속하던지, g2의 flip 영역에만 속하던지, 둘 다 속하던지, 둘 다 속하지 않던지, 네 가지 경우입니다.

각각의 경우를 적용하면 쉽게 확인할 수 있습니다.

(2) g1g1 = identity는 같은 걸 두 번 뒤집었으니 원래대로 됩니다.

Lemma2) f, g를 flip을 유한번 적용하는 함수이고

영역 0 <= i < row - 2, 0 <= j < col - 2에서 f(A)[i][j] = g(A)[i][j]라면 f = g이다.

(즉, 위의 영역에서만 같고 다른 부분에선 다른 경우는 없다.)

pf) 일반성을 잃지 않고 g가 항등함수일 때만 보여도 충분합니다.

왜냐하면 g도 flip을 유한 번 적용한 함수이고, flip 함수는 자기 자신이 역함수이기 때문에

f(A) = g(A)는 , g^(-1)f(A) = gf(A) = A과 동치이고, gf를 f로 치환하여 생각하면 되기 때문입니다.

f는 flip을 유한 번 적용한 함수이기 때문에 G의 원소 g1, g2, ... gk에 대하여 f = g1g2...gk라고 할 수 있습니다.

Lemma1에서 교환법칙이 성립한다고 했기 때문에, gi = flip(rowIdx, colIdx)에서 (rowIdx, colIdx)의 사전식 오름차순으로 g1...gk를 재배열 할 수 있습니다.

Lemma1에서 g^2 = identity라고 하였으므로, 짝수 번 나오는 것들은 모두 소거되고, 홀수 번 나오는 것들은 1개로 소거할 수 있습니다.

재배열하고 소거한 것을 다시 g1...gk라고 합시다. (소거되지 않고 남은 게 있다고 가정합시다.)

g1...gk(A)[i][j] = A[i][j] (for all 0 <= i < row - 2 && 0 <= j < col - 2) 입니다.

g1 = flip(rowIdx, colIdx)라고 가정합시다.

g1...gk(A)[rowIdx][colIdx]는 A[rowIdx][colIdx]를 flip한 것입니다.

사전식으로 정렬하여 재배열 하고 중복된 걸 소거했기 때문에 giA[rowIdx][colIdx] = A[rowIdx][colIdx] (i >= 2)이기 때문입니다.(사전식으로 gi가 뒤에 있기 때문에 (rowIdx, colIdx)를 뒤집을 수 없습니다.)

따라서 영역에서 값이 같다는 사실에 모순입니다. 이것은 "소거되지 않고 남은게 있다고 가정"했기 때문에 생기는 모순입니다.

따라서 f는 항등함수입니다.

Lemma2에 의해 두 번째 의문점은 해소됩니다.

왜냐하면 flip을 유한번 해서 0 <= i < row - 2 && 0 <= j < col - 2 영역에서의 값이 결정되면 그것이 유일하기 때문입니다.

(그 영역을 유지하면서 flip을 다시 유한 번 시켜도 영역 이외의 부분은 바꿀 순 없습니다.)

위 영역이 모두 false이기 때문에, 나머지 영역은 자동으로 결정되고 따라서 모두 false가 아니라면 변환이 불가능한 경우입니다.

첫 번째 의문점을 해소해봅시다.

g1...gk를 A에서 B로 변환시키는 최적 경로라고 합시다.

Lemma1에서 교환법칙이 성립하므로 재배열하여도 최적해입니다.

flip은 역함수가 자기자신이므로, Lemma2의 증명과정처럼 재배열했을 때 소거되는 것이 없을 것입니다.

소거되는 것이 있다면, 최적해는 그것이 되기 때문입니다.(더 적은 횟수로 변환 가능하므로 모순)

사전식 오름차순으로 재배열했기 때문에, g1 = flip(rowIdx, colIdx)라고 하였을 때,

(rowIdx, colIdx)보다 이전에 있는 인덱스들은 최적해 과정(g1...gk)에서 flip이 되지 않습니다.

따라서 g1은 가장 처음 값이 다른 인덱스에 대해서 flip을 수행합니다.

g1...gk가 A를 B로 변환하는 최적함수라면

g2...gk는 g1A를 B로 변환하는 최적함수입니다.(만일 g1A를 B로 변환하는 더 짧은게 존재한다면, 그것에 g1을 합성한 함수가 g1...gk보다 짧은 최적해(A -> B)가 되므로 모순입니다.)

g2도 마찬가지로 g1A와 B에서 가장 처음 값이 다른 인덱스에 대해서 flip을 수행하는 함수입니다.

이것을 계속 반복하면 위의 알고리즘과 같은 수행방법입니다. 따라서 첫 번째 의문점이 해소됩니다.

3. 왜 그리디인가?

"값이 다른 것의 개수"를 기준으로 움직인다고 생각하면 그리디가 아닙니다.

변환 과정에서 "다른 값의 개수"가 더 많아질 수 있기 때문입니다. 그것을 기준으로 놓고 보면 부분최적이 아닙니다.

그러나 Lemma1의 사실을 알고 있다면, flip의 순서는 상관없고 최적해에는 중복으로 flip하는 것이 없다는 사실을 알고 있다면,

위의 알고리즘 과정이 "이제 flip을 하지 않을 곳"의 개수를 늘린다고 생각하면 될 거 같습니다.

만일 A[0][0] != B[0][0] 이라면 flip(0, 0)을 합니다. 그리고 (0, 0)은 이제 "flip을 하지 않을 곳"에 추가됩니다.

flip 하지 않을 곳을 점점 늘려나가니까 그걸 기준으로 보면 부분적으로 최적이고, 그리디라고 볼 수 있을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.