데이터 과학 유망주의 매일 글쓰기 — 프로젝트 5–3
코딩테스트 문제 푸는 전략
# 전략, #알고리즘
오늘 한일:
오늘은 병원에 좀 들렀다. 내 녹내장 때문이다. 다행히도 그렇게 심하지 않아, 잘 관리하면 될 것 같다. 앞으로도 컴퓨터를 보면서 코딩을 할 수 있을 것 같아, 속으로 쾌재를 불렀다.
이번 주는 주어진 문제를 어떻게 해결했는지에 대한 과정을 보여주는 프로젝트를 하고 있다. 내가 해석한 문제의 의의, 내가 선택한 문제해결방법을 상세히 설명해야하는 프로젝트다. 왠지 개발자로 일하면 통과해야할 코딩테스트같은 느낌이 들었다.
문제를 해결함에 있어 가장 좋은 방법을 찾는 방법은 무엇일까? 어떻게 해야 효율적으로 문제에 접근할 수 있을까? 프로젝트를 하면서 어려운 문제에 부딪히는데, 그럴 때마다 나는 어떤 태도를 취할 수 있을지 정리를 할 필요성을 느꼈다.
코딩 테스트 문제를 푸는 전략
알고리즘이란 사실 별개 아니고, “문제를 해결하는 그 어떤 방법”이 될 수 있다. 즉, 하나의 정해진 형태가 아니라, 주어진 문제를 해결하는 방법, 특히 특정한 패턴을 만들어낼 수 있는 방법을 말한다. 생성한 패턴이 반드시 문제의 요구사항에 따라 원하는 결과를 만들어 낼 수 있어야한다.
많은 사람들은 시간을 들여 코딩테스트 기출 문제 같은 것을 풀어보는 것을 추천한다. 물론, 자신 만의 방법으로 문제를 해결하고, 그것을 설명하는 연습을 할 수 있기에 이는 매우 중요하다. 단, 소프트웨어 개발은 암기가 통하지 않는 분야이기 때문에, 코딩테스트의 문제와 답을 외우는 수준에 머물러서는 안된다. 문제를 제대로 이해하고, 이에 따라 어떤 전략을 취할지에 대한 선택을 적절하게 할 수 있는 것이 중요하다.
컴퓨터 과학에서는 “추상화(abstraction)”이라는 개념이 매우 중요하다.
“‘추상적인 것’은 ‘모호한 것'과는 전혀 다른 의미다. 추상화의 목적은 개념을 흐릿하게 하는 것이 아니라, 명확히 정의 될 수 있는 어떠한 새로운 개념을 만드는 것을 의미한다.” — Edsger Dijkstra
즉, 컴퓨터 과학의 백미는 “추상화"라는 것이다. 코드는 추상적(abstract)일 수록 좋다고도 볼 수 있다. 그 어떤 문제를 해결함에 있어서도, 이러한 추상화의 개념을 활용하면, 정말 좋은 솔루션을 만들어 낼 수 있다.
과정
아래는 코딩테스트 문제를 접근하는데 있어 가장 널리 따르는 과정이다.
- 문제 분석하기
- 문제를 재정의 하기
- 입력값과 출력값의 예를 들어보기
- 문제를 작은 단위로 나누기
- 의사코드(Pseudocode)로 코드를 추상화해보기
- 입력값 예제를 의사코드에 기반해 처리해보기
- 의사코드로 코드를 작성해보기
- 입력값 예제를 작성한 코드에 입력해보기
- 리팩토링(Refactoring)으로 코드 효율성 높이기
1. 문제 분석하기
먼저 가장 중요한 것은 문제를 분석하는 것이다. 문제를 읽기만 한다고 해서 이해할 수 있는 것은 아니다. 문제를 제대로 이해하지 못했다면, 의미없는 해결책을 도출해 낼 수도 있다. 대부분의 문제는, 문제에서 요구하는 사항을 한 두 문장에 드러낸다. 문제에서 나타나는 중요 키워드가 무엇인지 구분해낼 수 있어야한다. 그 키워드가 문제가 무엇인지에 대한 그림을 그릴 수 있게 해준다. 즉, 문제에서 아래에 대한 사항들을 구분해야한다.
- 입력값
- 원하는 출력값
- 그 밖에 문제를 정의하는 키워드나 단어들
예를 들어 LeetCode의 26번 문제를 보자.
“정렬된 정수 배열이 주어졌을 때, 중복되는 것을 제거하여 각 아이템이 유니크하게 한 번만 나타날 수 있도록 하고, 처리된 배열의 크기를 반환하라.
단, 외부 메모리를 사용해 새로운 배열을 생성해서는 안되며, 반드시 입력 배열을 수정하는 방식으로 처리해 리턴해야한다. (공간복잡도 = O(1))
위 내용을 기반으로 문제를 정리하면 아래와 같다.
- 출력은 배열이어야한다. 배열의 순회를 위해 일정한 반복을 사용할 필요가 있다.
- 배열은 정수의 배열이다.
위 문제에서 우리가 반환해야 하는 것들은 아래와 같다.
- 새로운 배열의 크기
위 문제에서 가장 어려운 부분은 아래와 같다.
- 새로운 배열이 원하는 형태로 나오지 않을 가능성
위 문제에서 언급된 중요 키워드는 아래와 같다.
- “정렬된”(중복되는 아이템은 서로 인접해 있다는 의미다.)
- “중복되는 것을 제거”
- “반드시 입력된 배열을 처리” (새로운 배열을 생성하지 않고 입력 배열을 수정해야한다. 사용할 수 있는 배열 처리 방법을 결정할 수 있다.)
- “공간복잡도 = O(1)” (변수를 만들 수는 있으나, 새로운 배열을 생성할 수는 없다.)
2. 문제를 재정의하기
문제를 자신만의 언어로 재정의한다. 만약 면접 상황이라면, 자신이 문제를 어떻게 해석했는지 표현함으로써 면접관에게 좋은 인상을 줄 수 있다. 또한, 모든 문제를 스스로의 언어로 정리할 수 있는 능력을 길러주며, 문제를 더 잘 이해할 수 있다.
아래는 위 문제를 나만의 언어로 재정의한 것이다.
“어느 정수의 정렬된 배열이 주어졌을 때, 중복되는 모든 아이템을 제거한 후 배열의 크기를 반환하라. 단, 새로운 배열을 생성하지 않고 입력 배열을 수정해야한다.”
3. 입력값과 출력값의 예를 들어보기
입력값과 출력값을 매핑해본다. A에서 B로 가는 방법을 찾아보기 위해서는 A와 B가 무엇인지 정의해야한다. 테스트케이스가 주어지더라도, 스스로 테스트케이스를 만들어본다. 무언가 보면서 이해하는 것보다는, 자신이 스스로 무언가를 만들어보는 것이 더 잘 이해할 수 있는 방법이다.
이 방법은 문제를 더 깊게 이해할 수 있다는 점에서, 더 궁극적인 해결책을 탐구할 수 있게 해준다. 텅빈 입력값이나, 중복된 값으로 이루어져있는 배열, 매우 큰 규모의 데이터 셋 등등의 Edge 케이스가 포함될 수 있다. 문제의 제한 조건 밖에 있는 것은 굳이 고려할 필요가 없다. 최소 3가지의 예제를 만들어 보자.
# Edge 케이스들의 예[] -> [], return 0 # 입력값이 아무것도 없을 때는 0을 리턴
[1] -> [1], return 1 # 입력값이 "1"일 때는 "1"을 리턴# 입력값의 중복되는 값을 제거하고 순수하게 유니크한 아이템들 만으로 이루어진 배열 리턴
[1, 1, 2, 3, 4, 4, 4, 5] -> [1, 2, 3, 4, 5], return 5
[1, 1, 1, 1, 1] -> [1], return 1
입력값이 주어진 상태에서, 입력값을 출력값에 맵핑하기 위한 충분한 정보가 있는가? 그렇지 않을 경우, 다음 과정으로 넘어가기 전에 충분한 정보를 얻을 수 있을 때까지 위 과정을 시험해 보는 것이 좋다. 면접이라면, 이해가 되지 않는 부분에 대해서는 확실하게 물어보는 것이 좋다.
입력값에 구애받지 않고 원하는 결과를 얻기 위해서는, 단순하면서도 일관성있는 프로세스를 가진 솔루션이 필요하다. 만약 자신이 만든 솔루션이 지나치게 많은 예외처리와 연산과정으로 이루어져있다면, 그렇게 효율적인 해결책이 아닐 수도 있다.
4. 문제를 작은 단위로 나누기
가장 단순한 문제부터 시작해, 점차 상위 문제로 올라가는 전략을 취한다면, 문제 해결이 좀 더 빠를 수 있다. 예를 들어 2개의 중복된 값을 가진 하나의 배열을 가정하자. ([1, 1, 2]) 문제를 이런 작은 부분으로 나누면, 문제에 접근하기가 더 용이해지고, 무엇을 먼저 해야하는지가 더욱 분명해진다. 그렇게 하면, 비슷한 다른 문제들을 해결하기도 더욱 쉬워지며, 각각의 단순한 문제를 전체적으로 해결하는 과정을 만들어내기가 더욱 수월해진다.
즉, 전체 문제는 아래와 같은 부분들로 분리할 수 있다.
- 배열을 순회하기
- 각 순회에서, 현재 배열의 어느 시점에 와 있는지 인지하기
- 인접한 값이 중복되는지 확인하기
- 인접한 값이 중복되는 값이라면, 처음 나온 값만 유지하고, 다른 것은 버리기
- 최종 배열의 크기를 리턴하기
이것은 상대적으로 단순한 문제지만, 사실 한 배열을 순회하면서 배열의 아이템을 제거하는 것은 다소 불안정한 해결책이다. 배열을 순회하면서, 인덱스가 고정이되어야 하는데, 아이템이 제거되면 인덱스가 변하기 때문이다. 이러한 문제 때문에, 반복 변수(“i”)등을 사용할 때 중복된 값을 건너뛰는 경우도 발생할 수 있다.
그러므로 배열을 순회시, 인덱스의 가변성 문제를 해결할 수 있어야한다. 가능하다면 이 기능을 구현한 또다른 함수를 Helper 함수로 이용하여, 배열의 각 부분을 확실히 검증할 수 있는, 좀 더 깔끔하고 효과적인 코드를 작성할 수 있다.
5. 의사코드로 생각을 추상화하기
지금까지 문제를 분석하여 요구사항과 제한사항을 확인했고, 문제를 작은 부분으로 나누어 제대로 이해하는데 성공했다. 이제는 문제를 해결하기 위해 자신의 생각을 추상화할 수 있을 것이다. 바로 생각을 코드로 옮기기 어렵다면, 좀 더 인간이 이해할 수 있는 방식으로 코드를 미리 계획할 수 있다. 그렇게 하는데 성공했다면, 실제로 동작하는 코드를 작성할 수 있다.
의사코드는 정해진 방식이 없고, 자신이 편한대로, 논리적으로 작성하면 된다. 철자가 반드시 완벽해야할 필요도 없고, 문법에 맞아야할 필요도 없다. 단, 스스로 논리적으로 생각을 정리할 수 있게끔 자신이 알아볼 수 있게는 쓰는 것이 좋다. 의사코드는 코드를 실제로 작성하는데 있어, 참고하면서 솔루션을 만들어나갈 수 있는 가이드 역할을 할 것이다. 만약 면접상황이라면, 다른 사람이 알아보고 논리적으로 무엇을 하려는지는 이해할 수 있도록 작성하는 것이 좋다. 만약 시간이 없어 코드를 완벽하게 작성하지 못했어도, 의사코드를 통해 무엇을 하려는지, 어떤 식으로 문제에 접근했는지 보여줄 수 있는 증거는 남게된다.
의사코드를 쓰는데 있어 정해진 규칙은 없지만, 몇 가지 활용하면 좋을 팁을 소개한다.
- function signature 로 시작한다. 즉, 함수의 이름이 무엇을 하려는 것인지 드러나게끔 한다. 예: def removeDuplicates(array)
- Whiteboard에 적는다고하면, 실제 코드를 쓸 수 있는 충분한 공간을 확보하라.
- IDE에 쓴다고하면, 주석을 달고 코드에서 분리하여 언제든지 참조할 수 있도록한다.
- 절차를 나열하는 식으로 적어, 무엇을 하려는지 단계적으로 표현할 수 있도록한다. (bullet point를 활용하는 것도 좋다.)
중복된 값을 찾는 것이 목적이기 때문에, 하나씩 아이템을 비교해야한다. 배열의 현재 위치의 값과 다음 위치의 값을 비교하거나, 이전 위치의 값과 현재 위치의 값을 비교할 수 있다.
# 배열의 중복값 제거 함수 의사코드
def removeDuplicates(array): repeat the following process until i == len(array):
if array == [] or array.size == 1:
return array.length
else:
compare if array[i] == array[i+1]:
remove array[i+1]
move to next element: i -> i+1
stop when i+1 == len(array)
위 의사코드를 보니, 내가 써야할 코드가 무엇인지 매우 분명해졌다. 먼저 배열의 크기가 “0”이나 “1”일 경우에 대한 Edge 케이스를 작성한다. 이 조건들 역시 중복값이 없어야하는 문제의 요구사항에 부합할 수 있기 때문이다. 그러므로, 배열의 값이 아무것도 주어지지 않거나, 하나만 주어지는 비교대상이 없는 상황도 고려해야한다.
다음으로, 배열의 모든 아이템을 순회해야하므로, 배열의 크기만큼 pointer를 사용하는 For문을 쓸 수 있다. 현재 시점의 아이템에서 다음 시점의 아이템을 비교해야 하기 때문에, pointer는 배열의 최종 값보다 하나 더 낮은 값에서 반복을 멈춰야한다. pointer는 위치가 재조정 되기전 모든 반복 연산마다 중복값을 먼저 제거하기 때문에, 다음 시점에서 인덱스를 shift할 필요가 없다.
6. 입력값 예제를 의사코드에 기반해 처리해보기
머릿속으로 의사코드에 기반해 입력값과 출력값을 처리해본다. 3번 과정에서 찾은 입력값과 출력값을 처리한 부분과 같게 나오는지 확인한다.
# Edge 케이스들의 예[] -> [], return 0 # 입력값이 아무것도 없을 때는 0을 리턴
[1] -> [1], return 1 # 입력값이 "1"일 때는 "1"을 리턴# 입력값의 중복되는 값을 제거하고 순수하게 유니크한 아이템들 만으로 이루어진 배열 리턴
[1, 1, 2, 3, 4, 4, 4, 5] -> [1, 2, 3, 4, 5], return 5
[1, 1, 1, 1, 1] -> [1], return 1
문제가 없는지 확인한다. 그러나 자세히 보면 모두 같은 아이템으로만 구성된 배열은, 배열을 순회하면서 중복값을 모두 제거했을 때, 다음 아이템이 존재하는지도 모르는 상황에서 무작정 다음 아이템으로 넘어가려할 수 있다. 코드를 작성할 때는 이러한 경우도 고려하면서, 순회를 반복하면서 배열의 크기가 변화하는 것을 감지할 수 있어야한다. 즉, 최대한 완성도 높은 코드를 작성하기 위해 노력해야한다.
7. 의사코드를 기반으로 코드 작성하기
이제 드디어 코드를 작성할 시간이다. 코드를 작성할 때 유의할 점은, 이전에 생각하지 못한 새로운 문제점을 발견할 수도 있다는 것이다. 이전 과정에서 의사코드를 통해 미리 계획을 더 잘 세울수록, 더 좋은 코드를 원활하게 작성할 확률이 높아진다. 만약, 예상치 못한 상황을 마주한다면, 의사코드로 돌아가, 그 부분에 대한 의사코드를 추가하는 것도 좋은 방법이다. 코드를 작성하면서 생각하지 못한 문제가 또 생겼는데, 바로 그것을 코드로 옮기기 힘들다면, 의사코드를 보완하여 문제해결을 위한 가이드를 업데이트할 수 있다. 이런 과정을 통해 문제 해결을 위한 계획을 업데이트하고, 좀 더 코드를 원활하게 작성할 수 있다. 물론 가장 좋은 것은 적절한 시간을 의사코드를 작성하는데 안배하여, 최대한 안배한 시간동안은, 되도록 구체적으로 모든 상황을 고려하여 코드를 계획하는 것이다.
# 초기 작성 코드def removeDuplicates(array): for i in range(len(array)):
if len(array) == 0 or len(array) == 1: # Edge cases
return len(array)
elif i+1 < len(array): # 반복문에서 i+1가 배열의 크기보다 1이 작은 값까지만 반복하도록 설정
if array[i] == array[i+1]:
array.remove(array[i+1])
return "array: {}, size: {}".format(array, len(array))
위 코드를 먼저 작성할 때 return statement를 먼저 작성하면, 달성하려는 목적이 무엇인지를 처음부터 명확히 할 수 있다. 또한 empty array나 아이템이 하나 밖에 없는 배열에 대한 Edge 케이스들을 대비할 수 있는 부분도 있어야한다. 배열의 크기만큼 배열의 모든 인덱스를 순회할 수 있어야하며, 배열내 모든 값이 중복되는 것이 없도록 해야한다. 그러자면, 위에 생성한 코드로는 충분하지 않다.
# 최종 코드def removeDuplicates(array):
if len(array) == 0 or len(array) == 1: # Edge cases
return len(array)
for i in range(0, len(array)):
if i+1 < len(array): # 반복문에서 i+1가 배열의 크기보다 1이 작은 값까지만 반복하도록 설정
while array[i] == array[i+1]: # 배열내 중복되는 값이 없을 때까지, 중복되는 값을 처리해준다.
array.remove(array[i+1])
return "array: {}, size: {}".format(array, len(array))
그래서 위와 같이 while문을 활용해, 명시한 조건이 더 이상 나타나지 않을때까지 (다음 시점의 값이 현재 값과 같지 않을때까지) 중복되는 아이템을 모두 조회해 제거할 수 있다. 이렇게 해 주면, 주어진 배열에 중복되는 아이템이 몇 번이 들어가더라도 제거할 수 있다.
8. 입력값 예제를 작성한 코드에 입력해보기
아래는 위 코드를 테스트 할 케이스를 작성해 본 것이다. 보는 바와 같이, 중복된 값이 없는 배열과, 그 배열의 크기가 정상적으로 반환된 것을 볼 수 있다. 물론, 원한다면 아래에 추가적으로 더 많은 테스트 케이스를 만들 수도 있다.
# 위 코드를 테스트할 예제 테스트 케이스removeDuplicates([0,0,0,1,1,1,2,2,3,3,4])>> array: [0, 1, 2, 3, 4], size: 5
이렇게 해서 “외적인 메모리를 사용하지 않는" 효율적인 솔루션이 완성되었다. 입력 변수인 array이외에는 그 어떤 변수도 활용하지 않았다. 시간복잡도 면에서는 모르겠지만, 주어진 공간복잡도의 요구사항에는 부합하는 해결책이다. 그렇다면, 코드를 조금 더 깔끔하고 효율적으로 만들 수있는 여지는 더 이상 없는 것일까?
9. 리팩토링(Refactoring)으로 코드 효율성 높이기
위 코드를 자세히 보면, 결국 배열내 아무것도 없는 상황이거나, 배열의 아이템이 단 한개 밖에 존재 하지 않을 경우는 배열의 길이가 “1 이하"인 경우로 볼 수 있다. 그렇다면 아래와 같이 Edge 케이스에 대한 코드를 두 조건으로 나누기 보다, 하나의 조건으로 만들 수 있다.
def removeDuplicates(array):
if len(array) <= 1: # Edge cases (배열의 크기가 1 이하)
return len(array)
for i in range(0, len(array)):
if i+1 < len(array): # 반복문에서 i+1가 배열의 크기보다 1이 작은 값까지만 반복하도록 설정
while array[i] == array[i+1]: # 배열내 중복되는 값이 없을 때까지, 중복되는 값을 처리해준다.
array.remove(array[i+1])
return "array: {}, size: {}".format(array, len(array))이렇게 해서 내가 작성할 수 있는 최적의 코드가 완성되었다. 여기서 더 단순화 할 수 있을지도 모르지만, 어쨌든 내 입장에서는 최대한 단순화 시킨 솔루션이다. 이렇게 해서 총 9가지의 과정을 통해, 코딩테스트 문제를 해결해 보았다.
앞으로 할일:
코딩테스트가 쉽지 않은 이유는 어떠한 문제가 어떻게 출제될지 예상을 할 수 없기 때문이다. 내가 어디선가 플어본 문제도, 조금 조건이 다르게 출제될 수도 있으며, 내가 보지 못한 문제를 맞이할 수도 있다. 하지만, 모든 문제가 그렇듯 서로 연관되거나 교집합을 갖는 문제들이 많기 때문에, 많은 문제를 풀어볼수록, 더 쉬워지는 것도 사실이다. 결국, 가장 좋은 방법은 많은 문제를 풀어보며 문제 해결 능력을 연습하는 것이다.
여기서 소개한 9가지의 과정은, 앞으로 내가 낮선 문제를 맞이했을 때 사용해 볼 수 있는 유용한 도구가 될 것이다. 코딩테스트를 함에 있어서 문제를 제대로 이해하는 것은 가장 중요한 과정이며, 이를 바탕으로 의사코드를 작성하는 것을 통해 충분히 문제 해결을 위한 계획을 세운다면, 복잡한 문제도 충분히 여러 작은 문제로 단순화할 수 있음을 알게되었다. 그러나, 막상 코딩을 하면서 생각치 못한 문제를 맞이하게 될 수도 있는데, 그럴 때마다 의사코드로 돌아가 업데이트 하면서, 그것을 가이드로 활용하여 문제를 푸는데 이용할 수 있다. 의사코드를 통해 문제 해결의 과정을 단순화하여, 고민하는 시간을 줄이고, 패닉할 때마다 언제나 돌아올 곳을 마련할 수 있다. 결국, 심리적으로도 매우 도움이 되는 방법이다. 마음을 다스리는 것이 문제 해결의 8할 이상임을 감안한다면, 이 유용한 도구를 활용하지 않을 이유가 없다.
내가 바로 그 코딩테스트 같은 프로젝트를 지금 하고있다. 마지막 문제를 풀어야하는데, 바로 이 과정을 모두 거쳐야한다. 그래서, 오늘 리뷰한 내용이 매우 많은 도움이 되었다. 오늘 배운 것을 바로 내일부터 써먹어서, 과제의 가장 복잡한 문제를 해결할 수 있기를 바란다. 무작정 뛰어들어야 좋은 일이 있고, 조금 더 생각해보고 접근해야 좋은 일이 있다. 코딩테스트나 프로그래밍은 아무래도 후자에 가까운 경우가 많다. 그러자면 문제를 태클하기 전에 충분히 생각할 시간을 마련하여, 문제 해결을 위한 전략을 세우고, 그것에 따라 효율적으로 시간을 안배하고 심리적인 문제를 최대한 덜어내면서 접근하는 것이 좋다.
모든 일은 계획할수록 쉬워진다는 만고의 진리를 다시 한번 깨닫게된다. 이 사실을 앞으로도 잊지 않기를 바라며, 내일도 더 나은 문제해결사가 되기 위해 노력해야겠다. 프로젝트를 진행하는 모든 이들 화이팅!
참조:
(1) https://dev.to/moresaltmorelemon/algorithm-problem-solving-strategies-21cp
