들어가면서

저는 컴퓨터학부 과정을 2학년까지 하고, 신체건강한 대한민국 남성이라면 많은 사람들이 끝냈거나, 현재 하고 있거나, 곧 하게될 군 생활을 하고 있습니다.

분명 입대할 때는, 코딩공부 절대 놓지 말아야지 하면서, 코딩용으로 쓸 태블릿도 하나 마련해서, 코딩과 함께할 군생활을 계획하였고, 일병 초반때 까지 백준 문제를 열심히 풀면서, 백준 문제 난이도를 매겨서, 자신이 푼 문제를 경험치화해 티어를 보여주는 solved.ac 기준으로 플래티넘을 찍자 하고 결심까지 했건만, 중간에 휴가를 위한 정보처리산업기사 공부와, 기타 여러가지 하면서 나중에 해야지 하고 미루고 미루었던, "블로그에 내가 공부했던걸 정리하기"를, 특히 "내가 책을 통해서 공부 하면서, 이해가 잘 안되거나, 추가적으로 궁금해서 구글링으로 찾아본 몇몇 자료들을 정리" 하는것을 velog라는 좋은 서비스를 알게된 오늘 바로 적어보려고 합니다.

저는 똑똑한 친구들과는 달리, 대학에 들어오기 전 컴퓨터 프로그래밍 관련 지식은 초등학교때 잠깐 만졌던 플래시의 Actionscript 몇번 깔짝대본것이 전부이고, 대학에서도 대회 등 대외적 활동이란걸 많이 안하였고(왜 안했는지 아직도 후회중), 그렇다고 해서 매우 비상한 머리를 가지고 있지도 않아, 주변의 코딩 잘하는 친구들 사이에서 부끄럽지 않을수 있도록 컴공인 사이에서의 바이블인 구종만 선생님께서 지으신 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략"(일명 종만책)을 한권 구입해서, 시간 될 때마다 읽어볼려고 노력 했습니다 만...... 문명에 빠져서 잘 못했습니다...... 이 글을 읽는 여러분들은 문명 같은 마성의 게임에 과몰입 되지 않도록 주의해 주세요

아무튼, 상병을 달고 몇개월 지나고, 삶의 여유도 일병때 보다는 좀 더 생기고, 코로나 때문에 자격증 시험이고 뭐고 날라가서, 다시 종만북을 한번이라도 완독 해보자 하는 생각으로 열심히 읽었고, "아무튼 완독"을 한 기념으로 이때까지 공부를 하면서 느꼈던 것들을 정리해 보고자 합니다.

1. 개인적으로 중요하다 생각해 가지고 가야겠다는 내용들
2. 공부하면서 궁금해져서 추가로 찾아본 내용들
3. 이해가 잘 안되서 찾아본 설명들의 모음

이 글과, 앞으로 쭉 적어갈 글들을 통해서, 이 책으로 알고리즘을 공부하면서 저와 비슷한 점들을 느끼고 있는 분들에게 많은 도움이 되었으면 합니다. 최대한 쉽게 적어서, 초심자 분들도 부담없이 읽을 수 있는 글이 되었으면 좋겠습니다.

제 2장 : 문제 해결 개관

이 책은 제목대로, 프로그래밍 대회를 위해서 공부할것을 상정하고 쓰여진 책이기 때문에, 제 1장은 책을 읽을 때의 참고사항이나, 대회를 준비할 수 있는 여러 사이트를 소개하는 내용으로 이루어져있고, 2장부터 "알고리즘"관련 내용이 나오기 시작 합니다. 이 책 2.3장 문제 해결 전략에 나오는 대표적인 문제 풀이 전략 몇가지를 정리해 보고자 햡니다.

1. 예전에 풀었던 비슷한 문제를 응용해서 풀 수 있는가?

대개 많은 공부에서도 적용되는 방법입니다. 고등학교때 열심히 수학 공부를 했다면, 시험에 나올법한 "유형" 들을 숙지하기 위해서 많은 문제를 푸셨을 것 입니다. PS도 다르지 않습니다. 사실 프로그래밍을 통한 문제해결이라는 것이, 문제를 보고, 어떤 알고리즘과, 어떤 자료구조를 통해서 문제를 빠른 시간 내에, 효율적으로 풀어낼 수 있는가의 문제 아니겠습니까? 물론 한 문제를 풀기 위한 알고리즘 학습을 위한 공부를 할 때, 정확히 어떤 방식으로 이 알고리즘이 돌아가는가를 숙지 해야지, 기존의 문제와 비슷한 문제를 볼 때, 어떠한 것을 수정해서 문제를 풀 수 있을지, 아니면 아예 접근 방식을 달리해서 문제를 풀어야 할 지 알 수 있으니까요. 이 책에서는 유명한 LIS(최장 증가 수열) 문제를 변형한 합친 LIS 라는 문제가 있고, 이 문제는 원래 LIS 문제를 어떻게 푸는지 잘 숙지하고 있으면 쉽게 풀 수 있는 문제이지요.

2. 단순한 방법으로 풀 수 있을까? (Brute Force)

제가 군 입대 전, 자기계발을 위해서 학교 도서관에 몇시간씩 앉아 있으면서 노트북 한대와, 학교 카페에서 산 아메리카노 한잔과 함께 문제를 풀어본 적이 있었습니다. 백준 1107번 문제 리모컨 이라는 문제였는데요, 그 당시 저는 문제를 풀다가 든 여러 직관적인 번뜩임에 의존해서 열심히 몇시간을 투자해 가면서 제 코드의 문제 때문에 생긴 "런타임 에러" 들이나, "틀렸습니다"를 받아가면서, $O(logN)$의 시간 복잡도를 만들어서 뿌듯했던 기억이 있습니다. 하지만, 그 문제는 단순한 브루트 포스 방식으로 풀 수 있는 문제였고, 그때 저는 만약 이것이 어떠한 시험에서 나온 문제였다면, 시간을 엄청나게 부어서 최적화 한 것이 그렇게 시험장에서 의미가 있었을까 하는 생각이 들었던 적이 있습니다. 이 책에서도

복잡한 알고리즘을 고생고생해서 작성한 뒤에야 간단하고 느린 알고리즘으로도 충분하다는 것을 깨닫는 순간의 슬픔은 겪어보지 않으면 모릅니다.

라고 하는데 정말 맞는 말입니다.

이 이야기를 하는 이유는, 여러분들이 프로그래밍 공부를 하면서, 메모리를 1바이트라도 아끼고 싶고, 시간복잡도를 어떻게든 낮추어, 프로그램 수행 시간을 1밀리초라도 줄이고 싶어, 시험장에서 안타까운 시간을 허비해 버릴수도 있지 않을까 해서 한 말입니다. 머리를 덜 굴리고 나올 수 있는 직관적인 방법으로도 해결할 수 있는 문제를, 다른 문제에 투자할 수 있었던 귀중한 시간을 뺐어가면서 문제의 필요사항 이상으로 최적화를 하는것이 그렇게 의미가 있는 행동으로 해석되기는 힘들 것입니다. 또한, DP로 일컬어지는 동적 계획법 등의 알고리즘이나, 그 변형들 또한, 이 "단순하게 풀기"에 기초해서 문제를 풀어나가기 때문에, 결코 경시해서는 안되는 부분이기도 합니다.

물론 모든 문제를 그냥 보이는대로 직관적인 단순한 방법으로 풀 수는 없습니다. 하지만 뒤에서 소개되는 여러 테크닉등을 이용해서 점진적으로 문제 풀이 코드를 최적화 해 나가면 의외로 괜찮은 속도 향상을 가져올 수 있습니다. 예를 하나 들어보겠습니다.

$N(N\le30)$개의 사탕을 세명의 어린이에게, 가장 많이 받는 아이와 가장 적게 받는 아이의 사탕의 무게의 합의 차가 최대한 적게 배분 하려고 한다. 사탕의 무게는 모두 20이하의 정수 일 때, 가능한 최소의 차이는 얼마인가?

직관적으로 생각해 봅시다. 각 사탕을 모두 나눠주는 방법의 수는 $3^N$입니다. N이 30일때, 이 값은 약 205조나 되는 엄청난 큰 수라서, 1초에 1억번 정도의 연산을 한다고 가정하는 주먹구구 식에 따르면 제 시간안에 문제를 풀기에는 힘들어 보이는 숫자입니다. 하지만, 실제로 받은 사탕의 종류가 달라도, 무게의 합이 같은 경우가 생기면, 문제에서 물어보는 "무게의 차이"의 입장에서 볼 때는, 그 경우들에 유효한 차이가 없을 것입니다. 이 점을 이용해서, 각 어린이가 가진 사탕의 개수와, 가지고 있는 사탕의 무게의 합을 저장하는 배열을 만들면, 사탕의 가능한 무게의 가짓수는 $0$부터 $20\times N+1$ 까지니까, 배열의 크기는 $(20\times N + 1)^3 \le 601^3$(약 2억) 정도 되겠지요. 코드로 적어보면

arr[20*N+1][20*N+1][20*N+1]

정도일것 같네요. 확실한건 위의 205조 보다는 숫자가 확 줄었다는 것입니다. 이는 앞에서도 말한 동적 계획법이라는 여러번 방문하는 상태에 대해서 정보를 배열에 저장해, 조금 더 빠르게 문제를 푸는 방법에도 쓰이니, 공부 하면서 익숙해 져야 할 것들중 하나가 되겠습니다.

3. 푸는 과정을 수식화 하기.

앞에서 소개한 단순하게 푸는 방법은 나름 강력한 도구이지만, 모든 문제를 풀어낼 수는 없습니다. 문제 푸는 과정을 수식화해서 수학 문제 풀듯 하여, 필요한 값을 도출하는 식을 만들어 낸다면, 미분 등의 방법을 통해서 원하는 식의 값을 빠르게 찾아 낼 수도 있을 것이고, 푸는 과정을 수학적으로 나타낸다면, 단순히 식을 전개하고, 축약하고 하는 등의 여러 수학적인 성질을 이용해서 알고리즘을 더욱 빠르게 하여 시간 제한을 통과하는데 많은 도움을 줄 수 있을 것입니다. 그렇게 문제를 정리하다 보면, 간단한 문제 두개로 분리가 될 수도 있구요.

이 책에서 수식화를 통해서 빠르게 풀어낼 수 있는 문제는 두니발 박사의 탈옥 문제를 들고 싶습니다. 주어진 문제 상황이 마코프 연쇄라는것을 이용해 행렬의 곱셈으로 문제를 척척 풀어내는 코드를 보면 정말로 감탄사가 나옵니다.

4. 문제를 단순화 해보기

주어진 문제를 푸는 방법이 직관적으로 떠오르지 않을때, 문제의 제약 조건 일부를 완화시킨 문제를 만들어 그 문제를 푸는것은 원래 문제를 푸는데에 도움이 됩니다. 2차원 격자위에 N개의 점이 각각 다른 위치에 있을때, 그 점들간의 거리를 최소로하는 점을 찾는 문제를 생각해 봅시다. 각 점들을 x축과 y축으로 사영하여 우리가 알고 싶은 점 X의 x좌표와 y좌표를 알 수 있고, 이 정보 두개를 조합하면, 우리가 필요한 정보를 알 수 있습니다. 물론 이런 경우는 흔치 않지만, 단순화된 문제를 풀면서, 원래 문제에 필요한 직관을 얻어낼 수 있습니다. 도시락 데우기 문제를 이 책에서 풀 때, 문제의 조건을 완화한 문제를 풀고, 거기서 얻은 직관을 원래 문제풀이에 사용해서 문제를 푸는 것을 볼 수 있습니다.

5. 문제의 순서를 바꿔보기

사다리게임에서 내가 원하는 지점으로 가기 위해서 시작점을 찾아야 한다고 합시다. 그러면, 다들 아마, 종점에서부터 맨 위까지 거슬러 올라가볼 것입니다. 이런 것들을 문제 해결에서도 비슷하게 사용할 수 있습니다. 중고등학교때 여집합을 이용해 푼 문제 같은 그런 문제도 이러한 방법을 사용할 수 있겠죠

6. 순서를 강제하기

순서가 없는 문제에 순서를 강제하는 방법도 있습니다. 이렇게 말하면 약간 아리송할 수 있으므로 바로 예제를 하나 들고오겠습니다. 5x5 LightsOut이라는 간략한 게임인데, 이 게임에서 한 칸을 클릭하면 그 칸과, 상하좌우로 인접한 칸의 상태가 반전됩니다. 불이 켜져있으면 꺼지고, 꺼져있으면 켜지는 식이죠. 이 게임을 하다보면 몇가지를 깨달을 수 있습니다.

• 어떤 순서로 칸을 클릭하건 상관이 없다
  • 각 칸의 상태는 자신 그리고 자신과 인접한 칸이 몇번 클릭되었는지에 따라서 결정되지, 순서는 딱히 상관이 없습니다.
• 한 칸을 두번 이상 클릭할 필요가 없다
  • 당연한 말입니다. 두번 누르면 안누른것과 같으니까요

단순히 이 게임을 푸는 코드를 작성할 때, 각 칸을 누를지 말지를 결정하는 식으로 코드를 작성한다면 필요한 연산의 수는 $2^{25}$입니다.
하지만 "왼쪽에서 오른쪽으로, 위에서 아래로" 라는 제약을 추가해서 코드를 짠다면 이야기는 조금 달라집니다. 임의의 칸 X의 왼쪽 칸이나, 위쪽 칸이 불이 꺼져있는 상태이고, 아까 말해둔 조건대로 진행했을때 X를 누를지 말지 결정하는 시간이라고 해봅시다. 만약에 X를 누른다면, X의 왼쪽이나 위쪽에 있는 칸은 불이 켜질 것이고, 이 불은 다시 끄지 못할 것입니다. 방향이 정해져있으니 돌아갈수 없으니까요! 맨 위의 칸의 모든 경우의 수인 $2^5$만 시도해 보면, 밑에 있는 칸들은 위의 제약 조건 때문에 결정이 됩니다. 그런식으로 해서 마지막 줄이 불이 다 꺼져 있으면 성공이고, 안되면 맨 윗줄 불을 다른 방식으로 꺼보고 하는 것이죠. 직접 풀어보고 싶은 분은 백준 14939문제를 풀어보는것도 좋을것 같네요.

이건 여담인데 모든 light out 퍼즐이 해결 가능한것은 아니라고 합니다.

마무리

최대한 쉬운 말로 써보려고 노력하고, 직접 머리속에 들어갈 수 있도록 최대한 많은 수단과 방법을 동원해서 글을 써야지 하고 생각을 했는데, 생각대로 잘 되지가 않네요. 이 방법들이 사실 어떠한 문제를 보면서 "아 이 문제는 어떠어떠한 기법으로 풀어야지" 이런식으로 되는것이 아니라, 이러한 기법들을 머리에 담아서, 문제를 풀 때 생각이 나는 정도면 될것 같다고 개인적으로는 생각합니다. 주변에 코딩 도사라 할만한 친구들 이야기를 들어보면 공통적으로 하는 말이 "문제를 많이 풀어라"고, 저도 이에 대해서 많은 공감을 합니다. 물론 실천을 잘 하고 있느냐에 관해서는.... 혹시 이 글에 관해서 질문이나 기타 하실 말씀이 있으시면 부담없이 댓글 달아 주세요. 개인 SNS를 많이 해보지 않아서 글 쓰는데 좀 미숙한 부분이 있을 수 있습니다만, 너그럽게 봐 주셨으면 합니다. 제 글 끝까지 읽어주셔서 감사합니다!

참고 자료

https://boycoding.tistory.com/210 [소년코딩]