문제 파악
분할 정복 유형이라는 것을 알고 접근했는데도 어떤 식으로 문제를 나눌 수 있는지 전혀 감이 오지 않았다. 분할 정복과 이전에 배운 단순한 재귀 호출을 통한 분할과의 차이점을 아직 완벽히 파악하지 못한 상태에서 문제에 접근하게 된것 같다.
압축을 먼저 전부 풀고 다시 압축을 하는 방식으로 생각해 봤는데 어떤 식으로든 중간 과정이 너무 복잡해져서 불가능하지 않을까라는 생각이 들어 손을 댈 수가 없었다. 문제를 작게 쪼개는 관점에 익숙해지지 않은것 같다.
올바른 풀이
문제 풀이의 핵심은 네 부분으로 나눌 때마다 같은 문제가 그대로 반복된다는 것이다. 이건 압축을 풀 때도 마찬가지고 상하로 반전시켜 다시 압축할 때도 마찬가지이다. 따라서 이 두 과정을 한번에 하는 것도 시간복잡도를 줄이는 데 핵심적인 아이디어이다.
네 부분의 상하를 반전시키고 다시 병합한다. 만약 네 부분 중 한 부분이 다시 네 부분으로 나뉘어져 있다면 그 부분에 대해서는 재귀 호출을 통해 또 상하를 반전시키고 병합시킨다. 이 과정을 계속해서 반복하면 결국 하나의 큰 화면을 상하 반전시키는 것과 똑같이 되는 것이다.
느낀 점
꽤 오랜 시간 고민했는 데도 전혀 해결책에 접근하지 못한 가장 큰 이유는 해결법을 접근하는 과정에서 문제를 더 작은 부분으로 나눌 수 있다는 데에 집중한 것이 아니라 수학 문제나, 퀴즈처럼 어떤 핵심적인 아이디어를 생각해 내면 풀 수 있지 않을까 하고 너무 큰 부분에 매달려 있어서 그랬던게 아닌가 하는 생각이 든다.
막상 해결책을 완전하게 이해하고 다시 보니 정말 간단하고 쉽게 생각해 낼 수 있는 아이디어 처럼 느껴졌는데, 이러한 관점의 차이에 익숙해 지는 것이 알고리즘 풀이를 능숙하게 하는 데에 필수적인 역량일 것이다.
