기술적 문제

준비하기

많은 지원자들이 공부를 한답시고 문제와 답을 읽기만 하곤 한다. 문제는 직접 푸는 훈련을 해야한다. 답을 외우는 것은 도움이 되지 않는다. 문제를 만날때마다 다음과 같이 행동하자

직접 풀도록 노력하라 : 문제에 힌트가 주어지긴 하지만 직접 답을 찾으려고 노력하자. 문제를 풀 때는 공간과 시간 효율에 대해서도 반드시 생각하자
코드를 종이에 적으라 : IDE를 이용하면 코드 문법 강조, 자동완성, 디버거가 갖춰진 편리한 환경에서 코딩할 수 있다. 종이에 코딩하게 되면 그런 도움을 받을 수 없다. 실제 면접에서도 마찬가지다.
코드를 테스트하라 : 물론 종이에서, 기본 조건, 오류 발생 조건 등을 전부 테스트 하라
종이에 적은 코드를 그대로 컴퓨터로 옮긴 뒤 실제로 실행해 보라 : 종이에 적는 과정에서 많은 실수를 저질렀을 것이다. 실수 목록들을 만들고 실제 면접장에서 같은 실수를 저지르지 않도록 유의하라.

그리고 가상 면접을 가능한 한 많이 해보길 바란다.

알고 있어야 할 것들

많은 회사에서 자료구조, 알고리즘 같은 종류의 문제에 집중하는데 이어한 문제를 내는 이유는 단순히 지식 확인을 위해서가 아니다.

핵심 자료구조, 알고리즘, 기본 개념

면접관이 우리에게 기대하는 것은 기본기다. 반드시 알아야할 것들로 다음과 같이 있다.

자료구조	알고리즘	개념
연결리스트	너비 우선 탐색	비트 조작
트리, 트라이, 그래프	깊이 우선 탐색	메모리(스택vs힙)
스택, 큐	이진 탐색	재귀
힙	병합 정렬	동적 프로그래밍
Vector, ArrayList	퀵 정렬	big-O시간&공간
해시 테이블

위 주제에 대하여 사용법, 구현법, 애플리케이션, 가능하다면 공간과 시간 복잡도에 대해서 알아두자. 특히 해시테이블은 매우 중요한 주제다 이 자료구조를 능숙하게 다룰 수 있도록 연습하자

2의 승수 표

위 표는 규모 확장성 및 메모리 제한과 관련된 문제를 풀 때 유용하다.

실제 문제 살펴보기

듣기 : 문제 설명과 관련된 것이라면 어떤 정보든지 집중해서 들어야 한다.
예제 : 직접 예제를 만들어서 디버깅하라
무식하게 풀기 : 알고리즘 효율을 높이려고 미리 애쓰지 말라, 먼저 무식한 방법으로 풀어보자
최적화
1. 간과한 부분이 있는지 생각해보자
2. 예제를 손으로 풀어보고 사고 과정을 되짚어 보자
3. 잘못된 방법으로 문제를 풀어 본 뒤 왜 알고리즘이 틀렸는지 생각해보자
4. 시간과 공간의 비용-이익 관계를 고려하라. (해시테이블이 특히 유용하다.)
검토하기 : 해법을 찾았다면 다시 한 번 검토하라
구현하기 : 시작부터 코드를 모듈화시키고 리팩토링해서 깔끔하게 만들어라
테스트
1. 개념적 테스트 - 마치 코드리뷰를 하듯이 자세하게 코드를 훑어보며 테스트
2. 특이하거나 표준적이지 않은 코드
3. 산술연산 혹은 널 노드와 같이 실수가 날 만한 부분
4. 작은 크기의 테스트들
5. 특이하거나 극단적인 입력

경청하기

반드시 문제를 잘 듣고 정확히 이해했는지 확인해야 한다. 확실하지 않은 부분은 질문을 통해 반드시 짚고 넘어가야 한다.

문제를 주의 깊게 듣고 문제와 관련된 모든 독특한 정보를 머릿속에 기억해 둬야 한다. 대부분 문제를 푸는데 아무 영향도 끼치지 않는 정보를 제공하는 경우는 많지 않다.

예제를 직접 그려보기

많은 지원자들이 머릿속에서 생각한 후 바로 문제를 풀려고 시도하는데, 예제를 직접 그려 보면 차원이 다른 문제 풀이 능력을 발휘할 수 있을 것이다.

예제를 만들 때는 다음을 유의해야 한다.

명확한 예제를 쓰라 - 문제에 맞는 실제 숫자와 문자열을 사용하라
충분히 큰 예제를 쓰라
특별한 예제를 지양하라

무식한 방법으로 일단 해보기

예제가 완성되면 일단 무식한 방법으로 먼저 시도해보자 첫 알고리즘이 형편 없어도 알고리즘의 시간 및 공간복잡도를 설명한 뒤 알고리즘을 개선해 나가면 된다. 무식한 방법 알고리즘은 느릴 수 있어도 토론할 가치가 있다.

최적화

간과한 정보가 있는지 찾아보자
새로운 예제를 만들어 보자
잘못된 방식으로 문제를 풀어보자 - 틀린 해법을 통해 올바른 해법을 찾아낼 수도 있다.
시간과 공간의 실익을 따져보고 균형을 맞추어라
정보를 미리 계산해 두라
해시 테이블을 사용하라 (면접 문제에 널리 사용되는 개념으로 반드시 알고 있어야 한다.)
가능한 최선의 수행시간이 무엇인지 생각하라

검토하기

최적 알고리즘을 완성했다고 바로 코딩에 뛰어들지 말라 잠시 생각하며 알고리즘에 대한 이해를 확실히 할 시간을 가지자

코딩을 시작하기 전에 가능하면 완벽에 가까운 상태로 만든 뒤에 실제 코딩에 들어가야 한다.

코드작성하기

아름다운 코드를 작성하려면 다음을 유의하라

모듈화된 코드를 사용하라 - 모듈화는 좋은 코딩 방식이다. 모듈화는 무엇인가를 쉽게 만들게 해준다.
에러를 검증하라
필요한 경우에 다른 클래스나 구조체를 사용하라 - 어떤 동작을 하는 함수가 필요한 경우 그 함수객체가 있다고 가정하고 사용한다. 그리고 나중에 시간이 남으면 그때 세부적인 부분을 처리하면 된다.
좋은 변수명을 사용하라 - 한 글자 변수명을 여기저기 사용하다 보면 코드를 읽기 어려워진다. 되도록 의미 있는 변수명을 쓰되 변수명이 너무 길어지고 반복되는 경우 처음에는 긴 변수명을 쓰고 이를 줄여서 약자로 쓰겠다고 면접관에게 설명하면 된다.

나중에 리팩터링해야 할 부분을 발견한다면 바로 뛰어들지 말고 면접관에게 우선 설명한 후 시간을 들일 필요가 있는지 판단하여 리팩터링 여부를 결정한다.

테스트

면접에서 테스트 없이 코드를 제출하지 말아야 한다. 테스트는 다음과 같은 방법을 사용하자

개념적 테스트부터 시작하라 - 개념적 테스트는 코드를 한줄 한줄 읽어 내려가며 어떤 일을 수행하는지 분석하는, 즉 머릿속에서 돌려보는 테스트를 의미한다.
코드에서 평소와는 다르게 돌아가는 부분을 유심히 살펴보라 - 예) x=length-2, i=1부터 시작하는 for문 등을 눈여겨 보자
버그가 자주 발생하는 부분을 유심히 살펴보라 - 예)재귀함수의 기본, 정수 나눗셈, 이진트리의 널 노드, 연결리스트를 순회할 때 시작과 끝점 같은 곳 등을 잘 확인하자
작은 규모의 테스트를 돌려보라 - 실제 입력데이터를 이용해서 테스트해보자, 알고리즘 테스트시 원소의 개수가 많은 배열은 되도록 사용하지 말자 3~4개 정도가 적당하다. 크기가 작아야 버그를 더 빨리 찾을 수 있다.

버그를 찾으면 바로 고치치 말고 왜 그런 버그가 발생했는지 주의 깊게 분석한 뒤 고치는 것이 최선의 방법이다.

최적화 및 문제풀이 기술 1 : BUD를 찾으라

B(병목현상), U(불필요한 작업), D(중복되는 작업)

알고리즘이 비효율적으로 동작하는 가장 흔한 이유가 위 세가지다.

병목현상

병목현상은 알고리즘에서 전체 수행 시간을 잡아먹는 부분을 의미한다. 일반적으로 다음의 두 가지 이유 때문에 병목 현상이 발생한다.

어떤 부분 때문에 알고리즘이 느려지는 경우 : 예) 두 단계로 이루어진 알고리즘이 있을 때, 이 알고리즘은 먼저 배열을 정렬한 뒤 특정 속성을 가진 원소를 찾는 알고리즘이다. 첫 번째 단계에서는 O(N logN)이 소요되고 두 번째 단계에선 O(N)이 소요된다. 두 번째 단계를 줄일 수 있지만 별 의미가 없을 것이다. 왜냐하면 O(N logN)이 이 알고리즘의 병목점이기 때문이다. 첫 단계를 최적화하지 않는 이상 이 알고리즘의 전체 수행시간은 O(N logN)으로 남게 된다.
검색을 여러 번 하는 것처럼 반복적으로 수행하는 부분이 여러 개 있는 경우 : 이 경우에는 O(N)을 O(log N) 혹은 O(1)로 줄이는 것이 의미가 있을 것이다. 이런 경우 전반적인 수행 시간에 엄청난 속도 향상을 이룰 수 있기 때문이다.

병목현상을 해결하는 것은 전체 수행 시간에 커다란 차이를 만들어낸다.

예제: 서로 다른 정수로 이루어진 배열이 있을 때 두 정수의 차이가 k인 쌍의 개수를 세라. 예를 들어 주어진 배열이 (1, 7, 5, 9,2, 12, 31이고 k= 2면, 두 정 수의 차이가 2인 쌍은 다음과 같이 네 개가 존재한다.
(1,3), (3,5), (5,7), (7,9)

여기서 병목점은 원소 쌍의 두 번째 원소를 반복적으로 찾을 때 있다. 따라서 여기가 최적화를 해야 할 부분이다. 만약 배열이 정렬되어 있다면 이진 탐색을 이용해 O(logN)에 찾을 수 있고, 이를 모든 N개의 원소에 적용해 보면 시간 복잡도는 O(N logN)이 된다.

이 알고리즘에선 배열을 정렬하는 부분이 새로운 병목점이 된다. 정렬 단계 때문에 두 번째 단계를 아무리 최적화해도 시간 복잡도 개선에 도움이 되지 않는다.

정렬되지 않은 배열에서 원소를 빠르게 찾을 수 있는 방법이 무엇일까? 바로 해시테이블을 이용하면 된다. 배열의 모든 월소를 해시테이블에 넣은 뒤 이 해시테이블을 통해 x + k 또는 x - k가 배열에 존재하는지 확인하면 된다. 이렇게 하면 O(N) 시간에 문제를 풀 수 있다.

불필요한 작업

예제: a, D, C, d가 1에서 1000사이에 있는 정수 값 중 하나일 때 2'+6% C+d?을 만족하는 모든 자연수를 출력하시오.

  
//무식한 방법 : 모든 가능한 값을 d에 대입해보는 과정은 불필요하다. 왜냐하면 가능한 d의 값은 딱 하나뿐이기 때문이다.
n = 1000
for a from 1 to n
  for b from 1 to n
    for c from 1 to n
      for d from 1 to n
        if a³ + b³ == c³ + d³
          print a, b, c, d
          //정답을 찾은 뒤에는 d를 찾는 루프를 빠져나와야 한다.
          break

이 방법의 시간복잡도는 여전히 O(N²)이라서 전체 시간 복잡도 개선에 별다른 영향을 주지 않는다.

  
n = 1000
for a from 1 to n
  for b from 1 to n
    for c from 1 to n
      d = pow(a³ + b³ - c³, 1/3)  //정수로 반올림한다.
      if a³ + b³ == c³ + d³  //실제 이값이 수식을 만족하는지 확인한다.
        print a, b, c, d

중복되는 작업 (103p)

최적화 및 문제풀이 기술 2 : 스스로 풀어보라 DIY

여러분이 컴퓨터 과학에 관한 지식이 없는 누군가에게 알파벳순으로 정렬된 학생 수첩 더미를 주면서 Peter Smith의 학생 수첩을 찾아보라고 한다면 그들은 이진 탐색 비슷한 방식을 이용할 것이다. 이진 탐색에 대한 사전 지식이 없더라도 직관적으로 어떻게 접근해야 할지는 알고있다.

‘알고리즘을 설계하라’ 라는 문구를 던지면 사람들은 종종 혼란에 빠진다. 하지만 수첩더미와 같은 실제 예제를 쥐어주면 인간은 굉장히 훌륭한 알고리즘을 직관적으로 찾는다. 그러므로 실제 예제를 통해 직관적으로 문제를 풀어나가려는 노력을 하자.

예제: 길이가 작은 문자열 s와 길이가 긴 문자열 b가 주어졌을 때, 문자열 b 안에 존재하는 문자열 s의 모든 순열을 찾는 알고리즘을 설계하라. 각 순열의 위치를 출력하면 된다.

s : abbc
b : cbabadcbbabbcbabaabccbabc

나쁜 풀이 ) s에서 가능한 모든 순열을 나열한 뒤 b에서 찾는다. 이경우 순열의 개수가 S!이므로 O(S!*B)가 될 것이다. 이렇게 하면 극단적으로 느린 알고리즘이 된다.

좋은 풀이 )

s의 길이가 4이므로 b를 4개씩 끊어서 차례로 살펴본 뒤 s의 순열을 만족하는지 확인한다.
b의 문자를 앞에서부터 차례로 살펴보면서 s에 속한 문자가 보일 때마다 그다음 문자를 포함한 4개의 문자열이 s의 순열을 만족하는지 확인한다.

이렇게 하면 아마 수행시간은 O(BS), O(BSlogS), O(B*S²) 중 하나가 될 것이다.

이처럼 문제를 풀때 문제에 적합하고, 크기가 크며, 구체적인 예제를 바탕으로 직관적으로 (손으로 직접) 문제를 풀어보길 바란다.

최적화 및 문제풀이 기술 3 : 단순화, 일반화하라

자료형과 같은 제약조건을 단순화하거나 변형시킨다.
단순화된 버전의 문제를 푼다.
단순화된 문제의 알고리즘이 완성되면 해당 알고리즘을 보다 복잡한 형태로 다듬어 간다.

예제: 랜섬 노트(ransom note)는 잡지에서 오린 단어를 이용해서 만들어 낸 새로운 문장을 의미한다. 잡지(문자열)가 주어졌을 때, 그 잡지에서 문자열로 표현된 특정 랜섬 노트를 만들 수 있는지 어떻게 확인할까?

이런 형태의 문제는 배열을 하나 만들어서 글자의 출현 빈도를 세기만 하면 풀 수 있다. 배열의 각 원소는 글자 하나에 대응된다. 우선 랜섬 노트 내에서 각 문자가 출현한 횟수를 센 다음, 잡지를 훑어 가며 각 문자의 횟수가 랜섬 노트에 출현한 문자의 횟수보다 같거나 많은지 확인한다.

==> 결과 값(랜섬노트)가 주어지고, 입력 값(잡지)가 주어졌을때 입력 값으로 결과 값을 만들 수 있느냐에 대한 문제 같음.

최적화 및 문제풀이 기술 4 : 초기 사례로부터 확장하기

이 접근법은 우선 초기 사례 예) n=1 과 같은 문제를 푼 뒤, 거기서부터 해법을 확장해 나간다. 106~107p

최적화 및 문제풀이 기술 5 : 자료구조 브레인스토밍

단순하게 일련의 자료구조를 차례 차례 살펴보면서 하나씩 적용해보면 된다. (107~108p)

가능한 최선의 수행 시간(BCR)

가능한 최선의 수행 시간이 무엇일까 생각해 보는 것 자체로도 문제를 푸는 유용한 힌트를 발견해낼 수 있다.

예) 길이가 A와 B인 배열 두 개가 주어졌을 때 두 배열에 공통으로 들어있는 원소의 개수가 몇 개인지 세는 경우

이 문제의 경우 각 배열의 원소를 적어도 한 번씩은 건드려봐야 하기 때문에 어떤 알고리즘이든 O(A+B)보다 빠를 수 없다. 따라서 이 문제에 BCR은 O(A+B)이다.

오답에 대한 대처법

면접에서 흔히하는 오해는 모든 문제를 맞춰야 한다는 생각이다.

면접에서 답을 평가할 때 맞냐 틀렸냐로 보지 않는다. 최종 답안이 최적 해법에 근접한가, 최종 답안을 내는데 시간이 얼마나 걸렸나 얼마나 힌트를 필요로 했는가 얼마나 코드가 깔끔한가를 더 중요하게 여긴다.
면접관은 지원자들을 상대적으로 평가한다.
대부분의 문제가 아주 어렵기 때문에 굉장히 실력있는 지원자라 하더라도 단번에 최적에 해법을 말하긴 어려울 수 있다.

알고 있던 문제가 면접에 나왔을 때

이전에 알고있던 문제가 면접에 나왔다면 면접관에게 사실대로 말하길 바란다. 면접관이 문제를 출제한 이유는 여러분의 문제풀이 능력을 평가하기 위함이다. 여러분이 이미 문제를 알고있다면 면접관은 여러분을 제대로 평가할 수 없다.

면접용으로 완벽한 언어

수많은 최고의 회사들은 언어 선택에 깐깐하게 굴지 않는다. 특정 언어에대한 내용을 알고있는지보다 얼마나 문제를 잘 풀었는지에 더 관심이 있다.

언어를 선택할 때는 여러분이 가장 편하게 코딩할 수 있는 언어를 선택하는 게 가장 좋다. 만약 그런 언어가 많다면 다음을 염두해두고 선택하자

널리 사용되는 언어 : 면접관도 알고 있는 언어로 코딩하는 것이 바람직하다.
언어 가독성 : 면접관에게 익숙하지 않은 언어라도 기본적인 내용은 이해할 수 있을 것이다. 어떤 언어들은 다른 언어들과 전반적으로 유사해서 자연스럽게 쉽게 읽히는 경향이 있다.
잠재적인 문제점 : 어떤 언어들은 그 언어를 사용한다는 이유만으로 안고 가야하는 잠재적인 문제점들이 있다.
언어가 얼마나 장황한지 : 예를 들어 자바는 파이썬과 비교했을 때 상당히 장황한 언어다.
사용하기 쉬운 언어 : 어떤 언어는 다른 언어보다 특정 기능을 사용하기 쉽다.

어떤 코드가 좋아 보이나

모든 회사가 좋고 깔끔한 코드를 작성하는 지원자를 원한다는 사실을 알고 있을 것이다. 알반적으로 얘기해서 좋은 코드란 다음과 같은 속성을 가진다.

정확도 : 예상 가능한 혹은 불가한 입력에 대해서 코드는 정확히 동작해야 한다.
효율성 : 시간과 공간 두 가지 측면에서 모두 효율성이 좋은 코드여야 한다. 효율성 개념은 O 표기법과 같은 점근적 효율성과 실생활에서 만나게 되는 실용적 효율성의 개념을 모두 포괄한다.
간략화 : 코드 100줄짜리를 10줄로 작성할 수 있다면 그렇게 해야 한다.
가독성 : 다른 개발자들도 여러분의 코드를 읽고 어떻게 동작하는지 이해할 수 있어야 한다. 필요한 곳에 주석이 달려 있어야 하며 쉽게 이해할 수 있는 방식으로 구현되어야 한다.
관리 가능성 : 코드는 제품의 수명주기 동안에 적절히 수정 가능해야 하고, 최초로 작성한 개발자뿐 아니라 다른 개발자도 쉽게 관리 가능한 코드여야 한다.

07. 기술적 문제