[Algorithm Strategies] 1-2. 문제 해결 개관

코딩 처음 시작할 때 오기로 읽었던 책이었는데, 다시 보니 새롭다.

그 때는 거의 절반 이상을 이해하지 못 하고 넘겼는데, 최근에 다시 읽어보니 너무 많은 내용을 놓치고 지나갔던 것 같아 다시 차근차근 읽어보기로 했다.

정리하는 게 습관이 되어서 포스팅을 하긴 해야 하는데 저작권법에 접촉되지 않는 선에서...최대한 내 의견을 중점으로 써야할 것 같다. 문제 생길 시 바로 내리겠습니다. 🥲

목차
1. 문제 해결 과정
2. 문제 해결 전략

---

1. 문제 해결 과정

 

작년에 썼던 이 글의 내용과 거의 동일하다 보면 된다.

알고리즘 문제를 풀면서 생각해보아야 할 것들

문제 해결 과정을 가장 큰 4단계로 나누면 다음과 같다.

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선 방법이 있는지 찾아본다.

 

1️⃣ 문제를 읽고 이해하기

모두에게 주의하는 내용이지만, 모두가 흘려 들었다가 낭패를 입는 단계다.

문제를 잘못 읽거나, 궁극적인 문제 혹은 제약 조건들을 잘못 이해한다면 옳은 결과를 절대 얻을 수 없다.

설명을 공격적으로 읽어서 문제가 원하는 바를 '완전히' 이해하는 과정이 반드시 필요하다.

 

2️⃣ 재정의와 추상화

프로그래밍에서 추상화란 결국, 현실 세계의 모든 문제를 다룰 수는 없으니 본질만을 남겨두고 나머지는 축약하여 다루는 것이다.

그렇다면 '무엇을' '어떻게' 다룰지가 중요한데, 구체적으로 따지자면 이런 것이다.

 

철수가 집에서 학교까지 가기 위한 경로와 각 경로마다 소요되는 시간 등이 주어졌을 때, 가장 빠르게 학교에 도착하는 경우는 무엇일까?

고민해야 할 점들이 너무 많겠지만, 이 문제에서 본질은 결국 '최단 거리'를 구하는 것이다.

Source(철수), Sink(학교), Edge(경로), Cost(소요시간), Vertex(경유지) 등의 전산학적인 개념으로 치환해서 생각하면 문제가 보다 직관적으로 바뀐다.

 

3️⃣ 계획 세우기

가장 중요하면서 쉽지 않은 단계다. 보통 여기서 막히거나, 어려워서 건너뛴다. :(

계획이 잘못되면 아무리 열심히 코드를 짜도 시간을 땅에 내다버리는 셈이니 절대 그러지 말자..

 

익숙한 접근법으로 해결 가능한 문제들의 경우 쉽게 해결할 수 있겠지만, 그렇지 않은 경우가 분명히 존재한다.

하지만 세상의 모든 알고리즘을 다 외우고 다닐 수는 없는 셈이니, 그럴 때는 포기해야 할까?

절대적인 방법이 있는 것은 아니지만, 해결하기 위해 고민해볼 수단들은 몇 가지 존재한다. 이 내용은 뒤에서 보다 자세히 다룰 것이다.

 

4️⃣ 계획 검증하기

전 단계에서 세운 계획이 타당한가를 고민해보아야 한다.

사실 모든 문제를 해결할 수 있는 기적의 알고리즘이 하나 존재하긴 한다. 바로 bruth force(전탐색) 알고리즘이다.

모든 경우의 수를 무식하게 뒤지니 해결 못할 문제는 없지만, 시간 복잡도 얘기가 나온다면 달라진다.

 

애초에 로직에 치명적인 결함이 있을 수도 있고, 문제는 없지만 시간/공간 복잡도에서 통과하지 못할 가능성이 있다.

이 판단은 구현을 하고 난 후에 하기에는 시간을 너무 많이 빼앗긴다. 꼭 검증 단계에서 걸러내야 한다.

 

5️⃣ 계획 수행하기

계획이 아무리 완벽해도 구현하지 못하면 의미가 없다.

즉, 논리력과 구현력 모두 뒷받침 되어야 문제를 해결할 수 있다는 의미다.

물론 단순 구현 문제의 경우엔 순수 구현력으로 승부가 나기도 한다.

 

이 과정도 '그냥 돌아가기만 하면 되는 거 아니야?'라고 생각할 수 있지만, 정말 많은 것들을 생각해볼 필요가 있다.

단순히 문제 해결을 위해서만이 아니라, 개발자로서 많은 것을 깨우칠 수 있는 단계라고 생각한다.

 

6️⃣ 회고하기

이건 실전에서 써먹기 보다는 공부할 때 필요한 단계다.

회고하는 게 중요하다는 걸 익히 들어서 ,알고는 있지만 안 하는 사람이 많다.

그도 그럴 것이 한 번 본 걸, 굳이 공을 들여서 또 들여다 본다는 건 생각보다 유쾌하지 않은 일이다.

 

나도 솔직히 이 과정을 게을리 했었는데, 블로그에 정리하기 위해서 지금까지 풀었던 모든 문제들을 다시 훑어본 적이 있었다. 그런데 놀랍게도 그 과정에서 잊어 먹었던 내용, 새롭게 보이는 내용, 그 때는 이해 못했거나 잘못 이해한 내용들이 너무 많았다는 걸 느꼈었다. (심지어 당시엔 완벽했다고 느꼈음에도 불구하고) 

 

다른 사람의 코드를 읽어보거나, 스터디를 통해서 아이디어를 공유하는 학습은 정말 소중한 자산이 된다.

절대 소홀히 여길 만한 단계가 아님을 명심하자.

 

✒️ 문제를 풀지 못할 때

모든 문제에 만능인 알고리즘은 없다.
골드 단계만 넘어가도 대부분은 기존 알고리즘의 응용 단계고, 플래티넘 이상은 두 말 할 것 없다.
문제를 직접 풀기 전에 절대 답안을 참조하지 말라는 이야기도 있고, 일정 시간이 지나도 갈피가 안 잡히면 참조해도 된다는 의견이 분분하지만, 내 생각은 뭐가 됐건 제대로만 하면 된다고 생각한다.

절대 답안을 참조하지 않기로 했으면, 그 문제를 풀기 위해 미친 듯이 몰두해라.
일정 시간이 지나면 답안을 참조한다는 원칙을 세웠다면, 참조한 코드를 온전히 내 것으로 만들 수 있을 때까지 완벽하게 분석해라.
뭐가 됐든 애매하게 이도저도 아닌 상태만 아니면 된다.

---

2. 문제 해결 전략

 

📌 직관과 체계적인 접근

문제를 읽고 알고리즘이 대략적으로 어떤 형태를 가질지 짐작할 수 있다면, 문제를 반쯤 해결한 것이다.

다만 이러한 문제와 답의 구조에 대한 직관력을 위해선 정말 많은 노력이 필요하다. (혹은 천재 ㅋㅋ)

막막한 문제들을 해결해나가며, 다양한 실패와 해결 경험들을 차곡차곡 쌓아나가면 직관력은 필연적으로 발달한다.

 

그렇다면 막막한 문제들을 마주쳤을 때, 직관이 아직 발달하지 못했다면 어떻게 해야 할까?

아이디어가 떠오를 때까지 장시간 앉아 있는 것도 방법이 되긴 하겠지만, 보다 체계적으로 접근할 수 있다.

백지에서부터 시작하여, 문제를 해결하기 위한 기반을 쌓아올리는 것이다.

문제의 요구 사항, 내가 가진 정보, 내가 가질 수 있는 정보, 그 정보들을 어떻게 다룰 것이며, 어떠한 논리적 접근으로 문제를 해결해나갈지를 가장 무식한 방법부터 떠올려보는 것이다.

 

물론 그렇게 한다고 언제나 해답이 나오는 것은 아니지만, 이렇게 축적한 경험은 절대 무시할 수 없다.

 

📌 비슷한 문제를 풀어본 적이 있던가?

형태가 비슷하거나 관련된 문제들을 접하면, 이전과 비슷한 접근 방법으로 풀릴 확률이 높다.

물론 기존에 사용한 알고리즘의 원리를 완벽히 이해하고 있고, 이를 변형할 수 있다는 가정하에 말이다.

 

철도망 위에서 두 도시를 잇는 가장 짧은 경로 문제를 풀기 위한 수많은 표준 알고리즘을 모두 외웠다고 가정하자.

그렇다고 해서 다음과 같은 변형 문제를 해결할 수 있을까?

• 한 도시를 두 번 방문하지 않으면서 가장 긴 경로를 찾는 문제
• 기차를 네 번 이하로 갈아타면서 가장 짧은 경로를 찾는 문제
• 역 간 운행 거리 중 가장 긴 구간이 가장 짧은 경로를 찾는 문제
• 역 간 운행 거리 중 가장 짧은 구간이 가장 긴 경로를 찾는 문제
• 가장 긴 구간과 가장 짧은 구간의 길이 차이가 가장 적은 경로를 찾는 문제

이 중에는 최단 경로 문제를 응용해서 풀 수 있는 것도, 그렇지 않은 것도 있다.

이들을 구분하기 위해서는 최단 경로 알고리즘을 단순히 알고 있는 게 아니라, 동작 과정과 원리를 완전히 이해하고 있어야 한다.

 

추가로 내가 말하려고 했는데, 책에서도 언급하고 있는 동적 계획법(Dynamic Programming) 이야기도 있다.

보통 경우의 수나 어떠한 일이 발생할 확률을 물으면 대부분 동적 계획법 문제에 해당한다.

다만, cache를 다루는 방법이 각양각색이라는 것이 문제다.

이를 구분하기 위해서는 단순히 문제를 해결하는 것보다도, 사용한 로직을 온전히 내 것으로 만들었는지가 핵심이 된다. 

• 합친 LIS (문제 ID: JLIS, 8장 연습 문제)
• 신호 라우팅 (문제 ID: ROUTING, 30장 연습 문제)
• 음주 운전 단속 (문제 ID: DRUNKEN, 30장 연습 문제)
• 선거 공약 (문제 ID: PROMISE, 30장 연습 문제)

 

📌 단순한 방법에서 시작할 수 있을까?

이건 친구가 처음에 내게 주입했던 방법인데, 그 친구가 이 책을 보고 내게 주입한 내용이니 사실상 이 책을 공부한 것이 되는 건가? ㅋㅋㅋ

 

해법이 곧장 떠오르지 않을 때는 "가장 무식한 방법"부터 떠올리는 것이 좋다.

전탐색 기법은 모든 문제를 통과할 수는 없을 지언정, 적어도 시간/공간 복잡도 제약만 없다면 어쨌든 모든 문제를 해결할 수 있다.

그리고 순차적으로 최적화, 자료구조 선택 등을 통해서 점진적으로 개선시키는 것이다.

 

책에서는 N(<=30)개의 사탕을 세 명의 어린이에게 공평하게 나누어주는 문제를 예시로 들고 있다.

공평함의 기준은 사탕의 총 무게가 가장 무거운 아이와, 가장 가벼운 아이의 차이로 결정된다. (사탕 무게는 20이하 정수)

1. 완전 탐색은 3^N개의 방법을 만든다. → 중복을 제거해보자
2. 아이가 가진 사탕 총량을 상태 공간으로 하는 BFS는 \((20 * N+1)^{3} <= 601^{3}\) 크기의 배열을 만들어야 한다. → 추가 조건들을 고려해보자
3. 사탕 무게는 20이하 정수이므로, 무게가 가장 무거운 아이와 가벼운 아이의 차가 20 이상인 경우에는 절대 최적의 답이 될 수 없다. 따라서 사탕을 가장 많이 받은 어린이가 \(\frac{20 * N}{3} + 20\) 넘게 사탕을 받는 경우를 무시하면 \( (\frac{20*N}{3}+30)^{3} <= 220^{3} \)으로 줄일 수 있다. → 여기서 더 최적화할 수 있다.
4. (200, 190, 180)이나 (180, 190, 200)이나 동등하다. 따라서 오름차순 정렬되어 있는 경우만을 탐색하자. 그렇다면 최종 탐색 경우는 1/6로 줄어든다.

결과적으로 처음 상태에 비해 검사해야 할 상태의 수가 1억분의 1로 줄어들었다.

 

📌 내가 문제를 푸는 과정을 수식화할 수 있을까?

위의 방법으로 풀리지 않는 경우가 있다. 아예 뭐랄까..색다른 발상의 전환이 필요한 문제들?

나는 알고 했던 방법은 아니지만, 책에서는 이런 경우 문제에 대한 결과를 직접 해결해보는 것이라고 한다. 

노가다? 그거 내 전문 분야야!

대회에서 써먹기는 조금 무리긴 하지만, 난 대회에서도 도저히 접근 방법이 안 떠오르면 이거라도 하고 있다.

그런데 가끔 이 방법이 먹힐 때가 있다. 크크.

그리고 오히려 문제 이해 단계에서 빠트린 중요한 키 포인트를 상기할 수 있기도 해서, 안정적인 방법이다.

• Quantization (문제 ID: QUANTIZE, 8장 연습 문제)
• 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 8장 연습 문제)
• 실험 데이터 복구하기 (문제 ID: RESTORE, 9장 연습 문제)
• 출전 순서 정하기 (문제 ID: MATCHORDER, 10장 연습 문제)
• 마법의 약 (문제 ID: POTION, 14장 연습 문제)
• 함정 설치 (문제 ID: TRAPCARD, 32장 연습 문제)

 

📌 문제를 단순화할 수 없을까?

"2차원 배열로 풀어야 할 것 같은 문제를 1차원 배열로 단순화할 수 없을까?"와 같은 종류의 질문이다.

유명한 N-Queen(BOJ-9663)을 예시로 들 수 있다.

 

이 문제는 이차원 배열에 DFS 탐색으로 해결해야할 것 같지만 실제로 그럴 필요는 없다.

어차피 하나의 행에는 하나의 queen만 놓여질 수 있으므로, 열을 의미하는 1차원 배열에 값으로 column값을 할당해주면 같은 의미로 해석할 수 있다.

 

• 비대칭 타일링 (문제 ID: ASYMTILING, 8장 연습 문제)
• 드래곤 커브 (문제 ID: DRAGON, 9장 연습 문제)
• 도시락 데우기 (문제 ID: LUNCHBOX, 10장 연습 문제)
• 어린이날 (문제 ID: CHILDRENDAY, 29장 연습 문제)
• 근거리 네트워크 (문제 ID: LAN, 31장 연습 문제)

 

📌 그림으로 그려볼 수 있을까?

이거 개인적으로 정말 중요하다고 생각한다.

나처럼 숫자에 강한 사람이 아니라면, 최대한 내 방식대로 문제를 직관적으로 파악할 다른 수단을 찾아야 한다.

그리고 그 중 내게 가장 맞는 방법은 그림을 그려보는 것이다.

 

언제나 통하진 않는다. 기하학 문제야 그렇다 치더라도, 모든 문제가 그림으로 표현될 수 있을리도 만무하다.

나는 예전에 고층 빌딩(BOJ-1328)을 풀다가 경험했었는데, 숫자로만 썼을 때는 해결책이 안 보이다가 그림을 그렸더니 너무 쉽게 해결했던 경험이 있다.

 

• 문자열 합치기 (문제 ID: STRJOIN, 10장 연습 문제)
• 너드인가, 너드가 아닌가? (문제 ID: NERDS, 15장 연습 문제)
• 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2, 22장 연습 문제)

 

📌 수식으로 표현할 수 있을까?

내가 가장 못하는 영역이기도 하다.

정보 올림피아드 출전할 정도로 잘 하시는 분들은 뭐만 하면 죄다 수식화 해버리는데 경이로울 지경.

예를 들어, Vertex Cover 증명을 위한 평서문을 전부 수식화하여 공식으로 적어놓는 것도 봤다. 🙄

 

• 수강 철회 (문제 ID: WIRHDRAWAL, 12장 연습 문제)

 

📌 문제를 분해할 수 있을까?

하나의 복잡한 문제를 쉬운 여러 문제로 분할하는 경우다.

즉, 복잡한 조건들을 단순한 형태를 갖는 여러 조건의 집합으로 분리할 수 있는지를 따져보는 것이다.

 

N명의 육상 선수들의 best[], worst[]가 있는데, 모든 선수는 이 범위 안의 기록만 세운다고 가정하자.

만약, 선수 i는 j에게 반드시 패배하면서, 선수 i와 j가 서로 상대에게 이길 가능성이 있는 기록의 집합을 확인하고자 한다면 어떻게 해야할까?

• !(worst[j] <= best[i]) : 선수 i의 기록 구간은 언제나 j보다 뒤에 있다.
• !(worst[i] <= best[j]) : 선수 i와 j의 기록 구간에는 교집합 영역이 있다. (가능성 존재)

 이를 정리하면 (best[j] < worst[i]) && (best[i] < worst[j])라고 할 수 있다.

 

📌 뒤에서부터 생각해서 문제를 풀 수 있을까?

Top-down 방식이냐, Bottom-up 방식이냐를 묻는 것이다.

Fireworks(BOJ - 12736)에서는 루트에서 리프 노트까지 내려가는 방식은 정보의 희박성이나, 너무 많은 경우의 수로 인해 탐색이 힘들다. 이럴 때는 리프 노드에서 거슬러 올라가는 방식을 택하는 것이 적절하다.

 

• 삽입 정렬 뒤집기 (문제 ID: INSERTION, 22장 연습 문제)
• 감시 카메라 설치 (문제 ID: GALLERY, 28장 연습 문제)
• Sorting Game (문제 ID: SORTGAME, 29장 연습 문제)

 

📌 순서를 강제할 수 있을까?

순서를 뒤집는 것과는 달리, 순서가 없는 문제에 순서를 강제하는 방법도 있다.

음~ 이건 직접 풀어보는 게 좋다고 생각한다. 뭔가 특별하다기 보단 너무나도 당연한 접근법?

 

문제를 해결하는데 있어서 순서가 명확히 정해져 있지는 않은데, 일의 중복을 걸러야 하는 경우를 생각해보면 된다.

• 게임판 덮기 (문제 ID: BOARDCOVER, 6장 연습 문제)
• 폴리오미노 (문제 ID: POLY, 8장 연습 문제)
• 웨브바짐 (문제 ID: ZIMBABWE, 9장 연습 문제)

 

📌 특정 형태의 답만을 고려할 수 있을까?

순서를 강제화 하는 기법의 연장선으로 정규화(canonicalization) 기법이 있다.

정규화란 우리가 고려해야 할 답들 중에서 형태는 다르나, 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법이다.

따라서 어떤 답이 주어지더라도 이것을 특정 형태의 답으로 바꿀 수 있는 변형 과정을 찾아야 한다.

(유용하긴 한데, 깨닫기까지의 경험과 공부량이 만만치 않다...나도 이 정도 단계까진 아직 한참 멀었다.)

 

책의 예시에서는 점선 원들을 모두 덮을 수 있는 실선 A 원의 중심 위치를 묻고 있다.

무한대의 경우의 수에서 A의 중심 위치를 찾기란 힘들지만, 어쨌든 모든 원을 덮기만 하면 된다.

즉 어떠한 점선 원에도 맞닿아 있지 않은 실선 원도 되지만, 두 개의 점선 원과 맞닿아 있는 실선 원도 괜찮다는 이야기다.

이렇게 되면 답이 하나라도 존재했을 때, 두 개의 점선 원과 접한 답 또한 반드시 존재함을 의미한다.

 

두 점선원과 A의 반지름만 주어진다면, A의 중심은 해봐야 2개의 경우밖에 나오지 않는다.

이 모든 후보들 중에서, 점선 원을 모두 덮는 경우를 찾으면 문제를 해결할 수 있다.

• 소풍 (문제 ID: PICNIC, 6장 연습 문제)
• 단어 제한 끝말잇기 (문제 ID: WORDCHAIN, 28장 연습 문제)

 

 

 

algospot.com :: JMBook 문제들 링크