[알고리즘] 코딩테스트 문제 대비

기술 면접 대비

문제 대비 훈련법

1. 직접 풀도록 노력해야합니다. 진실로 노력해야합니다. 많은 문제들은 까다롭게 만들어졌습니다. 문제를 풀때는 공간과 시간 효율에 대해서 반드시 생각해야 합니다. 공간효율을 희생해서 시간 효율을 높일 수 있는지, 아니면 반대로 할 수 있는지 자문해 보아야 합니다.

2. 알고리즘 코드를 종이에 적어봅니다. 여러분은 아마 지금껏 컴퓨터 앞에서 코딩을 해왔을 것이고, 컴퓨터가 주는 편리함에 익숙해져 있을 것입니다. 하지만 면접을 보는 동안에는 문법 강조 기능이나 코드 완성, 컴파일링 기능이 갖추어진 도구의 도움을 받을 수 없습니다. 종이에 코딩하면서 같은 상황에 대비하여야 합니다.

3. 코드를 테스트해봅니다. 역시 종이 위에. 일반적인 경우뿐 아니라, 기본 조건 그리고 오류 발생 조건 등을 전부 테스트해보아야 합니다. 면접을 보는 도안에도 그렇게 해야하므로, 미리 연습하는 것이 최선입니다.

4. 종이에 적은 코드를 그대로 컴퓨터로 옮깁니다. 아마 종이에 적는 과정에서 꽤 많은 실수를 저질렀을 것입니다. 실수 목록들을 만들고, 실제 면접장에서는 그런 실수를 저지르지 않도록 유의해야 합니다.

알아야 할 것들

대부분의 면접관은 이진 트리 균형을 맞추는 방법 중 특정한 것을 묻거나, 기타 복잡한 알고리즘에 대해 묻지 않습니다. 사실, 졸업한지 몇 년 지났으니 그들도 이런 알고리즘에 대해 기억하지 못할 것입니다. 기본기를 잘 알아둬야 합니다. 아래는 반드시 알아야할 항목에 대한 나열입니다.

자료구조	알고리즘	개념
연결 리스트	너비 우선 탐색	비트 조작
이진 트리	깊이 우선 탐색	싱글톤 디자인 패턴
트라이	이진 탐색	팩토리 디자인 패턴
스택	병합 정렬	메모리 (스택 vs 힙)
큐	퀵 정렬	재귀
Vector/ArrayList	트리에 대한 삽입/탐색 등등	O표기법
해시 테이블

위 주제 각각에 대해 사용법과 구현법, 그리고 가능하다면 공간과 시간 복잡도에 대해서 알아두는 것이 좋습니다. 자료구조와 알고리즘의 경우, 아무것도 없는 상태에서 밑바닥부터 구현이 가능하도록 연습해 두는 것이 좋습니다. 구현해보라는 문제가 나올수도 있고, 주어진 코드를 변형하라는 문제가 나올 수도 있습니다. 어느 쪽이건 간에, 능숙하면 할수록 좋습니다.

특히, 해시 테이블은 매우 중요한 주제입니다. 면접 문제를 풀 때 자주 사용해야 됨을 알게 될 것입니다.

2 급수표(power of 2)

어떤 사람은 암기하고 있겠지만, 그렇지 못한다면 면접 전에 외워두는 것이 바람직합니다. 규모확장성에 관계된 문제를 풀 때, 데이터 저장에 필요한 공간을 계산할때 편리하게 쓰입니다.

x	2x	근사값	메모리 요구량(바이트)
7	128
8	256
10	1024	1,000(천)	1K
16	65,536		64K
20	1,048,536	1,000,000(백만)	1MB
30	1,073,741,824	1,000,000,000(십억)	1GB
32	4,294,967,296		4GB
40	1,099,511,627,776	1,000,000,000,000(조)	1TB

이 테이블이 있으면 32비트 정수를 불린 값에 대응시키는 해시 테이블이 한 대 컴퓨터 메모리를 얼마나 잡아먹을지 쉽게 계산할 수 있을 것입니다. 웹 기반 사업을 하는 회사와 전화 면접을 하는 경우에는 보이는 곳에 붙여 놓으면 도움이 될것 입니다.

기술 문제 대처 요령

기술 면접시 언어의 주된 개념이 아니라 자료구조와 알고리즘입니다. 면접은 원래 어려운 것입니다. 그러니 모든 문제를 바로 풀지 못해도 괜찮습니다. 그러니 어려운 문제를 만나도 당황하지 말아야 합니다. 어떻게 풀 것인지 이야기하는 것으로 시작하면 됩니다. 어떻게 문제를 공략해 나갈 것인지 면접관에게 보여주어, 막혀 쩔쩔매고 있다는 인상을 주지 않도록 하는 것이 중요합니다.

면접관이 '끝'이라고 하기 전까지는 끝난 것이 아닙니다. 알고리즘을 생각해 낼 때는, 그에 수반되는 문제에 대해서도 생각해 보는 것이 좋습니다. 코드를 작성할 때에는, 버그를 찾아내도록 애써야 합니다. 

기술 문제를 푸는 다섯 단계

1. 면접관에게 문제의 모호한 부분에 대해 묻는다.

2. 알고리즘을 설계한다.

3. 가상코드를 먼저 작성하라. 면접관에게는 실제 코드는 마지막에 작성할 거라고 말해두라.

4. 적당한 속도로 코드를 작성하라.

5. 코드를 테스트하고, 주의 깊게 오류를 교정하라.

1단계: 질문 던지기

기술적인 질문들에는 생각보다 모호한 구석이 많습니다. 그러니 명확하지 않은 부분에 대해서는 반드시 질문하도록 해야 합니다. 그러다 보면 처음에 생각했던 것과는 아주 다른, 그러나 때로 좀 더 쉬운 문제를 풀어야 한다는 결론에 마주하게 될 수 있습니다. 사실, 많은 면접관(특히 마이크로소프트)은 여러분이 좋은 질문을 던질 능력이 있는지도 특별히 테스트합니다.

좋은 질문들은 이런 것들입니다. "자료형은 무엇인가요?" "데이터가 얼마나 많은가요?" "어떤 가정을 해야 하나요?" "사용자는 누구인가요?"

사례: 리스트를 정렬하는 알고리즘을 설계하라

질문: 어떤 리스트인가요? 배열인가요? 아니면 연결 리스트인가요?

답: 배열입니다.

질문: 배열에는 어떤 데이터가 들어가나요? 수? 문자? 문자열?

답: 수입니다.

질문: 정수들인가요?

답: 그렇습니다.

질문: 이 수들은 어떤 수인가요? 식별자인가요? 아니면 어떤 값인가요?

답: 고객의 나이입니다.

질문: 고객의 수는 얼마나 되죠?

답: 백만 명 정도입니다.

이제는 처음과는 다른 문제가 되었습니다. 0에서 130까지의 범위에 속하는 정수 백만 개를 정렬하는 문제가 된것입니다. 어떻게 풀어야 할까요? 길이가 130인 정수 배열을 생성한 다음에 각각의 수가 나올 때마다 그에 해당하는 배열 원소의 값을 하나씩 증가시키면 될 것입니다.

2단계: 알고리즘 설계

알고리즘 설계는 까다롭게 느껴질 수 있는 작업입니다. 하지만 다음 절의 '알고리즘 설계의 다섯가지 접근법'을 읽으면 도움이 될 것입니다. 알고리즘 설계를 하는 동안, 아래와 같은 질문들을 던져보면 좋습니다. 

- 시간과 공간 복잡도는?

- 데이터가 많아지면 어떻게 되나?

- 내 설계가 다른 이슈들을 파생시키지는 않는가? 일례로, 변형된 이진 탐색트리를 만들었다면, 여러분의 설계가 기존의 삽입, 탐색, 삭제 시간에 영향을 미치지는 않는가?

- 다른 이슈나 한계점이 있다면, 적절한 타협안(trade-off)를 만들었나? 그 타협안이 최적으로 동작하지 않는 시나리오로는 무엇이 있나?

- 면접관이 데이터의 특징을 명시했다면(가령 데이터가 나이라거나, 아니면 정렬된 상태라거나) 그 특징을 활용하였는가? 면접관이 그런 정보를 줄때에는 이유가 있게 마련이다.

처음에는 brute-force 알고리즘을 내놓아고 괜찮습니다. 그런 다음에 최적화시켜나갈 수 있습니다. 가능한 한 가장 최적인 답안을 내놓아야 한다고 자정해도 되지만, 그렇다고 처음에 내놓은 답안부터 완벽할 필요는 없습니다.

3단계: 가상 코드

처음에 가상코드로 적으면 생각을 정리하고 실수를 줄이는 데 도움이 됩니다. 하지만 면접관에게 지금은 가상코드를 적지만 곧 실제 코드로 바꿀거라는 점을 알려야 합니다. 많은 지원자가 실제 코드를 적어야 하는 부담을 피하고자 가상 코드를 활용합니다. 하지만 아마도 여러분은 그런 사람들 가운데 한 명으로 취급되고 싶지는 않을 것입니다.

4단계: 코드

코드를 급히 작성할 필요는 없습니다. 정연함을 유지하면서 적절한 속도로 진행합니다. 그리고 다음을 기억합니다.

- 자료구조를 풍부히 활용하라: 관련성이 있다면, 좋은 자료구조를 선택해 활용하거나 스스로 정의하여 사용합니다. 가령 여러분이 일군의 사람들 가운데 나이가 가장 어린 사람을 찾으라는 문제를 받았다면, '사람'을 나타내는 자료구조를 정의할 수 있는지 고려해 보면 좋습니다. 이렇게 하면 면접관들은 여러분이 올바른 객체 지향 설계에 신경쓴다는 인상을 받을 것입니다.

- 코드를 복잡하게 보이도록 하지 마라: 사소한 문제이긴 한데, 알아두면 도움이 됩니다. 화이트보드에 코드를 작성하고 있다면, 가운데서부터 작성하지 말고 왼쪽 상단부터 작성해야 합니다. 답을 적을 넉넉한 공간을 마련할 수 있을 것입니다.

5단계: 테스트

작성한 코드를 테스트 해봐야 합니다. 다음과 같은 사항을 테스트하도록 신경씁니다.

- 극단적인 경우: 0, 음수, null, 최댓값, 최솟값.

- 사용자 실수: 만일 사용자가 null이나 음수 값을 주며 어떻게 되나?

- 일반적인 경우들: 일반적인 경우에 대해서도 테스트하라.

알고리즘이 복잡하거나 복잡한 수치 연산을 포함한다면(비트 시프트, 계산 등등) 코딩이 끝난 다음에 하는 대신, 코딩 도중에 테스트 하는 것이 좋습니다. 실수를 발견했다면(아마도 그럴 것인데) 교정 작업에 들어가기 전에 '왜' 그 버그가 발생했는지 깊게 생각하는 것이 좋습니다. 되는대로 고치고 보는 사람이라는 인상을 주면 안됩니다. 가령 여러분이 만든 함수가 어떤 값에 대해서는 true 대신 false를 반환하는 것을 발견했다고 하자. 반환값을 무작정 뒤집으면, 그 특정한 경우에 대해서는 오류가 사라지겠지만 결국 다른 새로운 문제 발생을 피할 수 없게 됩니다.

그러니 문제점을 발견했다면, 고치기 전에 깊이 생각하는 것이 좋습니다. 그러면 아름답고 깔끔한 코드를 보다 빨리, 정말로 빨리 만들어 낼 수 있을 것입니다.

알고리즘 설계의 다섯가지 접근법

까다로운 알고리즘 문제를 푸는 확실한 전가의 보도는 없습니다. 하지만 아래의 접근법을 따르면 도움이 될 것입니다. 더 많은 문제로 훈련하면 할수록, 어떤 접근법이 유용할지 판단하기도 더 쉬워진다는 것을 명심합니다. 아래의 다섯 접근법은 뒤섞어 사용할 수도 있습니다. 다시 말해, '단순화 & 일반화'를 적용한 다음에, '패턴 매칭'을 시도해 볼 수도 있습니다.

접근법 1: 예증

문제를 구성하는 특정한 사례들을 나열하고, 그런 다음 일반적 규칙을 유도해 낼 수 있는지를 살펴보는 방법입니다.

예제: 시간이 주어졌을때, 시침과 분침 사이의 각도를 구하라.

3:27과 같은 사례부터 시작해 보겠습니다. 시침과 분침을 적정한 위치에 두고, 그림을 그릴 수 있을 것입니다. 아래의 답안에서 h는 시간이고 m은 분입니다. 시는 0부터 23까지의 정숫값입니다.

몇 가지 사례를 살펴보면, 아래와 같은 규칙을 이끌어 낼 수 있습니다.

- 분침과 12 사이의 각도는 360*m/60이다.

- 시침과 12 사이의 각도는 360*(h%12)/12+360*(m/60)*(1/12)이다.

- 시침과 분침 사이의 각도는 (시침과 12 사이의 각도 - 분침과 12 사이의 각도)%360이다.

간단한 수식 계산을 통해, 답이 30h-5.5m임을 얻을 수 있습니다.

접근법 2: 패턴 매칭

패턴 매칭 접근법을 쓰는 경우, 우선 풀어야할 알고리즘이 어떤 문제와 유사했는지 살핍니다. 그리고 그 문제의 답을 수정하여, 지금 풀어야 하는 문제에 적용할 알고리즘을 개발합니다.

예제: 정렬된 배열을 회전시켜 3 4 5 6 7 1 2 와 같은 배열을 얻었다. 이 배열 내에서 최솟값은 어떻게 구할 수 있겠는가?

- 배열 내의 최솟값 원소를 찾아라

- 배열 내의 특정 원소를 찾아라(가령, 이진 탐색)

배열 내에서 최솟값 원소를 찾는 것은 특별히 흥미로울게 없는 알고리즘입니다(그냥 순서대로 검색해봐도 됩니다). 물론, 배열이 정렬되어 있다는 정보를 이용해 봐도 그렇습니다. 여기서는 특별히 유용할 것 같지 않아 보입니다.

하지만 이진 탐색 기법은 유용합니다. 여러분은 배열이 정렬되어 있다는 것, 하지만 회전된 상태라는 것을 알고 있습니다. 그러니 오름차순으로 전진하다 초기화하고, 다시 전진시켜야 합니다. 최솟값의 원소는 '초기화된' 지점에 있습니다.

배열의 중간 원소(MID)와 마지막 원소(RIGHT)를 비교해 보면 (6과 2) 초기화 지점이 우측이라는 것을 알 수 있습니다. MID > RIGHT이기 때문입니다. 초기화 지점이 그들 사이에 있지 않으면, 이 조건은 만족되지 않았을 것입니다.

MID값이 RIGHT보다 작았다면, 초기화 지점은 왼쪽 반 어딘가에 있거나, 아니면 존재하지 않을 것입니다(배열이 완전히 정렬된 상태라면 그렇습니다). 어느쪽이건 간에, 최솟값 원소는 거기서 찾을 수 있을 것입니다.

따라서 이 접근법을, 마치 이진 탐색과 같이 배열을 반씩 나누어 가며 계속 적용해 나갈 수 있습니다. 종국에는 최솟값 원소(즉 초기화 지점)을 찾을 수 있을 것입니다.

접근법 3: 단순화와 일반화

이 접근법을 따르면, 다단계 접근법으로 구현하게 됩니다. 우선, 자료형이나 데이터 양과 같은 제약 조건을 변경합니다. 그렇게 하면 문제를 단순화하는 데 도움이 됩니다. 그런 다음, 단순화된 버전의 문제를 풉니다. 알고리즘이 구해지면 최종적으로 문제를 일반화하여, 구해진 알고리즘을 보다 복잡한 형태로 다듬어 갑니다.

예제: 인질범이 즐겨 사용하는 RANSOME NOTE는 잡지에서 단어를 오려 새로운 문장으로 조합해 내는 것입니다. 잡지가 주어졌을 때, 그 잡지에서 특정한 RANSOME NOTE(문자열로 표현된)를 만들어 낼 수 있는지는 어떻게 알아낼 수 있겠는가?

문제를 단순화하기 위해, 잡지에서 단어를 오려내는 대신 글자 하나씩 오려내는 것으로 바꾸어보자. 이런 형태의 문제는 배열을 하나 만들어 글자의 출현 빈도를 세기만 하면 풀 수 있습니다. 배열의 각 원소는 글자 하나에 대응됩니다. 우선, 몸값 쪽지 문자열 내의 각 문자 출현 횟수를 센 다음, 잡지를 훑어가며 그 모든 글자가 나오는지 보면 되는 것입니다.

이 알고리즘을 일반화해 보아도 하는 일은 비슷합니다. 글자의 출현 횟수를 세는 배열 대신, 단어와 그 출현 횟수를 대응시켜 저장하는 해시 테이블(Hash Table)을 만들면 됩니다. 

접근법 4: 초기 사례로부터의 확장

이 접근법은 특정한 종류의 문제에 적용하면 멋집니다. 이 접근법을 사용할 경우, 우선 초기 사례에 대해 문제를 풉니다(가령 n=1과 같은). 초기 사례에 대해서는, 단순히 올바른 결과만 기록해 두면 끝나는 경우가 많습니다. 그런 다음, n=1에 대한 답은 이미 안다고 가정하고 n=2에 대해서 문제를 풉니다. 그런 다음에는 n=1과 n=2에 대한 답을 안다고 가정하고 n=3의 경우를 풉니다. 

결과적으로, N-1에 대한 답을 안다고 가정하면 N에 대한 답은 언제나 구할 수 있는 해법을 얻게 됩니다. N이 3이나 4가 될 때까지는, 이전 조건에 기초하여 답을 계산할 수 있을만한 '눈길을 끄는' 규칙이 발견되지 않을 수도 있습니다.

예제: 문자열의 모든 순열을 계산하는 알고리즘을 설계하라. 모든 문자는 문자열 내에서 고유하다고 가정할 것.

입력 문자열로 abcdefg가 주어졌다고 해보자.

Case "a" --> {"a"}

Case "ab" --> {"ab", "ba"}

Case "abc" --> ?

이것이 최초로 만나게 되는 '눈길을 끄는' 경우입니다. P("ab")에 대한 답을 안다면, 어떻게 P("abc")를 구할 수 있을까요? 음 그러니까, 추가로 고려해야 할 문제가 "c"이므로, 그냥 가능한 모든 지점에 "c"를 우겨넣기만 하면 됩니다. 다시 말해,

P("abc") = "c"를 P("ab") 결과로 얻은 문자열의 가능한 모든 지점에 삽입

P("abc") = "c"를 {"ab", "ba"}의 가능한 모든 지점에 삽입

P("abc") = merge({"cab", "acb", "abc"}, {"cba", "bca", "bac"})

P("abc") = {"cab", "acb", "abc", "cba", "bca", "bac"}

이제 이 패턴을 이용하여 일반적인 재귀 알고리즘을 만들어 낼 수 있습니다. 문자열 s1...sn의 순열을 구하는 경우, 마지막 문자열은 잠시 제쳐놓고 우선 s1...sn-1의 순열을 만듭니다. 그 순열을 얻고 나면, 그 리스트에 있는 문자열 각각의 모든 지점에 sn을 삽입합니다. 

초기 사례 확장 알고리즘은 자연스럽게 재귀 알고리즘으로 구현되는 경우가 많습니다.

접근법 5: 자료구조 브레인스토밍

이 접근법은 분명 너저분한 것이지만, 통할 때도 자주 있습니다. 일련의 자료구조를 차례차례 적용해보고 해결되는지 보는 것입니다. 가령 '트리를 쓰자'와 같은 결정이 내려지고 나면 자연스럽게 풀리는 문제들이 있기 때문에 유용한 접근법입니다.

예제: 난수 발생기로 만든 수들이 크기가 저절로 늘어나는 배열에 차례로 저장된다. 중간값(median)을 추적하려면 어떻게 해야 하는가?

이 문제를 풀기 위한 자료구조 브레인 스토밍 과정은 이런 식으로 이루어질 것입니다.

- 연결 리스트? 아마 아닐 것이다. 연결 리스트는 수를 정렬하거나 정렬된 수를 접근하는 데에는 취약하다.

- 배열? 그럴 수도 있다. 하지만 문제에서는 이미 '배열'이라고 언급했다. 배열에 저장된 수들을 정렬된 상태로 유지할 수 있나? 할 수 있더라도 비용이 만만치 않을 것이다. 일단은 제쳐두고 필요할 때 자시 생각해 보자.

- 이진트리? 가능하다. 이진 트리는 순서를 유지하는데 강점이 있기 때문이다. 사실 이진 트리가 완벽히 균형 잡힌 상태인 경우, 트리의 제일 위에 위치한 원소가 중간값이다. 하지만 조심하자. 원소가 짝수 개인 경우, 바로 그 중간값은 사실 가운데 위치한 두 원소의 평균 값이다. 그런데 가운데 위치한 그 두 원소는 동시에 트리 꼭대기에 위치할 수 없다. 쓸만한 알고리즘이긴 하지만, 제쳐두자.

- 힙? 힙은 기본적인 순서 관계, 그리고 최댓값과 최솟값을 유지하기 정말 좋은 자료구조다. 정말 재미있는 특성은 바로 이것인데, 힙을 두 개 사용할 경우, 큰 수 무더기와 작은 수 무더기를 분리하여 추적할 수 있다는 것이다. 큰 수 무더기는 최소 힙(min heap)에 두되, 큰 수 무더기 가운데 가장 작은 수가 루트root에 오도록 한다. 작은 수 무더기는 최대 힙(max heap)에 두되, 그중 가장 큰 수가 루트에 오도록 한다. 이렇게 하면 중간값 후보 원소들이 루트 자리들에 오게 된다. 두 힙의 크기가 달라지게 되면, 원소가 더 많은 힙에서 원소 하나를 덜어내 다른 힙에 넣어서 재빨리 균형을 맞출 수 있다. 

문제를 많이 풀어볼수록, 어떤 자료구조가 적합할지 눈치채는 감이 좋아질 것입니다. 또한, 지금까지 언급한 접근법들 가운데 어떤 것이 가장 좋을지 골라 내는 본능적 감각도 좀 더 향상될 것입니다.

어떤 코드가 좋아 보이나

고용주가 여러분이 '좋고, 깔끔한' 코드를 썼는지 확인하고 싶어한다는 사실을 지금쯤이면 여러분도 알고 있을 것입니다. 하지만 이 말이 진정으로 의미하는 것은 무엇일까요? 그리고 면접시에는 어떤 과정을 통해 확인하게 될까요?

크게 본다면, 좋은 코드는 다음과 같은 속성을 갖고 있습니다.

- 정확함: 예상한 입력이든 혹은 예상하지 못했던 입력에 대해서든, 여러분의 코드는 정확히 동작해야 합니다.

- 효율성: 시간과 공간 효율성은 좋은 코드여야 합니다. 이 '효율성' 개념은 O표기법과 같은 점근적 효율성과, 실생활에서 만나게 되는 실용적 효율성의 개념을 포괄합니다. 가령 O표기법을 사용해 시간 효율성을 계산하면 상수 수분이 탈락되어 무시되겠지만, 실제적으로는 그 부분도 굉장히 중요할 수 있습니다.

- 단순성: 100줄 대신 10줄로 뭔가를 할 수 있다면, 그래야 합니다. 개발자가 빠른 시간에 작성할 수 있는 코드여야 합니다.

- 가독성: 여러분의 코드를 많은 프로그래머가 읽고 이해할 수 있어야 합니다. 필요한 곳에는 주석이 달려 있어야 하며, 쉽게 이해할 수 있는 방식으로 구현되어야 합니다. 비트 시프트 연산을 많이 사용해 작성한 코드는 그럴듯해 보일지는 몰라도 가독성이 좋은 코드는 아닐 수 있습니다.

- 관리가능성: 제품 개발 사이클 동안에 적절히 변경 가능해야 하고, 최초로 작성한 개발자뿐 아니라 다른 개발자도 쉽게 관리 가능한 코드여야 합니다.

이런 측면들을 추구하다 보면 균형을 잡을 필요가 있습니다. 가령, 관리 가능한 코드를 만들려면 어느 정도의 효율성은 희생해야 합니다. 효율성이 우선이 되면 관리 가능성은 희생됩니다. 면접중에 코딩할 때에는 이런 요소들을 생각해봐야 합니다. 지금부터 이야기할 내용은 앞서 이야기한 다섯 속성을 좀 더 구체적으로 보여줍니다.

자료구조를 일반적으로 사용하라

두 개의 단순 다항식을 더하는 함수를 작성하라는 문제를 받았다 해보겠습니다. 다항식은 일련의 항이 연결된 것으로서, 각항은 지수에 상수를 곱한 것입니다. 면접관은 문자열 파싱은 필요없으며, 다항식 저장에 필요한 자료구조는 어떤 것을 사용해도 좋다고 이야기 합니다. 구현하는 방법에는 여러가지가 있씁니다.

1) 나쁜 구현 형태

다항식을 하나의 double 형 배열에 저장한다고 해보겠습니다. 이때 k번째 원소는 다항식의 X^k 항의 계수에 해당합니다. 이런 혀애의 자료구조는 음수 또는 정수가 아닌 지수를 항으로 가질 수 없으므로 좋지 않습니다. X^1000 하나의 항을 갖는 다항식을 위해서도 1000개의 원소를 갖는 배열을 정의해야 하므로 비효율 적입니다.

int[] sum(double[] poly1, double[] poly2) {
    ...
}

2) 좀 덜 나쁜 구현 형태

이것보다는 조금 나은 방법은, 하나의 다항식을 coefficients와 exponents라는 두 개의 배열로 나누어 저장하는 것입니다. 이 접근법을 사용하면 다항식의 각 항을 임의 순서로 저장할 수 있습니다. 다만 i번 째 항은 coefficients[i]*X^exponents[i]에 의해 표현될 수 있도록, 배열 원소의 짝을 잘 맞춰야 합니다.

그러므로 coefficients[p] = k이고 exponents[p] = m이면 p번째 항은 kx^m입니다. 앞서 살펴본 방법과 같은 제약은 없지만, 여전히 지저분합니다. 하나의 다항식을 표현하기 위해서 배열을 두 개나 추적해야 합니다. 두 배열의 길이가 다르면 다항식은 '정의되지 않은' 값을 갖게 됩니다. 다항식을 반환하는 것도 성가시기 짝이 없는데, 배열을 두개 반환해야 하기때문입니다.

??? sum(double[] coeffs1, double[] expon1, double[] coeffs2, double[] expon2) {
    ...
}

3) 좋은 구현

이 문제를 푸는 좋은 방법은, 다항식을 표현하기 위한 자신만의 자료구조를 설계하는 것입니다.

class PolyTerm {
    double cofficient;
    double exponent;
}

PolyTerm[] sum(PloyTerm[] poly1, PolyTerm[] ploy) {
    ...
}

누군가는 이것이 '지나친 최적화'라고 주장할 것입니다. 그럴 수도 있고 아닐 수도 있습니다. 이에 대한 여러분 의견과는 관계 없이, 위의 코드는 여러분이 코드를 어떻게 설계해야 하는지 생각했다는 점, 허겁지겁 코드를 쓸어 담으려하지 않았다는 점을 보여줍니다.

적절한 코드 재사용

여러분이 문자열로 전달된 이진수의 값이, 역시 문자열로 전달되 16진수 값과 일치하는지를 검사하는 함수를 작성하라는 주문을 받았다고 해보겠습니다. 이 문제에 대한 우아한 해답 중 하나는, 코드 재사용을 장려합니다. 아래를 보겠습니다.

public boolean compareBinToHex(String binary, String hex) {
    int n1 = convertToBase(binary, 2);
    int n2 = convertToBase(hex, 16);

    if(n1 < 0 || n2 < 0) {
        return false;
    } else {
        return n1 == n2;
    }
}

public int digitToValue(char c) {
    if( c >= '0' && c <= '9') return c - '0';
    else if( c >= 'A' && c <= 'F' ) return 10 + c - 'A';
    else if( c >= 'a' && c <= 'f' ) return 10 + c - 'a';
    return -1;
}

public int convertToBase(String number, int base) {
    if ( base < 2 || (base > 10 && base != 16) ) return -1;
    int value = 0;
    for (int i = number.length() - 1; i >= 0; i--) {
        int digit = digitToValue(number.charAt(i));
        if (digit < 0 || digit >= base) {
            return -1;
        }
        int exp = number.length() - 1 - i;
        value += digit * Math.pow(base, exp); 
    }
return value;
}

이진수를 변환하는 함수와 16진수를 변환하는 함수를 별도 분리해서 작성할 수도 있었겠지만, 그렇게 하면 코딩하기 어려워질 뿐 아니라 유지보수하기도 힘든 코드가 만들어집니다. 대신, 우리는 convertToBase라는 함수와 digitToValue라는 함수를 작성한 다음 재사용했습니다.

모듈화

모듈화된 코드를 작성한다는 것은, 관계 없는 코드들을 별도 메서드로 나눈다는 것을 의미합니다. 그렇게 하면 코드를 좀 더 쉽게 유지보수할 수 있게 되고, 가독성이 좋아지며, 테스트하기도 쉬워집니다.

정수 배열의 최솟값과 최댓값 원소를 바꾸는 코드를 작성해야 한다고 하겠습니다. 메서드 하나로 작성하면 이렇게 됩니다.

public void swapMinMax(int[] array) {
    int minIndex = 0;
    for(int i = 1; i < array.length; i++) {
        if (array[i] < array[minIndex]) {
            minIndex = i;
        }
    }

    int maxIndex = 0;
    for(int i = 1; i < array.length; i++) {
        if (array[i] > array[maxIndex]) {
            maxIndex = i;
        }
    }

    int temp = array[minIndex];
    array[minIndex] = array[maxIndex];
    array[maxIndex] = temp;
}

아니면, 상대적으로 관련성이 적은 코드를 서로 다른 메서드로 분리하여, 모듈화 할 수도 있을 것입니다.

public static int getMinIndex(int[] array) {
    int minIndex = 0;
    for (int i = 1; i < array.length; i++) {
        if (array[i] < array[minIndex]) {
            minIndex = i;
        }
    }
    return minIndex;
}

public static int getMaxIndex(int[] array) {
    int maxIndex = 0;
    for (int i = 1; i < array.length; i++) {
        if (array[i] > array[maxIndex]) {
            maxIndex = i;
        }
    }
    return maxIndex;
}

public static void swap(int[] array, int m, int n) {
    int temp = array[m];
    array[m] = array[n];
    array[n] = temp;
}

public static void swapMinMaxBetter(int[] array) {
    int minIndex = getMinIndex(array);
    int maxIndex = getMaxIndex(array);
    swap(array, minIndex, maxIndex);
}

모듈화하지 않는다고 꼭 끔찍한 코드가 되는 것은 아닙니다. 하지만 모듈화하면 각 부분을 독립적으로 확인할 수 있어 테스트를 한층 쉽게 할 수 있습니다. 코드가 복잡해질수록, 모듈화 원칙을 지키는 것이 중요합니다. 가독성도 높아지고, 유지보수하기 쉬워질 것입니다. 여러분의 면접관은 여러분이 이런 기술을 갖고 있는지 확인하길 원합니다.

유연하고 튼튼한 코드

tic-tac-toc 게임 결과를 판정하는 코드를 작성하라는 문제를 받았다고해서, 게임판이 3x3이라는 가정을 하고 문제를 풀어야 하는 것은 아닙니다. N x N 크기 게임판에 적용할 수 있는, 보다 범용적인 코드를 작성하면 안될 것 없습니다.

유연하고 범용적인 코드를 작성하려면, 상수 대신 변수를 쓰거나, 또는 템플릿/제네릭을 써야 할 수도 있씁니다. 좀 더 일반적인 문제를 풀 수 있는 코드를 작성할 수 있다면, 그래야 합니다.

물론, 그러지 말아야 하는 경우도 있습니다. 일반적인 경우를 풀려면 해답이 너무 복잡해진다거나, 지금으로서는 그럴 필요가 없어 보인다거나 하면, 그냥 간단한, 풀어야 하는 경우에 대해서만 집중하는 것이 좋습니다.

오류 검사

신중한 코더는 입력에 대해 아무런 가정도 하지 않습니다. 대신, ASSERT나 if문을 통해서 입력이 기대하던 대로인지 아닌지를 검사합니다.

일례로, 앞서 살펴보았던 특정 진수로 표현된 정수를 int 값으로 변환하는 코드를 살펴보겠습니다.

public int convertToBase(String number, int base) {
    if (base < 2 || (base > 10 && base != 16)) return -1;
    int value = 0;
    for (int i = number.length() - 1; i >= 0; i--) {
        int digit = digitToValue(number.charAt(i));
        if(digit < 0 || digit >= base) return -1;
            int exp = number.length() - 1 - i;
            value += digit * Math.pow(base, exp);
    }
    return value;
}

2번째 줄에서, 우리는 base에 올바른 값이 주어졌는지 검사합니다. (10보다 큰 base 값의 경우에는 1을 제외하고는 표준적인 문자열 표현방법이 존재하지 않는다고 가정합니다) 6번째 줄에서는, 각 숫자를 검사하여 허용된 범위 내에 있는지 확인합니다.

이러한 테스트는 상용 수준 제품에 포함되는 코드를 작성할 때 아주 중요하며, 면접을 볼 때에도 마찬가지입니다.

물론, 이런 코드를 작성하는게 어리석어 보이고, 제한된 면접 시간을 낭비하는 것처럼 느껴질 수도 있습니다. 중요한 것은 여러분이 '결국에는 오류 검사를 위한 코드를 추가할 것'이라는 사실을 보이는 것입니다. 만일 간단한 if문으로 검사 코드를 추가할 수 없다면, 코드가 들어갈 공간을 남겨두고 면접관에게 '나머지 코드를 완성한 다음에 채우겠습니다'라고 말하는 것이 최선입니다.