BOJ 9177 단어 섞기

단어 3개가 주어지는데, 첫번째 단어와 두번째 단어를 섞되 원래의 각 단어내에서 알파벳의 순서는 변하지 않도록 해서 세번째 단어를 만들 수 있는지 판단하는 문제이다.

단어들을 각각 str1, str2, str3라고 하면
나는 str3의 뒤에서 부터 한 글자씩 str1, str2의 뒤의 글자와 비교하면서 모든 경우를 다 해보는 식으로 접근했다.
str3[idx3]와 str1[idx1], str2[idx2]을 비교해보고 같다면 각각의 경우를 다 보는 식으로 해서 재귀를 이용해서 구현했는데 이렇게 할 경우 O( 2의 400(str3의 길이)제곱 )의 시간 복잡도를 갖게 된다. 그래서 memoization을 이용해야 한다.

근데 문제의 데이터가 약해서인지 O(2의 N제곱) 구현이 통과됐다. 그것도 0ms만에... (참고로 memoization을 이용한 다른 분들의 코드는 대부분 4ms이상) 처음에는 통과되서 좋아했는데, 생각해보니 절대 시간내에 들어올 수가 없는 시간복잡도라... 내가 직접 예제를 넣어봤다.
최악의 경우를 테스트하기 위해 aaaa... aaaa... aaaaaaaa... 이런식의 예제를 넣어봤다.
str3의 길이가 30만 되어도 10억을 넘기때문에 대충 30 - 40을 길이로 하면 몇초가 걸려야 하는데, 1초도 안걸려서 바로 나왔다. 그래서 처음엔 나도 모르게 엄청 효율적인 알고리즘을 짠 것인가...라는 생각을 잠시 했지만 아무리 생각해봐도 그럴리 없는 코드이다. 그래서 재귀함수 안에 printf를 넣어서 어떻게 돌아가는지 살펴보기로 했다. 하지만 그리 쉽지 않았다. 엄청 헷갈리고.. 그래서 예제를 줄여서 해보고 printf를 이곳 저곳 다 찍어보고 ...예제도 바꿔보고 하면서 알게 된 사실 하나가 답이 yes가 나와야하는 예제에 대해서는 생각과 달리 엄청 빨리 나오는데, no가 나와야하는 예제에 대해서는 생각한대로 정말 느리게 나온다는 것이다.
printf로 출력하는 것도, no가 나와야하는 예제는 끝날 기미를 안보인다. 정말 2의 N제곱만큼 보는 것 같아보인다. 하지만 yes가 나와야하는 예제는 입력이 아무리 길어도 조금만 출력되고 끝난다.
아마 Baekjoon Online Judge의 데이터는 최악의 경우를 가정한 데이터도 yes가 나오는 경우만 넣어놓은 것이 아닐까... 그건 그렇고 왜 저런 처이가 발생할까?
여기저기 printf를 해보면서 과정을 따라가다보니 함수가 호출되지 않는 경우가 발생했다는 것을 알 수 있었고, 정말 감사하게도 순간적으로 short circuit evaluation이 떠올랐다!!!

short circuit evaluation! || 연산이나 && 연산에서 왼쪽 부분에 따라 오른쪽 부분이 뭐가 오든간에 결과는 같을 경우, 오른쪽 부분 계산을 하지 않고 넘어가는 것인데, 바로 이 것 때문에 yes가 나와야하는 경우에 왼쪽이 true가 되어 || 오른쪽은 살펴보지 않고 넘어갔고 그래서 매우 빠르게 나왔던 것이다. 반면에 no가 나와야하는 경우는 false가 왼쪽에 있어서 오른쪽까지 다 보게된 것이다...

그래서 하나 또 실험을 해봤는데,true, false를 판별하는 경우에는 |나 ||나 똑같기 때문에 |를 써봤다. 참고로 |(bitwise | operator)는 short circuit evaluation이 적용되지 않는다. 역시 ||를 썼을 때 매우 빠르게 나오던 예제에 대해서도 매우 느리게 나온다.
그리고 궁금해서 찾아봤는데 참고 : bitwise operator는 short circuit evaluation이 적용되지 않는 이유
다양한 답변들이 있는데, 내가 이해한 답변을 하나 소개하면, 0*x에 대해서도 0*를 하는 경우가 거의 없고 다른 경우가 많기 때문에 short circuit evaluation이 적용되지 않듯이 bitwise &이나 bitwise |의 경우 대부분의 경우 short circuit evaluation을 쓸 경우가 많지 않기 때문에(대부분 그냥 bitwise 연산) 그런 것 같다.

그리고 또한, short circuit evaluation의 side effect(부작용)에 관한 것들도 눈에 띄었는데, 제대로 찾아보지는 않았지만 나중에 찾아보면 좋을 것 같고, 조금 찾아본 바로는 나의 경우에서 처럼 디버깅을 해볼 때, 매우 헷갈린다든지, 시스템 프로그래밍 같은데서 command에 해당하는 코드가 실행되지 않을 수 있다든지 하는 문제가 있어서 주의해서 코딩해야 한다고 한다.

이제 dp로 어떻게 구현할 것인지에 대해 생각해보자.
내가 처음에 이렇게 완전탐색으로 구현하기 전에도 dp로 구현하려고 했었는데,
d[idx1][idx2] = 단어1을 idx1까지, 단어2를 idx2까지 사용했을 때, 단어3에대해 가능한지 아닌지.
하지만 이렇게 하면, memoization해놓은 것이 주어진 단어3에만 적용되는 것이라 새로운 단어3이 들어오면 안되지 않나...는 고민을 했는데, 내가 예제만 보고, 단어1, 단어2는 똑같은 것이 들어오고 단어3만 바뀐다고 착각해서 잘못 생각한 것 같기도 하고, 또한 완전탐색으로 해보고 디버깅하면서 엄청나게 많은 경우를 보기 전에는 memoizaion을 해도 다시 또 쓰일까? 라는 의문이 있었다. 즉 완전 잘못 생각하고 있었다. 처음에는 완전탐색도 O(N)으로 착각하고 있었다...실제로, 완전탐색을 자세히 들여다보면 먼저 재귀로 한 가지 경우를 끝까지 보고, dfs처럼 탐색하는데, 모든 경우를 다 보면서 처음에 봤던 경우를 또 봐야되는 경우가 생긴다.

아 그리고, 원래 코드에서는 배열의 인덱스가 -1까지 가버리는 경우도 있었다. idx3==-1인 경우만 기저사례로 처리하기 때문에, idx1이나 idx2가 음수가 되는 경우가 있었는데, 이 부분도 if문에 처리를 해줘야 한다.
그래서 이번에는 memoization을 이용해서 풀어보려고 한다.
구현하려 하면서 든 생각이, d[idx1][idx2]만으로는 부족해보인다. idx3의 정보도 알아야할 것 같다. 하지만 잘 생각해보면, idx3정보는 필요없다. idx1, idx2가 뭐냐에 따라 결정되기 때문이다. 그리고 d[idx1][idx2]에 해당하는 경우가 여러가지 있지 않나? 라는 생각이 들 수 있다. 하지만 어차피 하나의 단어3에 대한 memoizaion이기 때문에, d[idx1][idx2]가 참이라는 것은 단어3에대해 참이라는 것. 즉 d[idx1][idx2]는 단어3에 대해만 성립하는 것으로 생각하면 납득이 된다.

테스트케이스가 이상한건지... 내가 이상한건지... 실수로 메모이제이션을 빼먹었는데..정확히는 bool& ret= 에 받지 않고, bool ret=d[idx1][idx2]로 해버렸는데... 이러면 d[idx1][idx2]에 기록이 안될텐데... AC를 받았다. 다시 제대로 짜보려고 한다...

이번에는 제대로 했다고 생각한다..(확실치는 않다.) 일단 짜면서 idx1이나 idx2가 -1이 되는 경우를 처리하는데 애먹었다. 결국 d[200][200]에서 d[201][201]로 늘리고 d[len1][len2]로 놓고(idx대신 길이로..) 해결했다.
그리고 idx1이나 idx2가 -1이 되는 경우를 처리할 일이 없도록 index를 0부터 늘려나가는 식으로 구현해보려고 한다. 이렇게 구현해도 결국 idx1이나 idx2가 끝에 도달하는 경우를 신경써야하지만 -1이되는 경우를 처리하는 것보다는 좀 더 쉬운 것 같다. 그리고 이 방법 역시 끝부분을 처리하기 위해 d[201][201]로 늘렸는데, d[idx1][idx2]의 의미는 그대로 사용하면 된다.