study coding_interview 기술적 문제 자료구조 알고리즘 BUD

기술적 문제(1) 면접 준비하기

알고 있어야 할 것들

6일차

게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.89 ~ p. 108

내용 정리

7. 기술적 문제

최고의 테크 회사들은 면접의 기초로 기술적 문제들을 삼는다.

준비하기

  1. 직접 풀도록 노력하라 : 직접 답을 찾도록 노력하고 포기하지 말자
  2. 코드를 종이에 적으라 : 코드 문법 강조, 코드 자동 완성 없는 것에 익숙해져보자.
  3. 코드를 테스트하라 : 종이에서 해야한다.
  4. 종이에 적은 코드를 그대로 컴퓨터로 옮긴 뒤 실제로 실행해 보라 : 어디에서 실수가 있었는지 체크하고 유의하자.

가상 면접 경험도 중요하다.

알고 있어야 할 것들

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

기초적인 것을 알고 있어야 한다.

자료구조 알고리즘 개념
연결리스트(Linked Lists) 너비 우선 탐색(BFS) 비트 조작(Bit Manipulation)
트리, 트라이(Tries), 그래프 깊이 우선 탐색(DFS) 메모리(스택 VS 힙)
스택 & 큐 이진 탐색 재귀
힙(Heaps) 병합 정렬(Merge Sort) 동적 프로그래밍(Dynamic Programming)
Vector / ArrayList 퀵 렬 big-O 시간 & 공간
해시테이블    

이 주제에 대해 사용법, 구현법, 애플리케이션, 그리고 가능하다면 공간과 시간 복잡도에 대해서 알아두기 바란다. 특히 해시테이블은 중요하다.

####

2의 승수(power of 2) 표

반드시 외울 필요는 없지만 알아두면 유용하다.

X 2^X 근사치 메모리 요구량
7 128    
8 256    
10 1024 천 1K
16 65,536   64K
20 1,048,576 백만 1MB
30 10,737,418,824 십억 1GB
32 4,294,967,296   4GB
40 1,099,511,627,776 조 1TB

실제 문제 살펴보기

링크에서 다양한 자료를 볼 수 있다.

원하는 것이 무엇인가

모든 문제에 즉시 답하지 못하더라도 괜찮다. 그러니 면접관이 하는 말을 잘 듣자.

  1. 경청하기 : 잘 듣고 정확히 이해해야하며, 확실하지 않은 부분은 질문을 통해 반드시 짚고 넘어가야 한다. 문제와 관련된 모든 독특한 정보를 기억해두자.

  2. 예제를 직접 그려보기 : 명확하고, 충분히 크며, 특별하지 않은 예제를 만들어보자.

  3. 무식한 방법으로 일단 해보기 : brute force로 먼저 시도해보자. 이 후 개선해 나가자.

  4. 최적화

    • 간과한 정보를 확인하기

    • 새로운 예제를 만들어 보기
    • ‘잘못된 방식’으로 문제를 풀어보기
    • 시간과 공간의 실익을 따져 보고 균형을 맞추기
    • 정보를 미리 계산하기
    • 해시테이블을 사용하기
    • 최선의 수행 시간(BCR) 생각하기

  5. 검토하기 : 바로 코딩에 뛰어들지 말고 생각하며 이해를 확실히 할 시간을 갖자.

  6. 코드 작성하기

    • 모듈화된 코드 사용하기
    • 에러를 검증하기
    • 필요한 경우에 다른 클래스나 구조체 사용하기
    • 좋은 변수명 사용하기

  7. 테스트

    • ‘개념적’ 테스트부터 시작하기
    • 코드에서 평소와는 다르게 돌아가는 부분 유의깊게 보기
    • 버그가 자주 발생하는 부분 주의하기
    • 작은 규모의 테스트 돌려보기
    • 특별한 경우를 테스트하기

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

BUD : Bottlenecks(병목현상), Unnecessary Work(불필요한 작업), Duplicated Work(중복되는 작업)을 뜻하는데, 알고리즘이 비효율적으로 동작하는 가장 흔한 이유이다.

병목현상(bottlenecks)

일반적으로 두 가지 이유로 인해 발생한다.

  • 어떤 부분 떄문에 알고리즘이 느려지는 경우 : 두 단계로 이루어진 알고리즘에서 첫 번째 단계가 O(NlogN), 두 번째 단계가 O(N)이 소요된다고 가정하면, 두번째 단계가 O(1)로 줄어도 의미가 없다. O(NlogN)이 알고리즘의 병목점이기 때문이다.
  • 검색을 여러 번 하는 것처럼 반복적으로 수행하는 부분이 여러 개 있는 경우

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

(1,3), (3,5), (5,7), (7,9)

brute force를 이용하면, 배열의 원소를 처음부터 순회하며 나머지 워놋들과 쌍을 만든다. 모든 쌍의 차이를 구한 뒤 그 차이가 k개 인 갯수를 센다. 여기서 병목점은 쌍의 두 번째 원소를 반복적으로 찾을 때이다.

이 병목점을 해결해보자. 첫번째 원소가 x라면, 두번째 원소는 x+k 나 x-k 둘 중 하나가 되어야 한다.배열이 정렬되어있다면 이진 탐색으로 O(logN)이 걸리고 모든 원소에 사용하면 O(NlogN)이 걸린다.

이렇게 되면 알고리즘의 두 단계 모두 O(NlogN)이 걸린다. 더 최적화를 걸고 싶다면 첫 번째 단계를 없애 정렬되지 않은 배열을 이용한다. 이를 위해서 배열의 모든 원소를 해시테이블에 넣으면 된다.

불필요한 작업(unnecessary work)

예제 : a, b, c, d가 1에서 1000 사이에 있는 정수 값 중 하나일 때 a^3 + b^3 = c^3 + d^3을 만족하는 모든 자연수를 출력하시오.

brute force로 풀려면 4중 루프를 이용해야 한다. 하지만 생각해보면 d를 계산하는 반복문은 무의미하다. a,b,c가 결정되면 d도 값이 하나 뿐이기 때문이다. 따라서 반복문을 쓰지 않고 a,b,c를 이용해 d를 계산해내면 된다. 이러면 O(N^4) 를 O(N^3)으로 줄일 수 있다.

중복되는 작업(duplicated work)

방금 예제를 살펴보자. 각각 (a,b) 쌍마다 모든 (c,d) 쌍을 구할 필요 없이 (c,d) 쌍의 배열 중 찾는 방법도 있다. 해시테이블을 이용하면 빠르게 구할 수 있다. c^3 + d^3 이 키(key)가 되고 (a,b) 쌍의 리스트가 값(value)이 되도록 해시테이블을 만든 뒤, 키 값을 통해 가능한 모든 (c,d)쌍을 찾으면 된다. (c,d)쌍을 만들고 따로 (a,b)쌍을 반복해서 만들 필요도 없어진다. 이러면 O(N^3)을 O(N^2)까지 줄일 수 있다.

최적화 및 문제풀이 기술 2: 스스로 풀어보라 DIY(Do It Yourself)

이진탐색 모르는 상태에서, 알고리즘에서 개념을 생각해내긴 힘들지만 알파벳순으로 정렬된 사전에서 찾는다면 자연스럽게 이용할 것이다. 너무 컴퓨터로만 생각해내지 말고 실제 예제로 생각해서 풀어보자.

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

(여기서 왜 갑자기 문자열 a가 나오는지 모르겠다.. 아마 s의 모든 순열을 찾으라는게 문제인듯 한데 번역 오류던가 오타가 아닐까.. 부드럽게 바꿔보았다. )

s에서 가능한 모든 순열을 나열한 뒤 b를 찾는 방법은 너무 극단적으로 느리다. 직접 예제를 만들어서 찾아보면 두 가지 방법 중 하나를 쓰게 된다.

  1. s의 길이만큼 b를 끊어서 살펴보며 s의 순열인지 확인하기
  2. b의 문자를 앞에서부터 차례로 보면서 s에 속한 문자가 보이면 그 이후 b의 길이만큼을 s의 순열인지 확인하기

이 방식을 이용하면 O(BS), O(BSlogS),O(BS^2) 중 하나의 시간복잡도로 될 것이다.

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

여러 단계를 걸쳐야 한다. 첫번째, 자료형(data type)과 같은 제약조건을 단순화하거나 변형시킨다. 두번째, 단순화된 버전의 문제를 푼다. 세번쨰, 단순화된 문제의 알고리즘이 완성되면 해당 알고리즘을 보다 복잡한 형태로 다듬어 간다.

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

문제를 단순화하여 단어대신 글자 하나씩 오리는 것으로 바꿔보자. 배열을 만들어 글자의 출현 빈도를 세기만 하면 풀 수 있다. 잡지에서 충분히 출현하는지 확인한다. 실제 알고리즘에선 배열 대신 해시테이블을 이용하면 된다.

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

n=1 부터 구하고 이 해법을 통해 n=3, n=4로 나아간다.

예제 : 문자열의 모든 순열을 계산하는 알고리즘을 설계하라. 모든 문자는 문자열 내에서 고유하게 등장한다.

abc는? ab에서 가능한 모든 지점에 c를 넣어보면 된다. 자연스레 재귀 알고리즘으로 구현된다.

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

여러 자료구조를 하나씩 써보다보면 풀릴수도 있다.

예제 : 임의의 숫자를 만들어 낸 뒤 확장 가능한 배열에 차례로 저장한다. 새로운 입력이 들어올 때마다 중간값(median)을 구하려면 어떻게 해야 하는가?

하나씩 생각해보자.

  • 연결리스트 : 정렬이나 특정 숫자에 접근하기 안좋으므로 X
  • 배열 : 이미 주어졌다. 가능은 하지만 우선 제쳐둔다.
  • 이진트리 : 가능하긴 할듯. 순서 유지에 유리하다. 그런데 가운데에 2개가 온다면 곤란해질듯. 일단 제쳐두자.
  • 힙 : 순서, 최댓값, 최솟값에 좋다. 어떻게 쓸지 고민해보자. 최소힙, 최대힙 두개를 쓰면 되지 않을까?

문제를 많이 풀수록 위 과정이 빨라진다.

읽고나서

오늘 기초적으로 꼭 알아야 할 개념들에 대해서도 나왔고, 마지막 여러가지 문제 접근 방법들은 면접뿐 아니라 알고리즘 문제를 풀때도 도움이 될것 같다. 꼭 알아야 하는 기초 개념들은 시간을 들여 꼭 정리해야겠다.

CATALOG
    coding_interview