구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.
📚 목차
1. 문제 해결 과정
2. 문제 해결 전략
1. 문제 해결 과정
6️⃣ 단계 문제 해결 알고리즘
1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 게획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
1️⃣ 문제를 읽고 이해하는 단계
문제 설명을 꼼꼼히 읽어서 문제가 원하는 바를 확실하게 알아야 한다.
사소한 제약 조건도 잘 읽자.
2️⃣ 재정의와 추상화
프로그래밍에서 추상화란, 현실 세계의 개념을 우리가 다루기 쉬운 수학적/전산학적 개념으로 옮겨 표현하는 과정이다.
자신이 다루기 쉬운 개념을 이용해 문제를 자신의 언어로 풀어써야한다.
어떻게 풀어쓰냐에 따라 어려운 문제를 쉽게 만들 수도 있고, 쉽게 해결할 수 있는 문제를 어렵게 만들수도 있다.
예를 들면 아래와 같다.
철수가 집에서 학교까지 가기 위한 경로와 각 경로마다 소요되는 시간 등이 주어졌을 때, 가장 빠르게 학교에 도착하는 경우는 무엇일까?
고민해야 할 점들이 너무 많겠지만, 이 문제에서 본질은 결국 '최단 거리'를 구하는 것이다.
Source(철수), Sink(학교), Edge(경로), Cost(소요시간), Vertex(경유지) 등의 전산학적인 개념으로 치환해서 생각하면 문제가 보다 직관적으로 바뀐다.
3️⃣ 계획 세우기
문제를 어떻게 해결할지 계획을 세워야 한다.
사용할 알고리즘과 자료 구조를 선택한다.
4️⃣ 계획 검증하기
계획을 검증해야 한다.
우리가 설게한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 한다.
5️⃣ 계획 수행하기
프로그램을 작성해야 한다. 정확하고 효율적인 방식으로 구현해야 한다.
6️⃣ 회고하기
문제를 해결한 과정을 돌이켜 보고 개선해야 한다.
문제를 한 번 더 풀면, 더 효율적인 알고리즘을 찾거나 더 간결한 코드를 작성할 수도 있고, 같은 알고리즘을 유도할 수 있는 더 직관적인 방법을 찾을 수도 있다.
효율적인 회고 수행 방법은 문제를 풀 땜다 코드와 함께 자신의 경험을 기록으로 남기는 것이다.
간단한 해법, 어떤 식으로 문제에 접근했는지, 해법을 찾는 데 결정적이었던 깨달음은 무엇인지 기록하면 좋다.
한 번에 맞추지 못한 경우에는 오답 원인을 적으면 좋다. 오답 노트를 적다 보면 자신이 자주 틀리는 부분을 알게 되고 실수를 줄일 수 있게 때문이다. 회고를 위한 또 다른 좋은 방법은 같은 문제를 해결한 다른 사람의 코드를 보는 것이다. 그러면 자신이 생각하지 못했던 통찰을 얻을 수도 있다.
문제를 풀지 못할 때
어떻게 해도 풀리지 않는 문제에 부딪혀 일정 시간이 지나도 답을 찾지 못할 때는 다른 사람의 코드나 풀이를 참조하는 것이 좋다.
하지만, 다른 사람의 코드나 풀이를 참조할 때는 반드시 복기해야 한다.
자신은 어떻게 문제에 접근했고, 왜 자신이 이 풀이를 못 떠올렸는지 살펴봐여 한다.
2. 문제 해결 전략
📍 직관과 체계적인 접근
직관은 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지 짐작할 수 있게 해준다. 직관을 발달시키기 위해서는 막막한 문제들을 해결하며 차곡차곡 경험을 쌓아 나가야 한다.
- 체계적인 접근을 위한 질문들
1. 비슷한 문제를 풀어본 적이 있던가?
형태가 비슷하거나 관련된 문제를 풀어 본 적이 있다면 이전에 적용했던 방법과 비슷한 접근 방법을 사용하여 문제를 풀 수 있다. 하지만, 기존에 접했던 문제가 온전히 경험이 되려면 그 원리를 완전히 이해하고 변형할 수 있어야 한다.
예) 철도망 위에서 두 도시를 잇는 가장 짧은 경로를 찾는 문제를 풀었는데, 이 문제의 해답 코드를 단순히 외우기만 하고, 원리를 완전히 이해하지 못했다면, 아래와 같은 변형 문제를 풀 수 없을 것이다.
- 한 도시를 두 번 방문하지 않으면서 가장 긴 경로를 찾는 문제
- 기차를 네 번 이하로 갈아타면서 가장 짧은 경로를 찾는 문제
- 역 간 운행 거리 중 가장 긴 구간이 가장 짧은 경로를 찾는 문제
- 역 간 운행 거리 중 가장 짧은 구간이 가장 긴 경로를 찾는 문제
- 가장 긴 구간과 가장 짧은 구간의 길이 차이가 가장 적은 경로를 찾는 문제
꼭 형태가 비슷하지 않더라도 문제의 목표가 같은 경우 이전에 적용했던 방법과 비슷한 접근 방법을 사용하여 문제를 풀 수 있다.
예) 어떤 사건의 발생 확률이나 경우의 수를 계산하는 문제들은 웬만하면 동적 계획법으로 해결할 수 있다.
문제의 목적을 보고 적절한 접근 방법을 선택하기 위해서는 어떤 문제가 최적화 문제인지, 경우의 수를 구하는 문제인지, 검색 문제인지 등을 분류하는 방법을 익히고, 각 알고리즘들이 어느 경우에 사용될 수 있는지 체게적으로 공부해야 한다.
- 단순한 방법에서 시작할 수 있을까?
비슷한 문제를 본 적이 없거나, 비슷한 문제의 해법이 곧장 적용되지 않을 때
먼저, 시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어보자. 즉, 일차적 목표는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 예방하는 것이다. 그 이유는 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문이다.
예) N(N<=30)개의 사탕을 세 명의 어린이에게 공평하게 나눠 주려고 한다. 공평함의 기준은 받는 사탕의 촐 무게가 가장 무거운 어린이와 가장 가벼운 어리간의 차이이다. 사탕의 무게는 모두 20이하의 정수이다. 가능한 최소 차이는 얼마일까?
~나중에 정리
- 내가 문제를 푸는 과정을 수식화할 수 있을까?
공부를 하다 보면 처음에 생각한 것과 완전히 다른, 새로운 방향에서 접근해야 풀리는 문제들도 만난다. 이렇게 번뜩이는 영감이 필요한 문제를 만났을 떄, 손으로 문제에 주어진 예제 입력을 직접 해결해 볼수 있다. 이 과정에서 알고리즘이 어떤 점을 고려해야 하는지는 알게 된다. - 문제를 단순화할 수 없을까?
주어진 문제의 좀 더 쉬운 변형판을 먼저 풀어보면 된다. 문제를 쉽게 변향하는 방법은 여러가지가 있는데, 문제의 제약 조건을 없앨 수도, 계산해야 하는 변수의 수를 줄일수도, 다차원의 문제를 1차원으로 줄여서 표현할 수도 있다.
예) ~~~ - 그림으로 그려볼 수 있을까?
문제에 관련된 그림을 그려보자. 두 개의 정수 쌍들을 다루는 문제가 있다면, 이 정수쌍을 2차원 평면 상의 좌표로 그려 보거나 직성 상의 구간들로 그려 보자. - 수식으로 표현할 수 있을까?
평문으로 쓰여 있는 문제를 수식으로 표현해보자. 수식을 전개하거나 축약하는 등의 순수한 수학적 조작이 문제를 해결하는 데 큰 도움을 줄 수 있기 때문이다. - 문제를 분해할 수 있을까?
더 다루기 쉬운 형태로 문제를 변형해보자.
예)
- 뒤에서부터 생각해서 문제를 풀 수 있을까?
문제에 내재된 순서를 바꿔보자. A에서 B로 가는 방법을 찾긴 어렵지만 B에서 A로 가는 방법을 찾기는 쉽기 때문이다. - 순서를 강제할 수 있을까?
순서가 없는 문제에 순서를 강제해서 문제를 풀어보자.
예) 격자 불 켜기 문제 - 특정 형태의 답만을 고려할 수 있을까?
순서를 강제하는 기법의 연장선으로 정규화 기법을 사용하자. 정규하란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법이다.
예) 원 덮기 문제
3장
