2. 문제 해결 전략

직관성 + 체계적인 접근.

 

---

 

직관성

가장 중요한 것. 문제와 답의 구조에 대한 직관성.

답안의 전체적인 모습을 직관적으로 머릿속에 그릴 수 있는게 가장 좋음. but 이게 안될 시 체계적인 접근이 필요함.

 

 

체계적인 접근

직관이 통하지 않을 때(문제를 봐도 모르겠을 때),

백지에서부터 시작해 문제를 해결하기 위한 기반을 차근차근 쌓아올리면서 점진적으로 전진하는 것을 의미.

 

 

---

 

체계적인 접근을 위한 질문들

 

 

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

• 형태가 비슷하거나 관련된 문제를 풀어본 적이 있다면, 이전에 접근했던 방법과 비슷하게 접근할 수 있음.
• 기존에 접근했던 방식이 온전히 경험이 되려면, 그 동작 과정과 원리를 완전히 파악해야함.
• 예제) 합친 LIS, 신호 라우팅, 음주 운전 단속, 선거 공약

 

---

 

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

• "무식하게 풀 수 있을까?" = 시간과 공간의 제약을 생각하지 않고 문제를 해결할 수 있는 가장 간단한 알고리즘을 만듬.
• 문제의 단순화 = 간단하게 풀 수 있는 문제를 너무 어렵게 생각하지 않는 것. 

 

 

---

 

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

• 번뜩이는 영감이 필요한 문제를 만났을 때
• 손으로 여러 간단한 입력(ex. 문제에서 주어진 예제 입력)을 직접 해결.
• 예제) Quantization, 두니발 박사의 탈옥, 실험 데이터 복구하기, 출전 순서 정하기, 마법의 약, 함정 설치

 

---

 

 

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

• 주어진 문제를 더 쉽게 변형하여 풀어보기.
• 원래 문제의 해법이 단순화된 문제 해법의 연장선에 있음.
• 예제) 비대칭 타일링, 드래곤 커브, 도시락 데우기, 어린이날, 근거리 네트워크

 

 

---

 

 

5. 그림으로 그려볼 수 있을까? = 도식화.

• 문제에 관련된 그림을 그림으로써, 문제 해결의 직관 얻음.
• 예제) 문자열 합치기, 너드인가 너드가 아닌가? 너드인가 너드가 아닌가?2

 

 

 

---

 

6. 수식으로 표현할 수 있을까?

• 글로 쓰인 문제를 수식으로 표현하는 것도 문제 해결의 직관을 얻을 수 있음.
• 예제) 수강 철회

 

 

---

 

7. 문제를 분해할 수 있을까? = 분할 해결.

• 한 개의 복잡한 조건을 여러 개의 단순한 조건으로 분해.
• 육상경기 기록 & 신문 기사 문제.

 

---

 

8. 뒤에서부터 생각해서 문제를 풀 수 있을까? = 순서 뒤집기.

• 문제에 내재된 순서를 바꾸거나 문제를 거꾸로 시작해서 올라감.
• 사다리 게임에서, 정답을 찾는 가장 효율적인 방법은 정답 사다리에서부터 거꾸로 올라가는 방법.
• 예제) 삽입 정렬 뒤집기, 감시 카메라 설치, Sorting Game

 

 

---

 

9. 순서를 강제할 수 있을까? = 순서 강제 기법.

• 순서 뒤집기의 연장선.
• 순서가 없는 문제에 순서를 강제하여 문제를 해결.
• 격자 불켜기 문제 -> 문제 내에선 순서가 없지만, 순서를 부여하여 각 칸을 켜는 형식으로 문제 해결.
• 예제) 게임판 덥기, 폴리오미노, 웨브바짐 

 

 

---

 

 

 

10. 특정 형태의 답만을 고려할 수 있을까? = 정규화.

• 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 후, 각 그룹의 대표들만을 고려.
• 순서 강제 기법의 연장선.
• 실선원과 점선원 문제.
• 경험을 통해 깨달아야 함.
• 예제) 소풍, 단어 제한 끝말잇기