[코드 인터뷰 대비 시리즈 #2] 배열/문자열 문제 접근 패턴 정리: 투 포인터, 슬라이딩 윈도우, 문자열 패턴 매칭을 단계별로 깊게 파헤치기

여러분, 코딩 인터뷰를 대비하며 알고리즘 문제를 풀다 보면, 배열(Array)과 문자열(String) 문제에서 시작하는 경우가 아주 많습니다. 왜일까요? 이 두 자료구조는 프로그래밍에서 가장 기본적이면서도, 문제 출제자가 난이도와 형태를 손쉽게 조절할 수 있는 재료이기 때문입니다. 이번 글에서는 배열과 문자열 문제를 다루는 과정에서 자주 등장하는 접근 패턴을 하나하나 아주 구체적으로 파헤쳐 볼게요.

단순히 “투 포인터를 써라”, “슬라이딩 윈도우를 적용하라”, “KMP로 문자열 검색 시간 단축” 같은 키워드에 머무르지 않고, 각 패턴을 적용하는 정확한 단계, 문제를 접했을 때 머릿속에서 어떤 논리적 흐름으로 접근 방법을 도출하는지, 면접 상황에서 어떻게 이를 설명할지, 그리고 실제 구현 시 어떤 점에 유의해야 하는지까지 꼼꼼히 짚어보겠습니다.

여러분이 이 글을 읽고 나면, 투 포인터나 슬라이딩 윈도우를 처음 듣는 사람도 “아, 이게 이런 상황에서 이렇게 쓰이는구나” 하고 확실히 이해하게 되고, 문자열 패턴 매칭 기법(KMP, Rabin-Karp)이나 아나그램 처리 방법도 한층 명확하게 파악할 수 있을 거예요.

1. 배열 문제 접근의 기초: "문제 구조 파악"에서 시작하기

배열 문제를 풀기 전에 먼저 우리가 해야 할 일은 문제의 구조를 파악하는 것입니다. 문제가 배열을 입력으로 주고, 특정 특성을 가진 부분 배열을 찾거나, 배열 원소들 간의 관계를 분석하거나, 배열을 재배치하는 것을 요구할 때, 가장 먼저 해볼 만한 접근은 다음과 같습니다.

(1) 단순 순회 연습:
문제를 받으면, 첫 번째 단계로 모든 원소를 단순 순회하며 무언가를 계산하는 기법(합, 최대/최소, 빈도 카운트 등)을 떠올려보세요. 예를 들어 “배열에서 최댓값 찾기” 문제는 매우 단순하지만, 이를 베이스로 “배열에서 특정 조건을 만족하는 원소 개수 세기”, “누적 합 배열(prefix sum array) 만들어서 구간 합 빠르게 구하기” 등으로 확장할 수 있습니다. 누적 합 배열은 추후 슬라이딩 윈도우나 부분 합 문제를 해결할 때 밑거름이 되므로, 이 기본을 잘 익혀두면 좋습니다.

(2) 정렬과 이진 탐색 활용:
배열 문제에서 “정렬 가능”이라는 조건이 주어지면 정렬 후 이진 탐색으로 문제를 최적화할 수 있는지 생각해보세요. 예를 들어, 목표값 target이 배열 내 존재하는지 확인하는 문제를 브루트포스로 O(N)에 할 수도 있지만, 정렬 후 이진 탐색하면 O(log N)에 확인할 수 있습니다. 면접 상황에서 “정렬된 배열이므로 O(N) 순회 대신 O(log N)에 값 탐색 가능”이라고 말하면 최적화 사고를 보여줄 수 있어요.

LeetCode의 “Binary Search” 문제나 Baekjoon의 이진 탐색 문제들을 통해 실전 감각을 키워보세요.

2. 투 포인터(Two Pointers) 기법: 정렬된 배열 문제에서 최적화하기

투 포인터 기법은 정렬된 배열을 다룰 때 특히 강력한 무기입니다. 예를 들어, 다음과 같은 문제를 가정해봅시다.

문제 상황 예시:
정렬된 배열 arr와 목표 합 target이 주어지고, arr[i] + arr[j] = target을 만족하는 (i,j) 쌍을 찾으라고 합시다. i<j라 가정하면, i를 0, j를 arr.size()-1 로 두고 시작합니다.

단계별 사고 과정:

1. 정렬 조건 인식:
   문제에서 배열이 정렬되어 있다고 했을 때, “정렬 특성을 이용할 수 있을까?”라는 질문을 던집니다. 정렬되어 있다면 양 끝에서 시작하는 투 포인터를 상상해보세요.
2. 양 끝 포인터 설정:
   left = 0, right = arr.size() - 1로 설정합니다. 이때 arr[left]는 작은 값, arr[right]는 큰 값이죠.
3. 합 비교와 포인터 조정:
   sum = arr[left] + arr[right]를 계산합니다.
   • sum == target이면 답을 찾은 것입니다.
   • sum < target이면 더 큰 합이 필요하므로 left++해서 합을 증가시킵니다.
   • sum > target이면 합이 너무 크므로 right--해서 합을 줄입니다.
4. O(N)에 해결 가능성:
   이렇게 하면 모든 원소 쌍을 다 살펴볼 필요 없이 포인터 이동만으로 O(N)에 문제 해결이 가능해집니다. 면접에서 이 과정을 보여주면 “정렬 특성을 이용해 O(N) 시간에 해결했다”는 최적화 능력을 평가받을 수 있습니다.

예제 문제로 LeetCode "Two Sum II" 문제나 유사한 two pointer 활용 문제를 풀어보시면 실전 감각이 올라갑니다.

코너 케이스 생각하기:

• 배열 길이가 1 이하인 경우, 두 수를 만들 수 없으니 즉시 에러 처리 가능.
• target보다 매우 작은 값만 있거나, 매우 큰 값만 있는 배열이라면 적절히 포인터 조정 후에도 답이 없으면 “No pair found”라는 에러 반환(예: std::expected를 사용).

면접 중 “투 포인터를 쓴다”라고만 말하지 말고, “정렬된 배열이므로 양 끝에서 시작하는 포인터를 조정하여 O(N)에 목표 합을 찾을 수 있어요”라며 아이디어 발생 과정을 설명해 주세요.

3. 슬라이딩 윈도우(Sliding Window) 기법: 연속 구간 처리 최적화

슬라이딩 윈도우는 “연속 구간” 문제에서 자주 등장합니다. 예를 들어, 길이 N인 배열에서 길이 K인 모든 부분 배열의 합을 구하는 문제를 생각해봅시다. 단순 접근으로 모든 K 길이 부분 배열의 합을 각각 O(K) 시간에 구하면 O(NK) 시간 복잡도지만, 슬라이딩 윈도우로 처음 K 길이 구간 합을 계산한 뒤, 윈도우를 한 칸 이동할 때마다 들어오는 원소를 더하고, 나가는 원소를 빼는 식으로 O(1)에 업데이트할 수 있으니 전체가 O(N)에 가능합니다.

단계별 사고 과정:

1. 연속 구간 문제 인식:
   문제에서 “연속된 부분 배열”이나 “연속된 부분 문자열”에 대한 처리 요청이 있다면, "슬라이딩 윈도우를 쓸 수 있을까?"라고 질문합니다.
2. 윈도우 정의하기:
   슬라이딩 윈도우는 시작 인덱스(start), 끝 인덱스(end)를 관리하며, 이 윈도우가 표현하는 부분 배열 또는 부분 문자열을 추적합니다. 초기에는 start=0, end=0으로 시작한 뒤 윈도우 크기나 조건에 따라 end를 늘리거나, 필요하면 start를 증가시켜 윈도우를 오른쪽으로 밀어냅니다.
3. 조건 만족 여부 체크:
   예를 들어, “K 길이 부분 배열의 합이 최소값을 갖는 구간 찾기”라면, end를 움직여 K 길이 구간을 만들고 합을 계산한 뒤, 다음 스텝에서 start++, end++로 윈도우를 이동시키며 합을 업데이트합니다.
4. 복잡도 및 최적화 논리 제시하기:
   면접관에게 "이 방법으로 각 요소는 최대 2번 정도(들어오고 나갈 때) 처리하므로 O(N) 시간에 문제 해결이 가능하다"라고 강조하세요. 단순 브루트포스 대비 얼마나 개선되었는지, 왜 이 방법이 효율적인지 구체적으로 언급하면 좋습니다.

슬라이딩 윈도우는 LeetCode의 "Minimum Size Subarray Sum" 문제, Programmers에서 슬라이딩 윈도우 응용 문제가 나올 때 유용합니다.

코너 케이스 생각하기:

• K가 N보다 크면 윈도우를 만들 수 없으므로 에러 반환.
• 빈 배열, 음수 값, 조건 만족 구간이 없는 경우 등도 std::expected로 처리 가능.
• 면접관에게는 “조건 불만족 시나리오를 미리 생각해 예외 처리하겠다”라고 어필하면 꼼꼼함을 드러낼 수 있어요.

4. 문자열 패턴 매칭: KMP, Rabin-Karp, 아나그램 처리

문자열 문제에서는 부분 문자열을 효율적으로 찾는 패턴 매칭 알고리즘이 중요합니다. 단순 O(N*M) 방식보다 KMP(Knuth-Morris-Pratt)를 사용하면 O(N+M)으로 부분 문자열 검색이 가능합니다. 면접관에게 이것을 언급하면 최적화 사고를 보여줄 수 있어요.

KMP 알고리즘 단계별 정리:

1. 패턴 전처리:
   패턴 P에 대해 접두사와 접미사가 일치하는 최대 길이를 담은 lps(Longest Prefix Suffix) 배열을 만들어요. 이 전처리로 P를 본문 T와 매칭 시도할 때 불일치 시 패턴 점프를 효율화합니다.
2. 본문 탐색:
   본문 T를 순회하며 P와 매칭 시도. 불일치 시 lps 배열을 참조해 패턴 인덱스를 건너뛰므로 O(N+M) 시간에 검색이 끝납니다.
3. 면접 시 표현:
   “KMP를 사용하면 패턴 전처리에 O(M), 본문 탐색 O(N)으로 전체 O(N+M) 시간에 부분 문자열 검색이 가능해요. 단순 브루트포스 O(N*M)보다 훨씬 효율적이죠.”

Rabin-Karp 알고리즘은 해싱을 이용해 평균적으로 O(N+M) 부분 문자열 검색을 가능하게 하나, 해시 충돌 처리 로직이 필요하다는 점을 언급하고, 면접관에게 “충돌이 없으면 빠른데 최악 O(N*M)일 수도 있습니다”라고 설명하세요.

아나그램 문제에서는 두 문자열이 같은 문자 빈도 분포를 갖는지 확인합니다. 이를 위해 정렬 후 비교(O(N log N))나 빈도 카운트(O(N))를 사용합니다. 빈도표를 해시맵 또는 고정된 문자셋이라면 정적 배열로 관리해 O(N)에 아나그램 여부 판단이 가능하다는 점을 강조하십시오.

예를 들어 LeetCode "Valid Anagram" 문제나, Baekjoon에서 문자열 패턴 매칭 문제가 나오면 이런 아이디어를 바로 적용할 수 있습니다.

5. 고급 문자열 알고리즘(접미사 배열, Trie) 언급

면접에서 접미사 배열(Suffix Array)나 Trie, 접미사 트리(Suffix Tree) 등을 직접 구현할 일은 드물지만, 이들의 존재와 개념을 언급하면 “이 지원자는 문자열 처리에 깊은 배경지식이 있구나”라는 인상을 줄 수 있습니다. 접미사 배열로 O(N log N) 전처리 후 O(M)로 부분 문자열 쿼리 처리 가능하다는 간단한 언급만으로도 전문성을 나타낼 수 있습니다.

Trie는 문자열 집합에서 접두사를 효율적으로 다루는 데 사용하며, 단어 필터링, 자동완성 문제 등에 응용할 수 있다고 설명하면 면접관이 여러분을 고급 문자열 문제에도 대비된 후보자로 볼 수도 있어요.

6. 조건부 처리, 비동기 처리, 로깅, 에러 처리, Ranges 활용 상세화

조건부 처리:
예를 들어, 슬라이딩 윈도우를 이용해 K 길이 부분 배열 합을 구하는 문제에서 K가 N보다 크면 부분 배열을 만들 수 없습니다. 이때 std::expected로 “K larger than array size”라는 에러를 반환하고, 면접 상황에서는 “입력이 유효한지 사전에 체크했다”라고 어필할 수 있어요.

비동기 처리 (Coroutine):
문자열이 매우 길거나, 스트리밍으로 데이터를 받는 상황이라면 coroutine을 통해 비동기 패턴 매칭을 구현할 수도 있습니다. 면접에서 이렇게까지 언급하면 굉장히 높은 수준의 확장성을 생각하는 지원자로 보일 겁니다.

로깅(std::format):
알고리즘 처리 중간에 어떤 변화가 일어나는지 콘솔에 로깅하는 것이 실전 면접에서 필수는 아니지만, “만약 디버깅이 필요할 경우 std::format으로 깔끔하게 메시지를 찍어볼 수 있다”라고 말하면 코드 품질과 디버깅 역량을 어필할 수 있죠.

Ranges 활용:
여러 입력 케이스에 대해 슬라이딩 윈도우 로직이나 투 포인터 로직을 연속 적용해야 한다면, Ranges 라이브러리를 통해 입력 스트림을 변환하고, std::views::transform으로 각 케이스에 대해 문제 해결 함수를 적용하는 식의 파이프라인을 구성할 수 있습니다. 면접관에게 “C++20 Ranges를 사용해 다수의 입력에 동일 로직을 쉽게 적용할 수 있다”고 언급하면 모던 C++ 능력도 보여줄 수 있어요.

7. 예제 문제를 통한 실전 감각 강화

여기서 제안하는 몇 가지 예제를 통해 연습해보세요.

• 투 포인터 예제:
  LeetCode "Two Sum II" 문제: 정렬된 배열과 target 값 주어짐. 투 포인터로 O(N)에 해결.
• 슬라이딩 윈도우 예제:
  LeetCode "Minimum Size Subarray Sum" 문제: 합이 target 이상인 최소 길이 부분 배열 찾기. 슬라이딩 윈도우로 O(N) 해결.
• 문자열 패턴 매칭 예제:
  Baekjoon KMP 문제(“문자열에서 패턴 찾기” 등)나, Programmers에서 “아나그램” 혹은 “부분 문자열 탐색” 문제를 골라 KMP 또는 해시로 최적화.
• 아나그램 처리 예제:
  LeetCode "Valid Anagram" 문제: 두 문자열이 아나그램인지 O(N)에 체크. 빈도 카운트나 정렬 후 비교.

각 문제를 풀 때 시간복잡도, 공간복잡도를 명확히 분석하고, 코너 케이스(빈 문자열, 배열 크기 0, 음수나 큰 수 등)를 생각해보세요. 풀이 후에는 “인터뷰였으면 어떻게 설명했을까?”를 상상하며 의사소통 연습까지 해보시길 권합니다.

8. 면접장에서의 상세 사고 과정 표현

면접 중 문제를 받았다고 가정해봅시다. 예를 들어 “정렬된 배열과 target 주어졌을 때, target 합을 이루는 두 원소를 찾아라”는 문제를 받았다면, 다음과 같은 과정으로 설명할 수 있어요.

1. 접근 아이디어 제안:
   “이 배열이 정렬되어 있기 때문에, O(N^2) 브루트포스 대신 투 포인터로 O(N)에 해결 가능합니다. 왼쪽 포인터 left, 오른쪽 포인터 right를 배열 양 끝에 둔 뒤, 합이 target과 비교하며 포인터를 조정할 거예요.”
2. 구체적 동작 설명:
   “arr[left] + arr[right]가 target보다 작으면 더 큰 합이 필요하므로 left++, target보다 크면 right--로 합을 줄입니다. target과 같으면 정답이죠.”
3. 복잡도 언급:
   “각 원소를 최대 한두 번씩만 검사하므로 O(N) 시간에 해결 가능하며, 추가 메모리는 O(1)입니다.”
4. 코너 케이스:
   “만약 배열 길이가 1 이하라면 두 원소를 만들 수 없으니 즉시 에러 반환하겠습니다(std::expected 사용). 정답이 없을 경우에도 에러를 반환합니다. 빈 배열이나 매우 큰 target 등 다양한 입력에도 잘 대응할 수 있어요.”

이렇게 단순한 문제에서도 사고 과정을 세세히 언어화하면 면접관에게 분석적이고 논리적인 이미지를 줄 수 있습니다.

슬라이딩 윈도우 문제나 문자열 문제에서도 비슷한 방식으로 상세한 사고 프로세스를 verbalize 할 수 있어요. “이 문제는 연속 부분 배열 합 문제이고, K 길이 부분 배열 합을 빠르게 구하기 위해 처음 K개 합을 계산한 뒤, 윈도우를 한 칸씩 옮길 때마다 나가는 원소 빼고 들어오는 원소 더해서 O(N) 시간에 모든 부분 배열 합을 구하겠습니다. K가 N보다 크면 부분 배열을 만들 수 없으니 에러 처리하겠습니다.” 등의 설명을 덧붙이세요.

마무리

여러분, 이번 글에서는 배열과 문자열 문제를 다룰 때 유용한 접근 패턴(투 포인터, 슬라이딩 윈도우, 문자열 패턴 매칭, 아나그램 처리)을 단계별로, 매우 구체적이고 자세하게 살펴보았습니다. 각 패턴을 적용하는 과정에서 어떤 논리적 흐름으로 아이디어를 도출하고, 면접관 앞에서 어떻게 설명하면 좋을지, 코너 케이스와 복잡도 분석, 조건부/비동기/로깅/에러 처리 응용 방안까지 이야기했어요.

이제 여러분은 배열/문자열 문제에서 단순히 정답을 맞히는 게 아니라, 왜 이 접근법을 택했는지, 복잡도는 어떻고, 더 개선할 여지는 없는지, 코너 케이스나 실패 시나리오는 어떻게 처리할지, 어떤식으로 최적화 사고를 면접관에게 전달할지를 더 명확히 구체화할 수 있을 겁니다.

이러한 능력을 갖춘다면 미국 빅테크나 네카라쿠배 기업의 인터뷰에서 배열/문자열 문제가 나온다고 해도 당황하지 않고,

“아, 이 문제는 슬라이딩 윈도우를 적용하면 O(N) 해결 가능하네”

혹은

“KMP를 써서 부분 문자열 검색 O(N+M)에 끝낼 수 있지”

하는 식으로 빠르게 접근법을 결정하고, 면접관에게 체계적인 사고 과정을 보여줄 수 있을 거예요.