Table of Contents
문제 읽기
간단한 문제가 아닌 이상, 많은 문제가 어떤 상황과 거기서 해결하고 싶은 문제를 제시하면서 ‘이것을 해결하는 코드를 짜라’고 한다. 문제를 처음 읽을 때 할 일은 그 상황과 해결하고 싶은 문제를 파악하는 것이다.
내가 주로 쓰는 방식은 한두 문장 정도로 문제를 간략하게 요약하는 것이다. 예를 몇 개 들어보자.
- softeer level2 GBC: 지정된 구간에서의 제한 속도와 시험 운행 기록이 주어진다. 운행 구간 중 제한 속도를 가장 많이 초과했을 때 제한 속도와 운행 속도의 차이를 구하라.
- softeer Level2 장애물 인식 프로그램: 정사각형인 2차원 배열이 주어진다. 0은 도로이고 1은 장애물이니 각 장애물마다 칸 수를 세고, 장애물의 개수와 오름차순으로 정렬한 각 장애물 당 칸 수를 출력하라.
- 백준 1107 리모컨: 10개의 숫자 버튼과 채널을 1씩만 바꿀 수 있는 +- 버튼이 달린 리모컨이 있는데, 숫자 버튼 몇 개가 고장났다. 기본값 100번 채널에서 원하는 채널로 이동하고자 할 때, 버튼을 눌러야 하는 가장 적은 횟수를 구하라.
- [LeetCode] 912. Sort an Array: 정수 배열
nums가 주어졌을 때, 배열을 오름차순으로 정렬하여 반환하라. 내장 함수를 사용하지 않고O(nlog(n))의 시간 복잡도와 가능한 가장 작은 공간 복잡도로 문제를 풀어야 한다.
상황을 파악하면서 예제도 같이 본다. 내가 요약한(= 이해한) 내용이 맞는지 확인하고 어떤 과정을 거쳐 답이 나오는지 파악한다. 문제 이해가 잘 안 될 때에도 예제로 이해하면 된다. 이때는 프로그램 생각을 할 필요는 없다. 사람이 이해하는 게 먼저다.
문제 파악과 계획
사람의 머리로 문제를 이해했으니 이제 컴퓨터식 생각으로 번역해야 한다. 구체적으로 무엇을 입력받는지, 무엇을 출력해야 하는지, 무엇을 저장할 건지, 대략 어떤 알고리즘으로 진행할 것인지 등을 생각해본다. 이 생각들을 한 번에 다 하긴 어려울 테고, 나는 나름의 순서가 있다(절대적인 순서는 아님).
- 사람의 생각은 어떤 과정으로 문제를 풀었는지 검토한다.
- 일단은 그대로 프로그램으로 구현한다고 생각해본다. → 여기서 알고리즘 초안이 나온다. 보통 내가 생각해내는 알고리즘 중에서는 가장 비효율적인 편이다.
- 불필요한 정보와 계산을 잘라낼 구석을 찾아보고 좀 더 나아 보이는 알고리즘을 구상한다.
- 구상한 것 중 먼저 시도해볼 것을 고른다.
- 선택한 알고리즘을 기준으로, 무엇을 저장해야 하는지 정한다. 메모리 사용량을 줄이기 위해 가능한 필요한 만큼만 저장할 수 있게 한다.
- (선택사항) 의사코드를 써본다. 매번 하는 건 아니고, 주로 머릿속으로 생각한 게 헷갈려서 과정을 다시 확인하고자 할 때 쓴다. 만약 썼다면 코드를 쓸 때 참고한다.
일단 돌아가는 코드 쓰기
알고리즘을 구상했고 계획까지 세웠다면 그 내용을 바탕으로 최소한 예제는 올바르게 실행되는 코드를 써본다. 보통은 예제를 기준으로 계획했기 때문에 여기까지는 된다. 예제에서도 틀린 부분이 나온다면 이유를 찾고 코드를 보수한다. 아직은 반례를 생각하지 않는다.
예제 실행이 정상적인 첫 번째 코드가 만들어졌다면 일단 제출해보고 틀리는지 본다. 안 틀렸다면 즐기면 되고, 틀렸다면 그때부터 반례를 찾으면 된다. 문제와 코드를 검토해서 조건이 빠진 부분을 찾아도 되고, 질문을 검색해서 다른 사람들이 찾은 반례를 넣어봐도 된다. 반례를 넣어볼 때는 디버깅 없이 실행해서 틀린 값을 확인한 다음, 왜 저런 값이 나오는지 예상해서 의심되는 코드에 중단점을 찍어놓고 디버깅한다. 모르겠다면 그냥 모든 과정을 디버깅하면 된다. 변수의 변화 과정에서 내가 의도하지 않은 일이 일어나는 곳이 반례 발생 이유가 된다.
- 반례를 찾았거나, 코드에서 틀린 이유를 찾았다면
- 반례를 따로 검수하는 코드를 추가하거나 조건을 바꾸어 반례가 걸러지게 한다.
- 반례를 검수하는 코드는 조금만 넣는다. 너무 많아지면 지금 쓰고 있는 알고리즘이 처음부터 이상한 방법을 시도하고 있었다는 뜻이다. 문제를 해결하는 알고리즘을 쓰는 게 맞지 반례를 하나하나 확인하고 걸러내는 코드를 쓰면 안 된다.
- 틀린 이유를 모르거나 반례 검수 코드가 너무 많아진다면
- 구상해놓은 다른 방법으로 새 코드를 써보거나, 아이디어가 영 없다면 풀이를 찾아본다. 내가 모르는 어떤 중요한 알고리즘이 필요해서 해결하지 못했을 수도 있고, 내 생각이 지역 최적값에 틀어박혀서 답을 못 찾고 있었을 수도 있다. 어느 쪽이든 새로운 시도가 필요하다.
- 내 생각이 지역 최적값에 틀어박혀 있었던 게 문제라면 다른 풀이를 배우면 되고
- 내가 모르는 알고리즘이 필요했던 거라면 해답 코드가 아니라 해당 알고리즘을 사용하는 개념적인 예시 코드를 보고 직접 상황에 맞춰 코드를 변형해본다. 이 과정이 실패한다면 해답을 본다. 솔직히 처음 보는 알고리즘을 제 손발처럼 다루기는 어려운 일이잖아.
정답 확인 후 미련 갖기
앞서 반례 찾기, 알고리즘 공부 등 알차게 문제를 풀었다면 보통은 ‘맞았습니다!’를 보긴 했을 것이다. 이제부터는 미련만 남는다. 욕심이라고 봐도 된다. 문제는 이미 맞았으니 홀가분하게 퇴근했지만 나는 내 코드를 더 빠르고 가볍게 돌리고 싶다, 혹은 비슷하지만 약간 다른 여러 가지 방법 중 뭐가 더 빠른지 궁금하다, 이런 생각이 코드를 더 고치게 만든다. 의무는 아니다.
이때는 점수가 중요한 게 아니다. 내가 쓰고 싶었던 함수를 써보고, 궁금했던 논리를 구현해보고, 최대한 메모리를 줄여본다. 다른 사람 답안을 찾아보기도 한다. 코드를 고치는 건 며칠동안 시간을 들여서 결국 의미없는 짓을 해도 내가 만족하면 그만이다. 이렇게 해보면 어디선가는 또 배우는 구석이 있을 테고, 그 배움은 다른 문제를 풀 때 좀 더 빠르게 효율적인 답안으로 수렴하게 한다.
이럴 때 시도하는 일의 예를 몇 가지 들어 보자면 재귀를 반복문으로 바꾸거나, 내가 저장한 변수 중 불필요한 부분이 없는지 검토해보거나, 선택문과 반복문 중 약간의 조작으로 과정을 줄일 수 있는 부분이 있는지 찾아보는 것 등이 있다. 특히 내가 자주 생각하는 부분은 불필요한 정보 줄이기이다. 나는 사람의 생각을 번역해 컴퓨터의 알고리즘을 만들기 때문에 사람이 계산할 때만 필요했던 정보가 알고리즘에 포함되었을 수도 있다. 혹은 굳이 그렇게까지 계산하고 그 값까지 알아낼 필요가 없는데 계산한 경우도 있다. 이 부분은 다른 해답을 볼 때 발견되기도 하고, 정답을 제출해서 통과한 후에 발견하기도 한다.
사실 코드를 또 고친다고 수행 시간이나 메모리가 극적으로 개선되는 일은 별로 없다. 그래도 프로그래밍이라는 게 컴퓨터가 사람에게 맞추는 일이 아니라 사람이 컴퓨터에게 맞추는 일이니 필요한 고민이라고 본다.
아무튼 미련과 욕심까지 다 해소하고 나면 더이상 해당 문제에는 볼일이 없다. 가끔 이건 기억해둘만 하다 싶은 내용을 블로그에 문제풀이로(혹은 아예 따로) 올리기도 한다.