[알고리즘 문제 해결 전략] 문제 해결 전략
알고리즘 문제 해결 전략
알고리즘을 공부하면서 문제에 대한 암기보다, 알고리즘 자체에 대한 개념을 학습하기 위해 읽기 시작한 책이다.
2장 문제 해결 전략
도입
무작정 알고리즘을 외우고 문제를 푼다고 해서 문제 해결 실력이 쌓이는 것은 아니다. (순간적인 암기에 불과STM)
문제 해결 능력은 프로그래밍 언어나 알고리즘처럼 명확히 정의된 실체가 없는 추상적인 개념이기 때문에 단순한 반복만으로 연마하기는 어렵다.
좋은 문제 해결자가 되기 위해서는 좀더 높은 차원의 수련이 필요하다.
이 수련의 목표는 문제를 푸는 것이 아니라 문제를 푸는 기술을 연마하는 것이다.
이를 위해서 자신이 문제를 어떤 방식으로 해결하는지 의식하고 어느부분이 부족한지, 어떤 부분을 개선해야 할지 파악해야 한다.
이 장에선 문제 해결 과정을 여러 단계로 나눠보고 각 단계를 더 잘하기 위한 여러 기술들을 소개한다.
문제 해결 과정
이 장에서 처음 소개할 내용은 현재 인류에게 가장 강력한 일반적 문제 해결 알고리즘이다.
저명한 물리학자 리처드 파인만이 처음 사용했다고 알려진 이 알고리즘은 다음과 같다.
- 칠판에 문제를 적는다.
- 골똘히 생각한다.
- 칠판에 답을 적는다.
반쯤 농담인 이 내용은 파인만은 어려운 문제를 잘 해결하는 것으로 유명했는데, 그는 번뜩이는 아이디어가 찾아올 뿐 그것이 어떻게 떠올랐는지 자신도 설명하기 어려워했다고 하여 파인만 알고리즘을 이에 빗대어 설명한다.
여기서 배울 점은 문제를 세분화하여 접근했다는 것이다. (단계별로 나누어)
문제를 세분화하는 것은 별거 아닌 것 처럼 보여도 어디가 부족하고, 어디를 개선해야 하는지가 명확히 드러나게 된다.
문제해결로 유명한 다른 책의 경우 문제 해결 과정을 다음과 같이 정의한다.
- 문제를 이해한다.
- 어떻게 풀지 계획을 세운다.
- 계획을 수행하여 문제를 해결한다.
- 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
회고가 추가되었다.
이 두 가지 접근 방법을 합쳐서 프로그래밍을 위한 여섯 단계 알고리즘을 만들어 본다.
- 문제를 읽고 이해한다.
- 문제를 익숙한 용어로 재정의한다.
- 어떻게 해결할지 계획을 세운다.
- 계획을 검증한다.
- 프로그램으로 구현한다.
- 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
1단계: 문제를 읽고 이해하기
문제 해결 알고리즘의 첫 번째 단계는 문제를 읽고 이해하는 것이다.
이 단계는 처음 참가하는 사람부터 과거 챔피언까지 모든 프로그래밍 대회 참가자들이 공통으로 하는 실수가 있다면 바로 문제를 잘못 읽는 실수이다.
가능한 한 빠른 시간에 문제를 풀어내야 하는 프로그래밍 대회에서는 조급한 마음에 문제를 곁눈질한 뒤 딸려오는 그림과 입출력 예제를 보고 문제가 원하는 것을 유추하기 십상이다.
2단계: 재정의와 추상화
두 번째 단계는 자신이 다루기 쉬운 개념을 이용해서, 문제를 자신의 언어로 풀어 쓰는 것이다.
이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요하며, 요구하는 바가 복잡한 문제일수록 그 중요성이 더해진다.
이 과정에서 중요한 일이 일어나는데, 바로 문제를 추상화하는 과정이다.
추상화란 현실 세계의 개념을 우리가 다루기 쉬운 수학적/전산학적 개념으로 옮겨 표현하는 과정이다.
현실 세계의 개념들은 너무 복잡하기 때문에, 현실 세계를 다루기 위해서는 어느 정도 본질만을 남겨두고 축약하여 다루기 쉽게 표현해야 한다.
이 과정을 추상화라고 한다.
우리에게 익숙한 문제 해결 도구들을 문제에 적용할 수 있는 계기가 된다.
이 추상화는 어떤 방식으로 재구성하느냐에 땨라 같은 일을 하는 프로그램이더라도 전혀 다른 문제로 받아들여질 수 있다.
어려운 문제를 쉽게 만들수도, 쉬운 문제를 어렵게 만들 수도 있다.
그러므로 실질적으로 추상화 과정이 프로그래밍이 나아갈 방향을 결정한다고 볼 수 있다.
어떤 부분을 추상화할 것인지를 선택하는 작업과 문제를 재정의하는 방법들에 대한 고찰은 좋은 프로그래머가 되기 위해 필수적인 과정이다.
3단계: 계획 세우기
문제 해결의 다음 단계는 문제를 어떻게 해결할지 계획을 세우는 것이다.
이 과정에서는 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.
사실상 이 부분이 문재 해결에서 가장 중요한 단계라고 할 수 있다.
자신이 알고 있는 알고리즘이나 자료 구조를 활용 한다면 단순한 문제는 쉽게 해결할 수 있다.
하지만 문제를 보고 바로 어떻게 해결해야 할지 떠오르지 않는 어려운 문제라면 이 과정에서 많은 고민을 하게 될 것이다.
4단계: 계획 검증하기
계획을 세웠다고 해서 곧징 키보드를 잡을 수 있는 것은 아니다.
구현을 시작하기 전에 계획을 검증하는 과정을 거쳐야 한다.
이 과정에서 설계한 알고리즘이 모든 경우에 요구 조건을 수행하는지 점검하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 한다.
5단계: 계획 수행하기
이와 같은 복잡한 과정을 거치고 나서야 이제 계획 수행의 수행, 즉 프로그램을 작성하는 단계에 들어설 수 있다.
아무리 천재적인 알고리즘을 고안하더라도 그 구현이 부정확하거나 비효율적이라면 프로그램은 정확히 동작할 수 없다.
6단계: 회고하기
문제 해결에 당장 직접적인 영향은 없지만 장기적으로는 큰 영향을 미치는 단계가 바로 회고이다.
회고란 자신이 문제를 해결한 과정을 돌이켜 보고 개선하는 과정을 말한다.
한 번 푼 문제를 다시 본다고 해서 배우는 것이 있을까 생각할 수 있지만, 오히려 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들은 다 배우지 못하는 경우가 많다.
두 번째로 풀 때는 더 효율적인 알고리즘을 찾거나 간결한 코드를 작성할 수 있고, 특히 이 장에서 다루는 문제 해결 기술은 외워야 할 의사코드도, 엄밀한 증명도 없는 추상적인 기술이기에 이들을 연마하기 위해선 끊임없이 자신이 이 기술들을 어떻게 사용하고 있는지를 돌아보는 것이 필요하다.
효과적인 방법은 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것이다.
이때 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무었이었는지를 기록하면 좋다.
실제로 많이 기록하는 편인데 생각보다 더 많이 찾아본다.
반대로 오답의 원인이라도 꼭 적는 것이 좋다.
과거의 실수에서 배우기란 매우 어렵기 때문에 대개 한 실수를 반복하게 되는데, 오답 노트를 적다 보면 자신이 자주 틀리는 부분을 알게 되고 결과적으로 실수를 줄일 수 있다.
회고의 또 다른 좋은 방법은 같은 문제를 해결한 다른 사람의 코드르 보는 것이다.
비슷한 알고리즘으로 해결한 사람의 코드도 백이면 백 모두 다르기 마련이다.
가른 방식으로 문제를 해결한 것을 보면 자신이 생각하지 못했던 통찰을 얻을 수 있다.
문제를 풀지 못할 때
물론 이 문제 해결 알고리즘이 만능은 아니다.
이 방법을 적용해 모든 문제를 척척 풀어나갈 수 있다면, 지금 이런 책이 나오지 않았을 것
누구나 어떻게 해도 풀리지 않는 문제에 부딪히기 마련으로 이런 경우에는 절대로 답안을 참조하지 말라는 조언도 있지만, 초보 시절엔 너무 한 문제에 매달리는 것도 좋지 않다.
일정 시간이 지나도 답을 찾지 못할 땐, 다름 사람의 소스 코드나 풀이를 참고하는 것도 좋은 방법이다.
단, 다른 사람의 코드나 풀이를 참조할 때는 반드시 복기를 동반해야 한다.
자신이 문제를 해결할 때 취했던 접근들을 되새겨 보고 자신이 왜 이 풀이를 떠올리지 못했는지 살펴봐야 한다. (분석)
주의
단계의 구분은 어디까지나 생각을 돕기 위한 도구로 경험이나 자신의 생각대로 이를 적용하면 된다.
문제 해결 전략
자신이 알고 있는 기술을 직접적으로 적용할 수 있는 단순한 문제의 경우에는 상관 없지만 어려운 문제일수록 다양한 방법을 시도해 보면서 답안을 찾아야 한다.
여기에서는 우리가 사용할 수 있는 가장 일반적인 전략들을 몇 가지 소개한다.
직관과 체계적인 접근
문제 해결 전략에서 가장 먼저 강조해야 할 것은 문제와 답의 구조에 대한 직관의 중요성이다.
직관은 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작할 수 있게 해준다.
이와 같이 답안의 전체적인 얼개를 머릿속에 그릴 수 있으면 문제를 반쯤 해결할 것이나 마찬가지다.
애초에 문제를 보자마자 어떻게 풀어야 할지 안다면 이 책을 보고 있을 이유가 없다..
직관 또한 시간이 지나면서 발달하는 것이고, 직관을 발달시키기 위해선 얼핏 보기엔 막막한 문제들을 해결하며 차곡차곡 경험을 쌓아 나가야 한다.
체계적인 접근을 위한 질문들
다음은 문제를 해결할 때 유용한 질문들의 목록으로, 많은 문제에 적용될 수 있는 강력한 질문들부터 그 사용처가 제한되는 질문들의 순서대로 배열되어 있다.
비슷한 문제를 풀어본 적이 있던가?
형태가 비슷하거나 관련된 문제를 풀어 본 적이 있다면, 이전에 적용했던 방법과 비슷한 접근 방법을 사용할 거라고 예측할 수 있다.
물론 단순 문제만 많이 푼다고 해서 그것이 다 경험이 되지는 않는다.
따라서 기존에 접했던 문제가 온전히 경험이 되려면 그 원리를 완전히 이해하고 변형할 수 있어야 한다.
단순한 방법에서 시작할 수 있을까?
비슷한 문제를 본 적이 없거나, 비슷한 문제의 해법이 적용되지 않는다면 대부분은 무식하게 풀 수 있는지 검증헤야 한다.
시간과 공간의 제약을 생각하지 않고, 가장 단순한 알고리즘을 설계하는 것이다.
이 전략의 일차적 목표는 간단하게 풀 수 있는 알고맂므을 만들어 보는 것이다.
물론 단순한 방법으로 풀릴 리는 없다.
이 방법의 유용한 진짜 이유는 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문이다.
이런 경우 효율적인 알고리즘을 기반으로 사용하거나, 계산 과정에서 같은 정보를 두 번중복을 게산하지 않는 등의 최족화를 사용하여 알고리즘을 개선할 수 있다.
점직적 개선을 통해 문제를 풀 수 없더라도 단순한 방법을 생각해보는 데는 나름 의미가 있다.
내가 문제를 푸는 과정을 수식화할 수 있을까?
물론 점진적인 접근 방식이 만능은 아니다. (하지만 효과는 있다.)
공부를 하다 보면 처음에 생각한 것과 완전히 다른, 새로운 방행에서 접근해야 풀리는 문제들도 만나게 된다.
이렇게 번뜩이는 영감이 필요한 문제를 만났을 때 시도할 수 있는 방법 하나는 손으로 여러 간단한 입력, 예제를 입력하느 것이다.
문제를 단순화할 수 없을까?
또 다른 강력한 문제 해결 도구는 주어진 문제를 좀더 쉬운 변형판을 먼저 풀어보는 것이다.
문제를 쉽게 해결하는 방법은 여러가지다.
문제의 제약조간을 없앨 수도 있고, 계산해야 하는 변수의 수를 줄일 수도 있다.
다차원의 문제를 1차원으로 줄여서 표현할 수 있다.
그림으로 그려볼 수 있을까?
문제의 해법에 대한 직관을 얻을 수 있는 도 다른 방법은 문제에 관련된 그림을 그려보는 것이다.
많은 사람들의 사고 체계는 숫자 나열보다 기하학적 도형을 더 직관적으로 받아들이기 때문이다.
이것은 꼭 문제가 기하학을 다루지 않더라도 유용하다.
수식으로 표현할 수 있을까?
가능한 한 직관을 얻기 좋은 방향을 사고를 전개하는 다른 접근 방식과는 반대로, 평문으로 쓰여진 문제를 수식으로 표하는 것도 도움이 되는 경우가 있다.
수식을 전개하거나 축약하는 등의 순수한 수학적 조작이 문제를 해결하는 데 큰 도움을 줄 수 있기 때문이다.
문제를 분해할 수 있을까?
또 다른 접근 방식은 더 다루기 쉬운 행태로 문제를 변형하는 것이다.
이 기술의 대표적인 예로 문제의 제약 조건을 분해하는 방법이 있다.
이 방법은 문제에 주어진 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해한다.
한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽기 때문에 종종 유용하다.
뒤에서부터 생각해서 문제를 풀 수 있을까?
또 다른 유요한 문제 변형 기법은 문제에 내재된 순서를 바꿔 보는 것이다.
이 기법을 사용할 수 있는 전형적인 예로 사다리 게임이 있다.
사다리 게임의 경우 원하는 답변을 위해 가장 쉬운 답을 도출해내는 방법은 거꾸로 올라가는 것이다.
즉, 이 기법처럼 문제의 순서를 바꿔서 푸는 것이 더 쉬운 경우가 많다.
순서를 강제할 수 있을까?
순서를 뒤집는 방법으로 순서가 없는 문제에서 순서를 강제하여 문제를 푸는 방법이다.
예제의 내용처럼 체스판의 불켜기 문제의 예시
스스로 순서를 (문제와 상관없는) 강제, 제약하여 좀 더 쉽게 문제에 접근함
특정 형태의 답만을 고려할 수 있을까?
순서를 강제하는 기법의 연장선으로 정규화 기법이 있다.
정규화란 답변해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만 고려하는 방법이다.
느낀점
2장은 1장과 다르게 책을 읽는 도중 여러번 다시 읽어야 할 부분이 많았다.
문제 해결 과정의 6단계를 지키고 문제를 푸는지, 접근하기 어렵다면 문제 해결 전략을 사용하여 다양한 방식을 사용해볼 수 있다.
이런 책 특징은 항상 다시 읽을 수 있어야 한다는 점이다.
따라서 지금 정리해놓은 내용을 토대로 어디가 부족한지 판단하고 다시 책을 열어볼 용기를 가져보자.
댓글남기기