[코드 인터뷰 대비 시리즈 #3] 연결 리스트, 스택, 큐 문제 접근 패턴 정리: 노드 조작, 후입선출 구조, FIFO 접근을 극대화하는 방법

여러분, 알고리즘 인터뷰에서 자료구조를 다루는 문제는 매우 빈번합니다. 그중에서도 연결 리스트(Linked List), 스택(Stack), 그리고 큐(Queue)는 가장 기본적이면서도 면접관이 여러분의 기본 자료구조 이해도, 포인터 조작 능력, 추상적 개념을 코드로 구현하는 능력을 평가하기 좋은 주제입니다. 이번 글에서는 이 세 가지 자료구조에 대한 알고리즘 문제 접근 패턴을 하나하나 단계별로 아주 구체적으로 살펴볼게요.

우리는 단순히 "연결 리스트 문제는 포인터 조작" 정도로 끝내지 않고, 실제 문제를 받았을 때 어떤 사고 과정을 거쳐 솔루션을 도출하고, 면접관 앞에서 어떻게 설명하면 좋을지, 각 자료구조별로 어떤 유형의 문제들이 빈출되는지, 코너 케이스나 최적화 포인트는 무엇인지까지 심층적으로 다루겠습니다. 또한 필요하다면 std::expected를 통해 에러 처리, std::format을 통한 로깅, coroutine을 통한 비동기 처리, Ranges를 통한 파이프라인 등 모던 C++20 기능을 어떻게 응용할 수 있는지도 예시로 들어보겠습니다.

1. 연결 리스트(Linked List) 문제 접근하기

연결 리스트는 배열과 다르게 임의 접근(random access)이 불가능하고, 노드 단위로 순회해야 한다는 특징이 있습니다. 이 때문에 인덱스 i번째 원소에 접근하려면 O(i) 시간이 걸리고, 배열 대비 일부 연산(예: 앞에서 삽입)이 O(1)에 가능하나 임의 위치 접근은 비효율적입니다. 면접관은 연결 리스트 문제를 통해 여러분이 포인터나 참조를 조작하는 능력, 노드 삽입/삭제 로직 설계 능력을 본다고 볼 수 있어요.

주요 패턴:

1. 노드 뒤집기(Reverse Linked List):
   고전적인 빈출 문제로, 단일 연결 리스트를 뒤집는 문제를 생각해봅시다. 이 문제에서 여러분은 prev, curr, next 세 포인터를 이용해 리스트를 한 노드씩 돌면서 curr->next = prev로 링크를 반전시키며 리스트를 뒤집는 접근을 할 수 있습니다.
   단계별 사고 과정:
   
   • 문제: 단일 연결 리스트를 뒤집어라.
   • 아이디어: 한 번 순회(O(N))로 리스트 뒤집기 가능.
   • 구현 시 prev=nullptr, curr=head로 시작, next=curr->next 저장 후 curr->next=prev, prev=curr, curr=next 로 한 스텝씩 이동.
   • 코너 케이스: 빈 리스트나 노드가 한 개뿐인 경우. 이런 경우 그대로 반환하면 됩니다.
   • 면접장에서 설명: "이 문제는 O(N) 시간, O(1) 공간으로 해결 가능합니다. 포인터를 세 개 써서 링크 방향을 반대로 바꿉니다. 각 노드를 한 번만 처리하므로 효율적입니다."
   LeetCode "Reverse Linked List" 문제로 연습해보세요.
2. 중간 노드(Middle Node) 찾기:
   연결 리스트 중간 노드를 찾는 문제는 “빠른/느린 포인터(Fast/Slow pointer)” 기법을 자주 사용합니다. slow 포인터는 한 칸씩, fast 포인터는 두 칸씩 이동하면서 fast가 리스트 끝에 도달할 때 slow가 중간 노드를 가리키도록 합니다.
   단계별 사고 과정:
   
   • 문제: 단일 연결 리스트의 중간 노드를 찾아라.
   • 아이디어: slow= head, fast = head 로 시작. fast와 fast->next가 null에 도달할 때까지 slow는 한 칸씩, fast는 두 칸씩 이동.
   • fast가 끝에 도달하면 slow는 중간을 가리킴. O(N) 시간, O(1) 공간.
   • 코너 케이스: 빈 리스트나 노드 한 개인 경우 그냥 head 반환.
   • 면접장에서 설명: "빠르고 느린 포인터를 이용하면 중간 노드를 추가 메모리 없이 한번 순회로 찾을 수 있습니다."
   LeetCode "Middle of the Linked List" 문제로 연습 가능.
3. 사이클(Cycle) 검출:
   리스트에 사이클이 있는지 판별하는 문제에서도 fast/slow 포인터 기법이 쓰입니다. fast와 slow가 언젠가 만난다면 사이클 존재, fast가 null에 도달하면 사이클 없음.
   코너 케이스는 없거나 단일 노드 상황에서도 자연스럽게 처리가능. 이 기법은 Programmers나 Baekjoon에서도 응용 가능.

추가 팁:
면접관에게 연결 리스트 문제를 설명할 때는 포인터 조작 과정(어떤 순서로 next를 저장하고 포인터를 이동하는지)을 구체적으로 말하며, 코너 케이스 처리(빈 리스트, 한 개 노드 리스트, 타겟 노드가 없는 경우 등)에 주의를 기울이겠다고 어필하면 좋습니다.

2. 스택(Stack) 문제 접근: 후입선출(LIFO) 구조 응용

스택은 LIFO(Last-In, First-Out) 구조를 가지며, 괄호 검사, 뒤집기, 모노토닉 스택 활용 문제 등에서 자주 등장합니다.

대표적 패턴: 괄호 검사(Balanced Parentheses) 문제

1. 문제 상황:
   문자열에 괄호들이 주어졌을 때, 괄호가 올바르게 짝지어졌는지 판단하는 문제. 예: "({[]})"는 올바르지만 "([)]"는 올바르지 않다.
2. 단계별 사고 과정:
   • 빈 스택 준비.
   • 문자열을 왼쪽부터 순회하며 여는 괄호('(', '{', '[')면 스택에 푸시.
   • 닫는 괄호(')', '}', ']')를 만나면 스택에서 top을 팝하고, 해당 괄호와 짝이 맞는지 확인. 짝이 안 맞거나 스택이 비어있으면 잘못된 괄호 구조.
   • 마지막까지 끝냈을 때 스택이 비어있으면 올바른 괄호 구조.
   이 로직은 O(N)에 처리 가능하고, 구현도 straightforward합니다. 면접에서 "스택을 통해 O(N)에 올바른 괄호 구조를 판별합니다. push/pop으로 괄호 짝을 맞추고, 코너 케이스로 빈 문자열이나 닫는 괄호가 먼저 나오는 경우를 에러 처리할 수 있습니다."라고 설명할 수 있습니다.
   LeetCode "Valid Parentheses" 문제로 연습하세요.

모노토닉 스택(Monotonic Stack) 활용:

모노토닉 스택은 스택을 통해 각 원소에 대해 다음 큰 원소(next greater element)를 O(N)에 찾는 등, 다양한 최적화 문제를 해결하는데 유용합니다.

• 예: 정수 배열에서 각 원소의 '다음으로 큰 원소'를 찾는 문제. stack에 인덱스를 저장하며, 새로운 원소가 들어올 때 stack top을 확인해 현재 원소가 더 크면 pop하면서 해당 인덱스의 다음 큰 원소를 현재 값으로 설정.
• 이로써 O(N)에 모든 원소의 다음 큰 원소를 찾을 수 있어요. 면접장에서 O(N log N) 정렬 후 탐색 대신 O(N) 모노토닉 스택 풀이를 제안하면 최적화 능력을 어필할 수 있습니다.

LeetCode "Next Greater Element" 류 문제로 연습해보세요.

3. 큐(Queue) 문제 접근: FIFO 구조와 BFS 응용

큐는 선입선출(FIFO) 구조를 갖고, BFS(Breadth-First Search)와 함께 그래프/트리 문제에서 자주 등장합니다. 여기서는 배열/문자열보다는 BFS에 더 많이 얽히지만, 문자열 변환 문제나, 슬라이딩 윈도우 최대값 문제를 deque(이중 덱)을 이용해 O(N)에 처리하는 등 큐 특유의 특성을 활용할 수도 있습니다.

예제: 슬라이딩 윈도우 최대값을 deque로 O(N)에 해결

1. 아이디어:
   • 단순 O(N*K) 또는 O(N log K) 풀이 대신 deque를 이용해 O(N)에 각 윈도우에서 최대값 찾기.
   • deque에 윈도우 내 유용한 후보 인덱스만 유지하며, 새 값 삽입 시 뒤에서부터 현재 값보다 작은 값들 pop해 단조 감소(decreasing) 형태 유지.
   • 윈도우 범위를 벗어난 인덱스는 front에서 pop.
2. 면접 설명 방식:
   • “deque를 사용해 슬라이딩 윈도우 최대값을 O(N)에 찾을 수 있습니다. 새 원소를 삽입할 때 덱 뒤에서부터 작거나 같은 원소 인덱스를 pop하므로 덱은 항상 단조 감소 순서를 유지합니다. 덕분에 덱 front는 항상 최대값 인덱스를 가리킵니다.”
   • 코너 케이스: 빈 배열, K > N이면 에러 처리.
   • LeetCode "Sliding Window Maximum" 문제로 연습 가능합니다.

큐는 BFS 응용에서도 중요합니다. 예를 들어 문자 배열로 주어진 미로에서 최단 경로를 찾거나, 그래프의 레벨 순회 시 큐를 활용해 각 레벨을 순서대로 처리할 수 있습니다. 면접에서 큐를 mention하며 BFS를 통해 O(V+E) 시간에 최단 경로 또는 레벨별 정보를 얻을 수 있음을 강조하세요.

4. 조건부 처리, 비동기 처리, 로깅, 에러 처리, Ranges 응용

앞서 다른 자료구조(배열/문자열)에서 언급했던 것처럼, 연결 리스트, 스택, 큐 문제에서도 조건부 로직이나 에러 처리, 비동기 처리, 로깅 등을 덧붙일 수 있습니다.

• 조건부 처리:
  예를 들어 연결 리스트 뒤집기 문제에서 리스트가 특정 조건(예: 너무 길거나 특정 값이 없음)을 만족하지 않으면 std::expected로 에러를 반환할 수 있습니다. 면접 중 "여기서 입력 검증을 하고, 조건 불만족 시 에러를 명확히 반환하겠습니다"라고 언급하면 꼼꼼한 인상을 줍니다.
• 비동기 처리 (Coroutine):
  예를 들어 매우 큰 연결 리스트나 외부 API로부터 스트리밍되는 노드를 비동기적으로 처리해야 한다면 coroutine으로 리스트 처리를 비동기 I/O와 결합할 수 있습니다. 면접에서 이런 가능성을 언급하면 고급스럽게 보일 수 있습니다.
• 로깅(std::format):
  스택/큐 연산 과정에서 push/pop 할 때마다 현재 상태를 로깅한다고 해보세요. 디버깅이나 검사에 유용한 기능을 제안하며, “성능 문제 시 로깅을 조건부로 비활성화하는 전략도 있다”라고 설명할 수 있습니다.
• Ranges 활용:
  예를 들어, 여러 테스트 케이스에 대해 연결 리스트 뒤집기나 스택 연산 시뮬레이션을 일괄 수행하려면 Ranges로 파이프라인을 구성해 인풋 스트림에 대해 transform을 적용하는 식으로 깔끔히 처리할 수 있습니다. 이는 면접에서 굳이 구현하지 않아도 "C++20 Ranges를 통해 다수의 입력 케이스에 동일 로직을 모듈화해 적용 가능"이라고 언급하면 모던 C++ 숙련도를 강조할 수 있습니다.

5. 예제 문제로 실전 감각 키우기

• 연결 리스트 뒤집기 예제:
  LeetCode "Reverse Linked List" 문제. 포인터 조작 연습 및 O(N), O(1) 솔루션 구현, 코너 케이스(빈 리스트, 1개 노드 리스트) 처리. 구체적으로 면접에서 포인터 세 개(prev, curr, next) 운용 과정을 말해보세요.
• 스택 괄호 검사 예제:
  LeetCode "Valid Parentheses" 문제. 스택으로 여는 괄호 push, 닫는 괄호 만나면 pop해 매칭 여부 검사. 조건 불만족 시 즉시 에러(잘못된 괄호 구조) 반환. 로깅을 통해 push/pop 과정을 콘솔에 출력할 수도 있습니다.
• 큐 BFS 예제:
  그래프 최단 경로 문제나 트리 레벨 순회 문제에서 큐 사용. 예를 들어 Baekjoon에서 BFS를 통한 최소 이동 횟수 문제나, Programmers에서 BFS 문제를 찾아 연습해보세요. 면접에서 "큐를 통한 BFS로 O(V+E) 시간에 최단 경로나 레벨 정보를 얻을 수 있고, 코너 케이스(비어있는 그래프, 단일 노드)도 자연스럽게 처리할 수 있습니다"라고 언급해보세요.

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

실제 면접 상황을 가정해봅시다. 면접관이 “이 단일 연결 리스트에서 중간 노드를 찾아주세요”라고 말하면, 여러분은 다음과 같이 사고 과정을 설명할 수 있습니다.

1. "연결 리스트는 임의 접근이 불가능하므로 한 번 순회해서 길이를 구한 뒤 두 번째 순회로 중간 노드를 찾는 O(N) 방법이 있습니다."
2. "하지만 더 효율적인 방법으로, fast/slow 포인터를 쓸 수 있어요. slow는 한 칸씩, fast는 두 칸씩 이동하면, fast가 리스트 끝에 도달할 때 slow는 중간 노드를 가리킵니다. 단 한 번의 순회로 중간 노드를 찾는 O(N), O(1) 솔루션이 가능하죠."
3. "코너 케이스: 빈 리스트면 그냥 nullptr 반환, 노드가 하나면 그 노드가 중간이므로 그대로 반환합니다. 이 방식은 추가 메모리 없이도 중간 노드를 효율적으로 찾을 수 있어 깔끔합니다."

이런 식으로 단계별로 논리를 전개하고, 최적화 포인트, 코너 케이스, 메모리 사용량까지 언급하면 면접관이 여러분의 사고 능력을 높게 평가할 것입니다.

마무리: 배열/문자열 문제에서 한 단계 발전한 자료구조 접근

이번 글에서는 연결 리스트, 스택, 큐 문제를 다룰 때 자주 등장하는 패턴들을 매우 상세한 단계로 나누어 설명했습니다. 연결 리스트 포인터 조작, fast/slow 포인터를 통한 중간 노드나 사이클 검출, 스택을 통한 괄호 검사나 모노토닉 스택을 통한 O(N) 최적화, 큐를 통한 BFS나 덱(deque)을 이용한 슬라이딩 윈도우 최대값 계산까지, 각 자료구조별 대표 패턴을 익혔습니다.

이러한 패턴을 숙지하면 새로운 문제를 만났을 때도 “이 문제는 스택으로 괄호검사 가능하네”, “여기서 모노토닉 스택으로 다음 큰 원소 찾기 가능하군”, “연결 리스트 이슈는 fast/slow 포인터 써서 해결할 수 있지” 같은 식으로 빠르게 접근할 수 있어요. 그리고 면접관에게 이 로직을 설명할 때 단계별로 사고 과정을 명확히 verbalize하면 훨씬 좋은 인상을 남길 수 있습니다.

이 글을 통해 여러분이 연결 리스트, 스택, 큐 문제에 대한 자신감을 갖게 되었길 바랍니다. 앞으로 더 다양한 문제 유형에 대해서도 이와 유사한 패턴 식별 과정을 적용해보세요. 그렇게 하면 어떠한 문제 유형이 나오더라도 당황하지 않고 논리적으로 접근하는 습관을 기를 수 있을 것입니다.