알고리즘 문제를 잘 푸는 방법

알고리즘 문제를 잘 푸는 방법이 따로 있을까?

알고리즘 문제를 어떻게든 빨리 풀어보려고 요구 사항을 대충 슥 읽고 코딩에 들어가본 적이 있으신가요? 그 결과는 어떠셨나요?

정말로 그렇게 해서 성과를 거둔 상황보다는, 내가 짠 알고리즘에 대해 스스로도 이해하지 못한 채 코드로 옮기다 중간에 턱 막히거나 어찌저찌 완성하더라도 핵심 요구 사항을 빼먹는 경우가 대부분일 것이라고 생각합니다. 그러고 나면 왜 안되는 거지? 머리를 싸매다가 정답을 보고 여기 고치고 저기 고치고 해서 찜찜하게 마무리되고 맙니다.

 

실제 제가 겪었던 경험을 토대로 상황을 설명했지만, 이런 경험을 한 번이라도 해 본 적이 있다면 알고리즘 문제를 해결하는 데 있어 그저 마구잡이로 코딩에 들어가서는 안된다는 것에 대해 충분히 공감하실 것이라 생각합니다. 옛말에 '급할수록 돌아가라'라는 속담이 있는 것처럼, 꼼꼼하고 체계적으로 알고리즘을 설계하고 이해한 뒤 코드로 옮기는 것이 훨씬 더 알고리즘 문제를 더 잘, 더 빠르게 푸는 방법일 것입니다. 그렇다면 구체적으로 어떻게 알고리즘 문제를 풀어야 할까요?

 

이러한 알고리즘을 잘 푸는 방법론을 게일 라크만 맥도웰의 <코딩 인터뷰 완전 분석>에서 접해볼 수 있었는데, 이를 토대로 핵심적인 내용들을 정리해 보았습니다.

 

 

 

알고리즘 문제풀이 과정

1. 요구사항 이해하기(경청하기)

문제 설명과 관련된 어떤 정보든 집중해서 써 놓는(듣는) 단계입니다. 수능 문제에서 '지문에 곧 답이 있다!' 말하는 것처럼 알고리즘 문제에도 이와 마찬가지로 문제에 쓰여져 있는 모든 독특한 정보에는 그렇게 쓰인 이유가 있습니다.

 

예를 들어 '정렬된 배열 두 개가 있을 때..'라는 말은 데이터가 정렬되어 있다는 사실을 꼭 알아야 함을 의미합니다. 데이터가 정렬된 상황과 정렬되지 않은 상황은 최적의 알고리즘 작성에 있어사 천지차이기 때문이지요.

 

곧 문제를 풀다가 막혔거나 최적화하는 단계에 있다면 문제에서 주어진 정보를 모두 사용하고 있는지 다시 생각해 보아야 합니다. 이 때 필요한 정보들을 노트나 화이트보드에 정리해 놓는다면 이런 상황에서 유용하게 사용할 수 있습니다.

 

2. 예제 직접 그려보기(이해하기)

직접 예제를 그려 보면서 문제에 대한 이해도를 높이고 나아가 문제풀이에 대한 열쇠를 얻는 단계입니다. 저 같은 경우에는 스네이크 게임 구현 문제에서 잘 이해가 가지 않는 상황이 있었는데, 이 때 직접 노트에 보드판을 그려 게임을 진행해 보았던 것이 문제풀이에 큰 도움이 된 적이 있습니다. 그렇다고 아무 예제나 만드는 것이 무조건적으로 문제풀이에 도움이 되지는 않습니다. 좋은 예제의 조건은 아래와 같은 특징을 가지고 있습니다.

ㆍ 명확한 예제 : 문제에 맞는 실제 숫자 또는 문자열을 사용해야 합니다.

ㆍ 충분히 큰 예제 : 대부분의 예제는 충분히 큰 예제의 50% 정도밖에 안 되는 경우가 많습니다.

ㆍ 특별한 예제 지양 : 무심코 특별한 경우의 예제를 그리기 쉬운데, 큰 문제가 없어 보이더라도 이를 다시 만드는 것이 좋습니다.

 

3. 무식한 방법으로 일단 풀어보기

말 그대로 일단 풀어보는 것, 단순무식(brute force)하게 알고리즘을 설계하는 단계입니다. 너무 뻔해도 괜찮고, 너무 비효율적이더라도 상관없습니다. 일단 만들어내고 나서 이후에 알고리즘의 시간 및 공간복잡도에 따라 개선해 나가면 되기 때문입니다.

 

4. 최적화하기

BUD 최적화 및 다양한 방법을 적용해 최적의 알고리즘을 설계하는 단계입니다. 단순무식한 알고리즘의 어떤 부분을 개선해야 주어진 조건에 맞는 시간-공간 제한 안에 문제를 해결할 수 있는지 고민하고 적용해 봅니다.

ㆍ  BUD 최적화 : 병목 현상(Bottlenecks), 불필요한 작업(Unnecessary Work), 중복되는 작업(Duplicated Work) 으로 대표되는 알고리즘이 비효율적으로 동작하는 가장 흔한 이유 세 가지에 대해 이를 제거하거나 개선할 방법을 찾는 것을 의미합니다.

ㆍ  간과한 정보가 있는지 찾아보기

ㆍ  새로운 예제 만들어보기

ㆍ  시간-공간의 실익을 따져 균형 맞추기 (문제에 대한 추가 상태를 저장해 수행 시간을 줄이는 방법 등)

ㆍ 정보를 미리 계산해 두기 (정렬 등을 통한 데이터 재배치, 필요한 계산을 미리 해두는 방법 등)

ㆍ  해시테이블 사용하기

ㆍ  가능한 최선의 수행 시간(BCR) 고려하기

 

5. 검토하기

최적의 해법을 찾은 뒤, 이 알고리즘에 대해 세밀한 부분까지 알고 있는지 확인하는 단계입니다. 최적 알고리즘을 완성했다고 해서 바로 코딩에 뛰어들지 말아야 하는데, 잠시 생각하며 알고리즘에 대한 이해를 확실히 다지고 내 통제 하에 코드를 두어야 코딩하면서 코드에 휘둘리지 않을 수 있기 때문입니다.

 

어떤 변수를 사용하는지, 언제 값을 변경할 것인지 등 코드의 세세한 부분을 숙지함으로써 코드의 전체적인 구조에 대한 감을 잡아야 합니다.

 

6. 코드 작성하기

최적 알고리즘을 알고 있고, 정확히 어떻게 코딩해야 할지도 알고 있는 상태에서 아름다운 코드를 작성하는 단계입니다. 아래와 같은 요소들을 고려해 코드를 작성합니다.

ㆍ 모듈화된 코드 사용 (함수 분리 등)

ㆍ 에러 검증

ㆍ 필요한 경우 다른 클래스, 구조체 사용

ㆍ 좋은 변수명 사용

 

7. 테스트

구현한 코드를 제출하기 전 시험해 보는 단계입니다. 이 때 중요한 것은 기존 예제를 그대로 이용하는 것이 영리한 방식이 아닐 수 있다는 점입니다. 입력 예제들은 다 맞는데 제출하면 틀렸다고 나오는 경우가 꽤 있습니다. IDE 상의 코드를 시험하는 것이 아니라, 종이에 써 놓은 코드를 시험한다고 했을 때 기존 예제를 통해 손으로 직접 테스트를 한다고 상상해 보라. 시간 내에 구현한 코드를 검증하려면 그런 방식이 아니라 다음과 같은 방법을 사용해야 합니다.

 

ㆍ 개념적 테스트: 코드를 한 줄씩 읽어가며 어떤 일을 수행하는지 머릿속으로 테스트 돌려보기

ㆍ 특이하거나 표준적이지 않은 코드: 코드에 평소와 다르게 돌아가는 부분(x = length-2, i = 1부터 시작하는 for루프)들을 살펴보기

ㆍ 버그가 자주 발생하는 부분: 산술연산, null 노드 등이 있는 부분 다시 확인하기

ㆍ 작은 규모의 테스트: 원소 8개의 큰 배열보다는 3~4개의 작은 배열을 사용해도 같은 종류의 버그를 찾을 가능성이 크다.

ㆍ 특이하거나 극단적인 입력: Null, 단일 원소, 극단적인 입력 등 특별한 입력에 대한 테스트 진행하기

 

 

 

<참고 자료>

게일 라크만 맥도웰 (2017). 코딩 인터뷰 완전 분석: 189가지 프로그래밍 문제와 해법. 인사이트