[번역] 14가지 패턴으로 코딩 인터뷰 완전 정복하기

*이번 포스팅은 "14 Patterns to Ace Any Coding Interview Question" 을 번역한 내용입니다.

코딩 인터뷰를 준비하는 과정은 많은 개발자들이 불안에 떨게 만듭니다. 엄청난 양의 내용을 커버해야하고, 개발자가 실제 업무하는 일과는 무관하게 느껴지기 때문에 스트레스를 가중합니다.

이런 이유 때문에 개발자들 사이에서는 수백가지의 인터뷰 문제들을 LeetCode같은 사이트를 이용해서 공부하는게 일상이 되었습니다. 불안한 개발자들이 인터뷰 전에 가장 많이하는 질문은 보통 내가 연습 문제 충분히 많이 풀었나? 더 해야하나? 입니다.

이런 이유 때문에 이번 글을 통해서 각 질문들의 기저에 깔려있는 패턴들을 다뤄보려고 합니다. ⎯ LeetCode에서 수백개의 문제를 풀면서 고통받지 않아도 되도록 돕고 싶기 때문입니다. 일반적인 패턴에 대한 이해가 있다면 그것들을 형식화해서 약간의 변형을 통해 나온 여러 문제들을 쉽게 풀어낼 수 있습니다.

여기에 가장 중요한 14가지 패턴을 소개합니다. 각 패턴의 정의를 설명하고, 예시를 들어주겠습니다. 이건 개요만 잡아주는 글이기 때문에 Grokking the Coding Interview: Patterns for Coding Questions 글을 참고하셔서 더 깊은 이해를 위한 설명, 예시, 코딩 연습을 해보세요.

여기서 다루는 패턴들은 이 글을 읽으시는 분들이 자료구조에 대한 기본 이해가 있다고 가정합니다.

1. Sliding Window

Sliding Window 패턴은 특정한 사이즈의 배열 혹은 링크드 리스트를 찾는데 사용합니다. 예를 들어 가장 긴 길이를 가진 부분 배열, 1을 반드시 포함하는 부분 배열을 모두 찾는 등이 있습니다. Sliding Window는 첫번째 요소에서 시작해서 오른쪽으로 이동하면서 사용하는데 문제에 따라 길이를 조정합니다. 어떤 케이스에서는 사이즈를 일정하게 유지하고 어떤 때는 사이즈가 커지거나 줄어듭니다.

다음은 주어진 문제에서 Sliding Window를 사용할지 생각해볼 수 있는 몇가지 경우이다.

문제 입력이 링크드 리스트, 배열, 혹은 문자열과 같은 선형 데이터 구조일 때
가장 긴/짧은 부분 문자열, 부분 배열, 특정 값을 요구할 때

Sliding Window 패턴을 사용하는 문제:

Maximum sum subarray of size “K" (easy)
Longest substring with ‘K’ distinct characters (medium)
String anagrams (hard)

2. Two Pointers or Iterators

Two Pointers는 두 포인터가 데이터 구조를 하나 혹은 두 포인터가 모두 특정 조건을 만족할 때까지 순회하는 패턴입니다. Two Pairs는 링크드리스트나 정렬된 배열에서 pairs를 검색할 때 유용합니다. 예를 들어, 배열의 각 요소를 다른 요소를 비교할 때 입니다.

Two Pointers는 하나의 포인터만 있으면 배열을 계속 반복해야하기 때문에 필요합니다. 단일 반복자를 이용해 앞뒤로 이동하는 것은 시간 및 공간복잡성이 비효율적입니다. ⎯ 이런 개념은 점근적 분석이라고 합니다. 포인터가 하나일 때 부르트 포스나 단순 솔루션이 작동하는 동안 O(N\(^{2}\)) 이 되는 경우가 많은데, Two Pointers를 사용하면 시공간 복잡도가 더 나은 솔루션을 찾는데 도움이 될 수 있습니다.

Two Pointer 사용할 시기를 찾는 방법:

linked list 혹은 sorted array를 사용하고 특정 조건을 충족하는 요소 집합을 찾아야 할 때
배열의 요소 집합이 pairs, triplet, 혹은 부분배열 일 때

Two Pointer 패턴을 사용하는 문제:

Squaring a sorted array (easy)
Triplets that sum to zero (medium)
Comparing strings that contain backspaces (medium)

3. Fast and Slow Pointers

Hare & Tortoise 알고리즘이라고도 하며, 배열을 서로 다른 속도로 이동하는 두 개의 포인터를 사용합니다. 이 접근 방식은 순환 연결 리스트나 배열을 다룰 때 유용합니다.

서로 다른 속도로 이동함으로써 두 포인터가 반드시 만나야 함을 이용해서 증명합니다. 두 포인터가 순환 루프에 있으면 빠른 포인터가 느린 포인터를 잡아야 합니다.

Fast and Slow Pointers를 식별하는 방법:

linked list 혹은 array 순환을 다룰 때
특정 요소의 위치나 linked list의 전체 길이를 알아야 할 때

2번에서 언급한 Two Pointer 방식 말고 선택해야 하는 이유?

단일 linked list와 같이 뒤로 이동할 수 없는 경우가 있습니다. 적절한 예시로는 linked list가 palindrome인지 확인하는 경우가 있습니다.

문제:

Linked List Cycle (easy)
Palindrome Linked List (medium)
Cycle in a Circular Array (hard)

4. Merge Intervals

Merge Intervals 패턴은 겹치는 간격을 처리하는 효과적인 방법입니다. 간격에 관한 많은 문제에서 겹치는 간격을 찾거나 병합해야 합니다. 패턴은 다음과 같이 작동합니다.

두 개의 간격 (a와 b)이 주어지면 두 간격이 서로 관련될 수 있는 6가지 방법이 있습니다.

Merge Intervals 패턴을 식별하는 방법:

상호 배타적인 간격만 있는 리스트를 생성하라는 요청을 받거나, "overlapping intervals" 용어가 들어갔을 때.

문제:

Intervals Intersection (medium)
Maximum CPU Load (hard)

5. Cyclic sort

Cyclic sort(순환 정렬) 패턴은 주어진 범위의 숫자를 포함하는 배열에 사용합니다. 한 번에 한 숫자씩 배열을 반복합니다. 반복하는 현재 숫자가 올바른 인덱스에 없으면 올바른 인덱스에 있는 숫자로 교체합니다.

Cyclic sort를 식별하는 방법:

주어진 범위의 숫자가 있는 정렬된 배열 관련 문제에서 사용할 수 있고, 문제가 정렬 혹은 회전된 배열에서 누락되거나 중복되는 가장 작은 숫자를 찾도록 요청할 때 사용할 수 있습니다.

문제:

Find the Missing Number (easy)
Find the Smallest Missing Positive Number (medium)

6. In-place reversal of linked list

연결 리스트에 있는 노드 집합 간의 순서를 바꾸라는 요청을 받을 수 있습니다. 종종 이런 경우 제약 조건으로 기존 노드 개체를 사용하고 추가 메모리를 사용 하지 않고 제자리에서 작업을 수행해야합니다. 이럴 때 In-place reversal of linked list는 유용합니다.

In-place reversal of linked list는 현재 연결 리스트에서 head를 가리키고 있는 current와 처리한 이전 노드를 가리키는 previous 요소를 시작으로 한 번에 하나의 노드를 뒤집습니다. 잠금 단계로, 다음 노드로 넘어가기 전에 이전 노드를 가리키도록 해서 현재 노드를 되돌립니다. 또한, previous 요소를 이미 진행한 current 요소값으로 업데이트합니다.

In-place reversal of linked list를 식별하는 법:

링크드 리스트를 추가 메모리 없이 뒤집으라고 요청받는다.

문제:

Reverse a Sub-list (medium)
Reverse every K-element Sub-list (medium)

7. Tree breadth-first search

Tree breadth-first search(트리 너비 우선 탐색)패턴은 큐를 사용해 다음 레벨로 점프하기 전에 현재 레벨의 모든 노드를 추적합니다. 레벨별 트리 순회에 관련한 모든 문제는 이 접근 방식을 사용할 수 있습니다.

트리 너비 우선 검색 패턴은 루트 노드를 대기열로 푸시한 다음 대기열이 비어있을 때까지 계속 반복하는 방식으로 작동합니다. 각 반복에 대해 대기열 가장 앞에 있는 노드를 제거하고 해당 노드를 방문합니다. 대기열에서 각 노드를 제거한 뒤 모든 children을 대기열에 삽입합니다.

트리 BFS 식별하는 방법:

레벨별 방식이나 레벨 순서대로 트리를 탐색하라는 요청을 받는 경우

문제:

Binary Tree Level Order Traversal (easy)
Zigzag Traversal (medium)

8. Tree depth-first search

Tree depth-first search(트리 깊이 우선 탐색)는 DFS 탐색이라 합니다. 재귀(또는 반복 접근 방식의 경우 스택)를 사용해 모든 이전(상위) 노드를 추적할 수 있습니다.

트리 DFS 패턴은 트리의 루트에서 시작합니다. 노드가 리프가 아닌 경우 다음 작업을 수행해야 합니다.

1. 현재 노드를 지금 처리할 지(pre-order), 두 자식 처리 사이(in-order), 모든 처리를 마힌 후(post-order)에 할지 결정합니다.
2. 현재 노드의 두 자식 모두에 대해 두번의 재귀 호출을 수행해 처리합니다.

트리 DFS 패턴을 식별하는 방법:

in-order, preorder, postorder DFS를 사용해 트리를 탐색하라는 메세지가 표시되어 있는 경우
노드가 잎에 가까운 곳을 검색해야하는 문제일 경우

문제:

Sum of Path Numbers (medium)
All Paths for a Sum (medium)

9. Two heaps

많은 문제에서 두 부분으로 나눌 수 있는 요소 집합이 주어집니다. 문제를 해결하기 위해 우리는 하나의 파트에서 가장 작은 요소와 다른 파트에서 가장 큰 요소를 알아내는데 관심이 있습니다. 이런 문제들에서 유용한 패턴입니다.

이 패턴은 두 개의 heap을 사용합니다. 최소 힙은 가장 작은 요소를 찾고 최대 힙은 가장 큰 요소를 찾습니다. 패턴은 최대힙에 숫자 전반부를 저장하는 방식으로 시작합니다. 전반부에서 가장 큰 수를 찾고 싶기 때문입니다. 그 다음 후반부에서 가장 작은 숫자를 찾고 최소힙에 저장합니다. 숫자 리스트의 중앙값은 두 힙의 맨 위 요소에서 계산할 수 있습니다.

Two Heaps 패턴을 식별하는 방법:

Priority Queue, Scheduling과 같은 상황에서 유용
문제에서 집합의 가장 작은/최대/중간 요소를 찾아야한다고 명시되어 있는 경우
이진 트리 데이터 구조가 특징인 문제에서 가끔 사용

Two Heaps 패턴 문제:

Find the Median of a Number Stream (medium)

10. Subsets

집합의 순열 조합 문제는 코딩 인터뷰의 단골 문제입니다. Subsets 패턴은 이런 문제를 해결하기 위한 효율적인 BFS 방식을 설명합니다.

패턴은 다음과 같습니다.

[1, 5, 3] 세트가 주어졌을 때,

1. 빈 집합으로 시작 [[]]
2. 모든 기존 하위 집합에 숫자 1을 추가해 새 하위 집합을 만든다. [[], [1]];
3. 기존의 모든 하위 집합에 두번째 숫자 5를 추가한다. [[]. [1], [5],[1,5]];
4. 모든 기존 하위 집합에 세번째 숫자 3을 추가한다. [[]. [1], [5],[1,5], [3], [1,3], [5,3],[1,5,3]];

Subsets 패턴을 식별하는 방법:

주어진 집합의 조합이나 순열을 찾아야 할 때

문제:

Subsets With Duplicates (easy)
String Permutations by changing case (medium)

11. Modified binary search

정렬된 배열, 연결 리스트, 행렬에서 특정 요소를 찾는데는 이진 검색이 가장 좋은 선택입니다. 이 패턴은 모든 이진 검색 관련된 문제를 해결하는데 효율적입니다.

수정된 이진 검색 패턴 식별하는 방법:

정렬된 무한 배열 문제에서 순서에 상관없는 이진 검색 또는 검색을 해결할 수 있습니다.

문제:

Order-agnostic Binary Search (easy)
Search in a Sorted Infinite Array (medium)

12. Top K element

주어진 집합에서 가장 높은/ 가장 작은/ 빈번한 'K' 요소를 찾도록 요청하는 모든 문제는 이 패턴에 해당합니다.

'K'요소를 추적할 때 가장 좋은 데이터 구조는 Heap 입니다. Heap이 요소를 계속 추적하기 때문에 정렬 알고리즘은 필요하지 않습니다.

Top K element 패턴 식별하는 방법:

주어진 집합의 최상위/가장 작은/빈번한 'K' 요소를 찾도록 요청받는 경우
정확한 요소를 찾기 위해 배열을 정렬하라는 메시지가 표시되는 경우

문제:

Top ‘K’ Numbers (easy)
Top ‘K’ Frequent Numbers (medium)

13. K-way Merge

K-way Merge 패턴은 배열 집합에 관한 문제를 해결하는데 도움이 됩니다.

'K' 정렬된 배열이 주어지면 힙을 사용해 모든 배열의 모든 요소에 대한 정렬된 순회를 수행할 수 있습니다. 최소힙에 있는 각 배열의 가장 작은 요소를 푸시하면서 전체 최소값을 얻을 수 있습니다. 전체 최소값을 얻은 후, 동일한 배열의 다음 요소를 힙으로 푸시합니다. 이 과정을 반복해 모든 요소가 정렬된 순회를 만듭니다.

K-way Merge 패턴을 식별하는 방법:

정렬된 배열, 리스트, 행렬을 사용합니다.
정렬된 리스트를 Merge하거나, 정렬된 리스트의 가장 작은 요소를 찾을 때 사용합니다.

문제:

Merge K Sorted Lists (medium)
K Pairs with Largest Sums (Hard)

14. Topological sort

토폴로지 정렬은 서로 종속된 요소의 선형 순서를 찾는데 사용합니다. 예를 들어, 이벤트 'B'가 이벤트 'A'에 종속된 경우 토폴로지 순서에서 'A'가 'B'보다 먼저 옵니다.

토폴로지 정렬을 식별하는 방법:

그래프나 방향없는 순회를 다룰 때
모든 개체를 정렬된 순서로 업데이트 하라고 할 때
특정 순서에 따르는 객체 클래스가 있는 경우

문제:

Task scheduling (medium)
Minimum height of a tree (hard)

코딩 인터뷰를 준비할 때 도움이 되었으면 좋겠습니다. Happy Hacking!

저작자표시 비영리 변경금지

'📒 Tech Note > 알고리즘 & 자료구조' 카테고리의 다른 글

[LeetCode] 153. Find Minimum in Rotated Sorted Array (0)	2022.09.24
[LeetCode] 152. Maximum Product Array (0)	2022.09.08
[LeetCode] 53. Maximum Subarray (0)	2022.09.03
[LeetCode] 238. Product of Array Except Self (0)	2022.08.24
[LeetCode] 217. Contains Duplicate (0)	2022.08.24