문제 분류 3 - 면접장에는 칸 이름이 없습니다

코딩 인터뷰 문제는 55개입니다 의 표는 왼쪽에서 오른쪽으로 읽습니다. 원형 이름이 있고, 그 옆에 Input 과 Output 이 있습니다.

면접은 반대입니다. 지문 하나가 주어지고, 칸 이름은 안 옵니다. 그러니 쓸 수 있으려면 오른쪽에서 왼쪽으로도 읽혀야 합니다.

1. 지문에서 보이는 것

지문을 읽을 때 눈에 걸리는 것들이 있습니다. 알고리즘 이름이 아니라, 그냥 적혀 있는 것입니다.

지문에 보이면	후보	가르는 질문
정렬돼 있다 · 정렬해도 된다	Two ends moving in · Boundary by monotonicity	짝을 찾나, 경계를 찾나
연속한 구간	Window over a sequence · Largest run	조건을 만족하는 구간인가, 합이 최대인 구간인가
늘어나기만 하는 가장 긴 것	Longest increasing subsequence	연속이어야 하나
각 자리에서 처음 만나는 더 크거나 작은 것	Next greater element	지금보다 작은 과거가 영영 쓸모없나
구간을 여러 번 묻는다	Prefix and range	중간에 값이 바뀌나
k번째	Kth element · Pull the best one next	한 번 묻나, 계속 묻나
합이 목표가 되는 둘 또는 셋	Pair with target	정렬해도 되나
몇 번 나왔나 · 과반 · 빠진 값	Count and tally	값의 범위가 좁나
어떻게 정렬할지부터 정해야 한다	Sort then scan	한 기준을 고정하면 나머지가 단순해지나
시작과 끝이 있는 것들	Intervals	시작으로 정렬하나, 끝으로 정렬하나
먼저 해야 할 일이 있다	Topological order	사이클이면 답이 없다
섬 · 덩어리 · 같은 그룹인가	Connected components	간선이 한꺼번에 오나, 하나씩 오나
사이클이 있나	Cycle	다음이 하나뿐인가, 여러 갈래인가
전부 잇는 최소 비용 · 최대로 흘릴 양	Spanning and flow	두 편으로 나뉘나
최소 비용 · 최소 걸음	Shortest path	가중치가 전부 1인가, 음수가 있나
격자	Walk a grid · Grid DP · Simulate on a grid	퍼지나, 한 방향으로만 가나, 규칙을 반복하나
행마다 정렬되고 열마다 정렬된 표	Search a sorted grid	한 줄로 펴도 정렬인가
행렬을 돌리거나 뒤집어라	Transform in place	추가 공간을 못 쓰나
트리	Walk a tree · Tree DP	한 번 훑으면 끝나나, 부분 트리마다 골라 가며 올라가나
순회 결과가 주어진다	Build a tree	뿌리를 어디서 아나
왼쪽이 작고 오른쪽이 큰 트리	Binary search tree	정렬된 수열을 만드나, 꺼내나
두 노드의 공통 조상	Lowest common ancestor	정렬 성질을 쓸 수 있나
회문	Palindrome	가운데에서 퍼지나, 양끝에서 좁히나
괄호나 연산자	Brackets and expressions	중첩이 있나
문자열이나 배열 둘	Edit distance · Common subsequence	고치는 비용인가, 공통인 것인가
긴 글에서 조각을 찾아라	Pattern in text	조각이 여럿인가
이 접두사로 시작하는 단어	Prefix set	질의가 반복되나
글자를 다시 배열한 것인가	Same letters	같은지만 보나, 같은 것끼리 묶나
규칙대로 고쳐 써라	Rewrite a string	규칙이 한 번에 끝나나, 나온 결과에 또 적용되나
단계마다 고른다	Carry state forward	상태 수를 미리 아나, 입력에 따라 늘어나나
방법이 몇 가지냐	Count the ways · Combinatorics	한 단계씩 세어 올라가나, 공식으로 한 번에 세나
구간을 합쳐 간다	Interval DP	마지막에 무엇을 하느냐로 나뉘나
한도나 목표를 두고 고른다	Knapsack	같은 걸 여러 번 쓰나
모든 배치를 보랜다	List every arrangement	가지치기가 되나
고른 것의 조합이 상태가 된다	Small n, every subset	부분집합만 상태로 쓰면 되나, 지금 어디인지도 들고 가야 하나
번갈아 둔다	Win or lose	판이 독립된 더미로 쪼개지나
하나만 빼고 짝이 맞는다	Bit tricks	짝이 몇 개씩 맞나
소수 · 약수 · 배수	Divisors and primes	하나를 보나, 범위를 보나
진법 · 자릿수 · 아주 큰 수	Digits and bases	자료형 범위를 넘나
무작위로 뽑아라	Chance and sampling	전체 크기를 미리 아나
연산 목록과 시간 제약	Design a structure	넣을 때 일을 해두나, 꺼낼 때 하나
용량이 차면 버려라	Cache and eviction	버리는 기준이 시간인가 횟수인가
한쪽 끝에서만 넣고 뺀다	Stack and queue discipline	최솟값 같은 걸 같이 묻나
넣고 빼고 찾기가 전부 빨라야 한다	Key to value	무작위 추출이 끼어 있나
하나씩 꺼내 달라	Iterate on demand	미리 다 펼쳐도 되나
노드가 이어져 있다	Linked list surgery	길이를 미리 아나

왼쪽은 답을 몰라도 보입니다. Monotonic Stack 은 단조 스택을 떠올려야 열리지만, "각 자리에서 다음으로 큰 것"은 지문에 그냥 적혀 있습니다.

2편의 55개 중 하나는 여기 없습니다. Geometry 는 지문에서 알아볼 신호가 "도형이 나온다" 말고는 없습니다. 신호가 약한 칸이 있다는 것도 알아둘 만합니다 — 그런 문제는 읽자마자 아는 수밖에 없습니다.

2. 제약 조건도 지문입니다

n 의 크기가 적혀 있으면 답의 복잡도가 거의 정해집니다.

  n ≤ 20          2ⁿ            부분집합을 전부 본다
  n ≤ 40          2^(n/2)       반으로 쪼개 만나기
  n ≤ 500         n³
  n ≤ 5,000       n²
  n ≤ 10⁵         n log n       정렬 · 이분탐색 · 힙 · 세그먼트 트리
  n ≤ 10⁷         n             한 번 훑기
  값이 10⁹까지     log(값) 또는 수학  크기가 아니라 수 자체가 크다

다만 이건 좁혀주는 것이지 정해주는 것이 아닙니다. n ≤ 20 이면 비트마스크 DP 일 수도 있고 그냥 백트래킹일 수도 있습니다. 후보를 몇 개로 줄여줄 뿐입니다.

3. 후보가 둘 이상일 때

여기서부터가 진짜입니다. 신호로 후보를 둘셋 줄였는데 그중 뭘 쓸지 모를 때, 이 순서로 묻습니다.

  ① 그냥 다 해보면 어떻게 하나
  ② 그게 왜 느린가
  ③ 무엇을 다시 안 해도 되나
  ④ 그래서 뭘 쓰나
  ⑤ 그게 왜 맞나

합이 K 이상인 가장 짧은 구간 으로 해보겠습니다.

  ①  모든 구간을 본다                        n²
  ②  왼쪽 끝을 옮길 때마다 합을 처음부터 다시 더한다
  ③  왼쪽 끝을 되돌릴 일이 없다 — 오른쪽을 늘렸다 왼쪽을 당기면 된다
  ④  슬라이딩 윈도우
  ⑤  합이 K 에 닿으면 왼쪽을 당겨도 되고, 모자라면 오른쪽을 늘려야 한다.
      양쪽 다 되돌아갈 일이 없으니 각 원소를 많아야 두 번 본다

③이 답입니다. 나머지는 거기 닿기 위한 질문입니다.

그리고 ③이 안 나오면 그 문제는 아직 모르는 겁니다. 방법 이름을 떠올렸는지와는 상관이 없습니다 — "슬라이딩 윈도우"라고 말할 수 있어도 ③을 못 하면 변형이 나왔을 때 막힙니다.

여기서 음수가 섞이면 ③이 깨집니다. 왼쪽을 당겨도 합이 줄어든다는 보장이 없으니까요. 가르는 조건 칸에 그렇게 적어둔 이유입니다.

4. 복습하는 법

  왼쪽만 보고 오른쪽을 가린다        신호 → 후보 → 가르는 질문 순으로 떠올린다
  막히면 ①~⑤ 를 소리 내서 한다      ③ 에서 막히는지 ④ 에서 막히는지 확인
  틀린 것을 더 자주 본다
  맞힌 것은 시간을 두고 다시 본다     바로 다시 보면 맞히는 게 당연하다

섞을 때는 헷갈리는 것끼리 섞습니다. 아무거나 뒤섞는 게 아니라 Window over a sequence 와 Largest run 처럼 Input 과 Output 이 거의 같은 것들을 나란히 놓습니다. 물어볼 것은 하나입니다 — 왜 이건 저 방법이 되는데 옆엣것은 안 되나.

섞으면 연습할 때는 더 못합니다

이걸 수학 문제로 잰 실험이 있습니다. 대학생 18명에게 낯선 입체 네 개의 부피 구하는 법을 가르치고, 한쪽은 같은 종류끼리 묶어서 연습시키고 다른 쪽은 네 종류를 섞어서 연습시켰습니다. 문제도 개수도 똑같고 순서만 달랐습니다.

  연습하는 동안      묶은 쪽  89%     섞은 쪽  60%
  일주일 뒤 시험     묶은 쪽  20%     섞은 쪽  63%

틀린 이유가 중요합니다. 묶어서 연습한 쪽은 계산을 틀린 게 아니라 어느 공식을 쓸지를 틀렸습니다. 공식만 맞게 적으면 답은 거의 다 맞았습니다.

묶어서 풀면 어느 것인지 고를 일이 없습니다. 알려주고 시작하니까요. Largest run 을 열 개 연속으로 풀면 열 번 다 답을 알고 시작합니다. 면접에는 그 알려주는 사람이 없습니다.

그런데 연습하는 동안에는 묶은 쪽이 더 잘합니다. 89% 대 60%. 그래서 섞으면 손해 보는 것처럼 느껴집니다. 그림을 보고 화가를 맞히는 다른 실험에서는 섞은 쪽이 더 나았던 사람이 120명 중 78% 였는데, 묶는 쪽이 낫거나 비슷했다고 답한 사람도 78% 였습니다. 시험을 치고 난 뒤에 물어봐도 그랬습니다. 느낌이 반대로 갑니다.

둘 다 실험실에서 대학생에게 잰 것입니다. 그리고 Rohrer & Taylor 는 자기 실험의 한계를 직접 넷 적어뒀는데, 그중 하나가 면접에는 제일 아픕니다 — 시험 문제가 연습 문제와 같은 꼴이어서, 처음 보는 변형에도 통하는지는 재지 않았습니다.

그리고 소리 내서 해보십시오. 면접은 푸는 시험이 아니라 푸는 과정을 보여주는 시험인데, 혼자 조용히 푸는 연습만 하면 그 부분이 훈련되지 않습니다. ①~⑤ 를 말로 하면 복습과 말하기가 같이 됩니다.

출처

Rohrer & Taylor 2007 · Doug Rohrer, Kelli Taylor, "The shuffling of mathematics problems improves learning", Instructional Science 35:481–498. 위 수치는 Experiment 2 입니다.
Kornell & Bjork 2008 · Nate Kornell, Robert A. Bjork, "Learning Concepts and Categories: Is Spacing the 'Enemy of Induction'?", Psychological Science 19(6):585–592. 위 수치는 Experiment 1a 입니다.

David learns to code