최근 CS 기술 면접 대비에 시간을 많이 쓰고 있다.
여러 자료 + 이전 강의에서 본 내용을 보면서 GPT와 모의면접을 하고 있는데, 생각보다 시간이 엄청 쓰인다.
이렇게 시간을 많이 쓰는데 면접이 끝나고, 붙으면 좋겠지만 혹여 떨어지면 지금 준비하는 이 시간이 아무것도 안한 시간이 될까봐.
그리고 분명히 작년 11월 즈음 면접 준비를 하긴 했는데, 기억에서 날라가버렸다..
뭐라도 남겨보자는 심정과 노션에 흩어진 글을 조금이라도 정제해보자는 마음으로 이 포스팅을 시작하였다.
주로 GPT + VSFe 님의 기술면접 질문 모음집을 참고하였다.
질문과 답변 모두 신입 개발자의 입장에서 쓰여진 것이니 오류나 말이 안 맞는 것이 있을 수 있다. 혹은 더 좋은 답변이 있을 수 있다.
이를 발견하여 제게 알려주신다면 커피..라도 한잔 사드리고 싶을 것 같다. 🙇🏻♂️
스택과 큐에 대해서 설명해 주세요.
스택과 큐는 대표적인 선형 자료구조입니다.
먼저, 스택(Stack)은 LIFO(Last In, First Out) 구조로, 가장 나중에 들어간 데이터가 가장 먼저 나오는 구조입니다. 주로 push(데이터 추가), pop(데이터 제거) 연산을 사용합니다. 대표적인 예로는 브라우저의 뒤로 가기 기능이나 재귀 호출의 콜 스택 등이 있습니다.
반면, 큐(Queue)는 FIFO(First In, First Out) 구조로, 먼저 들어온 데이터가 먼저 나갑니다. 일반적으로 enqueue(추가), dequeue(제거) 연산을 사용하며, 이벤트 처리, 작업 스케줄링, 프린터 작업 대기열 등에 적합합니다
스택 2개로 큐를 구현할 수 있을까?
배열 하나로 shift 하지 말고 배열 두개로 큐를 구현합니다.
하나의 배열은 inStack으로 push를 하는 enqueue 스택입니다.
나머지 하나는 outStack으로 pop을 하는 dequeue 스택입니다.
예를 들어, enqueue를 하면, 값을 inStack에 push합니다.
이후 Push는 계속 inStack에 push 하다가, dequeue 명령어가 오면, 두가지 행동으로 나뉩니다.
- 먼저 outStack이 비어있으면, inStack의 모든 요소를 pop하여 outStack에 push합니다.
- outStack이 비어있지 않으면 outStack에서 pop만 하면 됩니다.
dequeue시, outStack을 채워주는 행위는 stack의 순서를 뒤집는 것입니다.
이것이 효율적인 이유는, pop, push 연산은 O(1)이기 때문입니다.
하지만 inStack → outStack으로 가는 작업이 O(n)이지 않냐는 의문이 들 수 있습니다.
여기서 생각해볼 수 있는 개념은 amortized O(1)이라고 부릅니다. 한국어로는 분할상환 분석이라고 합니다.
전체 n개의 input에서, 평균적으로 각 연산은 O(1)입니다.
만약 outStack이 비었을때만 inStack에서 옮겨지는 연산을 수행하지만, 각 원소는 최대 한번만 옮겨지는 행위를 당하게됩니다.
대부분의 연산은 O(1)이지만, 가끔 일어나는 O(n) 때문에 모든 연산이 O(n)이라고 할 수는 없고, 대부분의 O(1)연산에 가끔 한번씩 일어나는 O(n)의 오버헤드를 분할해 O(n)을 줄인다는 개념입니다.
https://gazelle-and-cs.tistory.com/87
스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.
- 스택 2개로 큐 만들기
inStack, outStack 하는거. - 큐 2개로 스택 만들기
먼저 q1, q2를 준비한다.
push(x)를 하면, q1에 enqueue한다.
pop()이면, q1의 요소를 하나 남길때까지 모두 q2로 넘긴다. 그러고 남은 하나를 pop한다.
시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?
먼저 스택을 구현하는 것은, 자바스크립트에서 push, pop 메서드로 쉽게 구현 가능하며, 이는 O(1)입니다.
큐를 구현하는 것은, 배열로 하면 shift로 pop을 구현하니 O(n)연산이라서 비효율적이다.
- 원형 큐를 사용한다. front, rear 포인터를 이용해 O(1)로 구현한다
- 두 배열로 큐를 구현한다. inbox, outbox 구조이며, amortized O(1)로 구현 가능하다
Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산하는 방법에 대해 설명해 주세요.
- Infix : 연산자가 피연산자가 사이에 위치하는 일반적인 수식 형태
3 + 4 → 컴퓨터는 우선순위와 괄호 처리가 필요해 파싱이 복잡 - Prefix : 연산자가 피연산자 앞에 위치
+ 3 4 → 왼쪽에서 오른쪽으로 읽으며 재귀적으로 계산 가능 - Postfix : 연산자가 피연산자 뒤에 위치
3 4 + → 괄호가 없어도 되며, 스택을 사용하면 계산이 효율적이다.
Postfix :
- 수식을 왼쪽에서 오른쪽으로 순회
- 숫자를 만나면 스택에 push
- 연산자를 만나면 스택에서 두 숫자를 pop하고 계산하여, 결과를 다시 push
- 수식이 끝나면 스택에 남은 값이 최종 값
Prefix :
- 수식을 오른쪽에서 왼쪽으로 순회
- 숫자를 만나면 push
- 연산자를 만나면 두개 꺼내서 연산 후 push
- 결과.
Infix :
Postfix로 계산하기 좋게 바꾼다
숫자 스택, 연산자 스택 두개를 사용한다.
- 숫자는 출력한다.
- 연산자는 스택에 넣는다. 연산자를 스택에 넣을 때, 우선순위에 따라 달라진다.
- 아무것도 없으면 스택에 push
- 스택 top의 연산자가 새로 넣을 연산자보다 우선순위가 높거나 같으면 그것들을 pop해 출력하고 그 다음 push한다.
- 스택 top의 연산자가 나보다 낮다면 그냥 스택에 push 한다.
- 남은 연산자를 스택에서 pop
function infixToPostfix(expression) {
const precedence = {
'+': 1,
'-': 1,
'*': 2,
'/': 2
};
const isOperator = (ch) => ['+', '-', '*', '/'].includes(ch);
const output = [];
const stack = [];
const tokens = expression.split(' '); // 공백 기준으로 파싱 (예: '3 + 4 * 2')
for (const token of tokens) {
if (!isNaN(token)) {
// 숫자면 바로 출력
output.push(token);
} else if (isOperator(token)) {
while (
stack.length > 0 &&
isOperator(stack[stack.length - 1]) &&
precedence[stack[stack.length - 1]] >= precedence[token]
) {
output.push(stack.pop()); // 우선순위가 높거나 같으면 pop해서 출력
}
stack.push(token);
} else if (token === '(') {
stack.push(token);
} else if (token === ')') {
while (stack.length > 0 && stack[stack.length - 1] !== '(') {
output.push(stack.pop());
}
stack.pop(); // '(' 제거
}
}
// 남은 연산자 출력
while (stack.length > 0) {
output.push(stack.pop());
}
return output.join(' ');
}
Deque는 어떻게 구현할 수 있을까요?
먼저 Deque는 양쪽 끝에서 삽입, 삭제가 모두 가능해야합니다.
- 배열 기반 구현따라서 원형 큐 방식으로 구현 시, O(1) 연산이 가능합니다.
단순 배열로 구현 시, 앞쪽 삽입, 삭제가 O(n)으로 효율이 떨어집니다.(shift/unshift) - 연결리스트 기반 구현
양방향 연결리스트로 구현 시, O(1)로 구현 가능합니다.
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class Deque {
constructor() {
this.head = null; // 앞쪽
this.tail = null; // 뒤쪽
this.length = 0;
}
pushFront(value) {
const node = new Node(value);
if (!this.head) {
this.head = this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.length++;
}
pushBack(value) {
const node = new Node(value);
if (!this.tail) {
this.head = this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.length++;
}
popFront() {
if (!this.head) return null;
const value = this.head.value;
this.head = this.head.next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null; // 요소 하나였던 경우
}
this.length--;
return value;
}
popBack() {
if (!this.tail) return null;
const value = this.tail.value;
this.tail = this.tail.prev;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null; // 요소 하나였던 경우
}
this.length--;
return value;
}
peekFront() {
return this.head ? this.head.value : null;
}
peekBack() {
return this.tail ? this.tail.value : null;
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
}
Deque을 사용해서 LRU Cache를 구현해주세요.
Deque과 Map을 사용합니다.
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // key → Node
this.deque = new Deque(); // 연결 리스트 기반 덱
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._moveToBack(node);
return node.value[1];
}
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value[1] = value; // update value
this._moveToBack(node);
} else {
if (this.deque.size() === this.capacity) {
const lruNode = this.deque.head;
this.deque.popFront();
this.map.delete(lruNode.value[0]);
}
const newNode = new Node([key, value]);
this.deque.pushBackNode(newNode);
this.map.set(key, newNode);
}
}
_moveToBack(node) {
this.deque.removeNode(node);
this.deque.pushBackNode(node);
}
}
// Deque에 다음 메서드도 추가
pushBackNode(node) {
if (!this.tail) {
this.head = this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.length++;
}
removeNode(node) {
if (node.prev) node.prev.next = node.next;
else this.head = node.next;
if (node.next) node.next.prev = node.prev;
else this.tail = node.prev;
node.prev = node.next = null;
this.length--;
}
Deque을 사용해서 Sliding Window Maximum을 구현해주세요.
크기가 k인 윈도우를 배열에 슬라이딩 시키며, 각 구간의 최대값을 구한다.
브루트포스는 O(nk)지만, Deque은 O(n)에 해결 가능.
덱에는 인덱스만 저장하고 항상 가장 큰 값이 앞에 오도록 유지
윈도우 벗어난 인덱스는 제거하고 새로운 값보다 작은 값들을 제거하고 push
function maxSlidingWindow(nums, k) {
const deque = [];
const result = [];
for (let i = 0; i < nums.length; i++) {
// 앞에서 제거: 윈도우 범위를 벗어난 값
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
// 뒤에서 제거: 현재 값보다 작은 값은 더 이상 최대가 될 수 없음
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
// 첫 k개 이후부터 정답에 추가
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// 결과: [3,3,5,5,6,7]
JavaScript로 스택과 큐를 각각 어떻게 구현할 수 있을까요? 간단한 코드 예시와 함께 설명해 주세요.
- 스택구현
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item); // O(1)
}
pop() {
return this.items.pop(); // O(1)
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 20
- 큐 구현(shift)
class Queue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item); // O(1)
}
dequeue() {
return this.items.shift(); // ❗ O(n) - 앞에서 제거 시 요소 이동 발생
}
front() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
- 효율적인 방법(inbox, outbox)
class EfficientQueue {
constructor() {
this.inbox = []; // 들어오는 애들
this.outbox = []; // 나가는 애들
}
enqueue(value) {
this.inbox.push(value); // O(1)
}
dequeue() {
if (this.outbox.length === 0) {
while (this.inbox.length > 0) {
this.outbox.push(this.inbox.pop());
}
}
return this.outbox.pop(); // O(1) amortized
}
peek() {
if (this.outbox.length === 0) {
while (this.inbox.length > 0) {
this.outbox.push(this.inbox.pop());
}
}
return this.outbox[this.outbox.length - 1];
}
isEmpty() {
return this.inbox.length === 0 && this.outbox.length === 0;
}
size() {
return this.inbox.length + this.outbox.length;
}
}
- 연결리스트
...TODO
브라우저의 실행 환경 중에서 "스택" 구조가 사용되는 예시는 무엇이 있을까요? 실제 동작과 연관지어 설명해 주세요.
브라우저의 콜스택이 있습니다.
자바스크립트 엔진 내부에서 함수 호출을 관리하는 실행 컨텍스트 저장소입니다.
스택 / 큐 구조가 어떻게 병목이나 메모리 문제를 일으킬 수 있나요?
실무에서는 큐의 병목과 메모리 이슈를 막기 위해, 큐 구조를 만드는 것 이상으로, 데이터 흐름을 통제하고, 실패를 관리하고, 사용자 피드백을 제공하는 전략이 필요합니다.
- 큐 길이 증가로 인해 병목이 생긴다면?
예를 들어, 생산 속도가 소비 속도가 빨라 병목이 생길 수 있습니다. 서버, UI, 백엔드 등에서 큐에 작업이 계속 쌓일 수 있겠습니다. 만약 큐가 무한히 커지면 메모리 부족(OOM)이나 응답 지연이 발생할 수 있습니다.
이를 해결해기 위해,- 최대 큐 길이를 설정하고, 큐가 가득 차면 새 요청에 에러를 반환하는 등의 처리를 할 수 있겠습니다.(Drop/Reject 정책) 그렇게 함으로써 시스템 전체가 멈추는 것을 방지하고, 생산자에게 알릴 수 있습니다.
- 우선순위 큐를 사용해, 중요도가 높은 요청부터 우선 처리합니다. UX 악화를 방지할 수 있습니다.
- 멀티스레드/멀티프로세스 환경이라면, 병렬 소비자 수를 조절해 처리량을 늘릴 수 있습니다. Node 에서는 cluster, 백엔드에서는 Kafka consumer group 처럼 병렬 처리를 통한 확장이 가능합니다.
- 단건 처리보다 일정량을 모아 처리하는 배치 방식은 처리 횟수를 줄여 병목을 완화합니다. 또는 쓰로틀이나 디바운스를 통해 입력 빈도를 제한할 수 있습니다. 특히 브라우저 입력이나 실시간 로그 처리에서 자주 사용됩니다.
- 메모리 누수 방지를 위한 전략
큐에 남은 항목들은 GC 대상이 되지 않거나 참조가 남아 메모리를 계속 점유할 수 있습니다.
이를 해결하기 위해, -
- 최대 큐 길이를 제한하고, 오래된 항목이나 실패한 항목을 TTL(Time-To-Live) 기반으로 주기적으로 삭제합니다. 예를 들어 5분 이상 처리되지 않은 항목은 로그를 남기고 제거합니다.
- 클로저나 전역 스코프에서 큐 항목을 계속 참조하면 GC가 되지 않아 메모리 릭이 발생합니다. 처리 완료 시, null로 설정하거나 큐 객체 자체를 delete하거나 splice하여 참조를 명시적으로 제거해야합니다.
- GC 친화적으로 데이터 구조를 설계합니다. 예를 들어 외부 컨텍스트를 담지 않고, 순수한 데이터만 넣도록 데이터를 단순화하여 넣습니다.
- 백프레셔란?
시스템에서 생산자가 너무 많은 데이터를 보내는걸 감지하고, 처리 가능한 양만큼만 받도록 제어하는 흐름 제어 메커니즘 ( paused 플래그를 하나 둠)
예를 들어, 생산자가 데이터를 계속 write → 버퍼가 가득 참 → writable.write()이 false 반환 → 생산자는 drain 이벤트까지 대기 → 소비자 속도에 맞춰 천천히 다시 write → OOM 방지- 지수 백오프 : 실패 시 점점 재시도 간격을 늘린다 (100ms → 200ms → 500ms …)
- 신호 기반 차단 : 생산자에게 더이상 쓰지 말라는 신호 (drain, pause())
- 샘플링 / dropping : 중요도가 낮은 항목은 중간에 버리거나 샘플링만을 처리(로그 수집기)
- UX 개선 전략
- 작업 진행 상태를 시각화하여 보여줍니다. 로딩 UI, 상태 표시줄
- 낙관적 업데이트를 적용하고, 실패 시 롤백 플랜
- 중복요청을 방지하고 디바운스를 겁니다. 혹은 에러 메시지를 구체적으로 보여줍니다.
대규모 트래픽 처리 시, 큐를 어떻게 안정적으로 운영하나요?
- 큐가 막혔을 때 시스템의 장애 대응 전략
- 자동 스케일링 : 소비자 수를 늘려 처리량 증가시킴
- 메시지 TTL
- Alert, 대시보드
- 백프레셔 적용
- Consumer의 병렬성(concurrency), batch 처리 전략은 어떻게 설계하나요?
- "처리량이 필요한 상황에서는 하나의 큐를 다수의 consumer가 병렬로 처리할 수 있도록 설계합니다.
RabbitMQ에서는 prefetch 값을 적절히 조절하여 병렬 처리 중 과부하를 방지합니다."
실시간 큐 시스템을 설계할 때 고려해야 할 요소는?
- 메시지 순서 보장 (Message Ordering)
순서 보장이 필요한 시스템에서는 메시지를 특정 키로 파티셔닝하거나,
FIFO 큐를 선택하고 병렬 consumer 수를 제한하여 순서를 유지했습니다. - 중복 방지 (Idempotency)
네트워크 지연, 재시도 등으로 인해 같은 메시지가 중복 처리될 수 있음
ex) 우리는 메시지에 UUID를 부여하고, 이미 처리된 메시지 ID는 Redis에 short TTL로 저장하여 중복을 방지했습니다. API는 항상 멱등성을 보장했습니다. - QoS (Quality of Service) 레벨 (모름)
- at-least-once : 최소 1번 → 중복 가능성 있음 (안정 우선)
- exactly-once : 정확히 1번 → 구현 복잡 (트랜잭션 + idempotency 필요)
- at-most-once : 최대 1번 → 메시지 손실 가능 (속도 우선) - 소비 속도가 느릴 때의 처리 전략
- 소비자가 느리면 생산자가 전송을 멈추거나 대기
- queue.length > threshold → 생산 차단 or 샘플링
- 처리가 반복 실패하는 메시지는 별도 보관 후 수동 처리
- 중요도 낮은 데이터는 일부만 처리 (예: 실시간 로그)
큐가 계속 쌓이기만 하면? → 메모리 누수
스택 오버플로우는 언제 발생할 수 있나?
큐를 polling 기반으로 처리할 때와 이벤트 기반으로 처리할 때의 성능 차이는?
'CS지식' 카테고리의 다른 글
| [운영체제] 시스템콜 (0) | 2025.04.21 |
|---|---|
| [자료구조] 연결리스트 (0) | 2025.04.20 |
| [알고리즘] 시간복잡도와 공간복잡도 (2) | 2025.04.18 |
| [네트워크] 서버3계층(3-Tier) 면접질문 (4) | 2025.04.17 |
| [네트워크] 쿠키, 세션, 토큰 면접질문 (2) | 2025.04.16 |