면접카타 [Data structure] -14,15

1. Array와 LinkedList 비교

Array (배열)

• 정의: 동일한 자료형의 원소들이 연속된 메모리 공간에 저장되는 자료구조
• 특징:
  • 고정된 크기: 선언할 때 크기가 정해지며, 크기를 변경하기 어렵다.
  • 빠른 접근 (O(1)): 인덱스를 이용하여 임의 접근이 가능하다.
  • 삽입/삭제가 느림 (O(n)): 중간에 삽입/삭제 시, 이후 원소들을 이동해야 한다.
  • 메모리 효율적: 포인터를 저장할 필요가 없으므로 메모리를 덜 사용한다.

Array 예제 (배열 사용)

// 배열 선언 및 초기화
let arr = [10, 20, 30, 40, 50];

// 배열 요소 접근 (O(1))
console.log(arr[2]); // 30

// 배열 중간에 요소 삽입 (O(n))
arr.splice(2, 0, 25);
console.log(arr); // [10, 20, 25, 30, 40, 50]

// 배열 요소 삭제 (O(n))
arr.splice(3, 1);
console.log(arr); // [10, 20, 25, 40, 50]

// 배열의 끝에서 요소 추가/삭제 (O(1))
arr.push(60);
console.log(arr); // [10, 20, 25, 40, 50, 60]

arr.pop();
console.log(arr); // [10, 20, 25, 40, 50]

• 특징: 배열은 빠른 접근이 가능하지만 중간 삽입/삭제 시 비용이 크다.

LinkedList (연결 리스트)

• 정의: 각 원소(Node)가 데이터와 다음 노드를 가리키는 포인터를 포함하는 자료구조
• 특징:
  • 동적 크기 조정 가능: 필요할 때마다 메모리를 할당할 수 있다.
  • 순차 접근 (O(n)): 인덱스를 통한 직접 접근이 불가능하며, 처음부터 탐색해야 한다.
  • 빠른 삽입/삭제 (O(1) ~ O(n)): 특정 위치에서의 삽입/삭제는 O(n)이지만, 앞/뒤에서 수행할 경우 O(1)이다.
  • 메모리 낭비: 각 노드마다 포인터를 저장해야 하므로 추가적인 메모리를 사용한다.

LinkedList 예제 (연결 리스트 구현)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // 연결 리스트 끝에 요소 추가 (O(1))
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  // 연결 리스트의 첫 번째 요소 삭제 (O(1))
  removeFirst() {
    if (!this.head) return;
    this.head = this.head.next;
  }

  // 전체 리스트 출력
  print() {
    let current = this.head;
    let result = [];
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    console.log(result.join(" -> "));
  }
}

let list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.print(); // 10 -> 20 -> 30

list.removeFirst();
list.print(); // 20 -> 30

• 특징: 동적 크기 조정이 가능하며 삽입/삭제가 빠르지만, 직접 접근이 느리다.

Array vs LinkedList 비교 

비교 항목	Array (배열)	LinkedList (연결 리스트)
메모리 할당	고정 크기	동적 크기
접근 속도	O(1) (인덱스 접근)	O(n) (순차 탐색)
삽입/삭제	O(n) (중간에서 수행)	O(1) (앞/뒤에서 수행)
메모리 사용	추가 메모리 없음	포인터로 인해 메모리 사용 증가

 

 

---

꼬리질문

Q1. Array와 LinkedList의 메모리 사용 방식 차이는 무엇인가요?

A1.

• Array (배열)
  • 연속된 메모리 공간을 차지함.
  • 따라서 인덱스 기반으로 빠른 랜덤 접근(O(1))이 가능.
  • 하지만 크기를 미리 지정해야 하거나 동적 배열을 사용할 경우 크기 변경 시 새로운 메모리 할당이 필요하여 O(n) 복사 비용이 발생함.
• LinkedList (연결 리스트)
  • 노드 단위로 메모리에 분산 저장되며, 각각의 노드는 다음 노드를 가리키는 포인터(주소)를 포함.
  • 따라서 중간 삽입/삭제가 O(1)로 효율적이나, 포인터(추가적인 메모리 사용)로 인해 오버헤드가 발생.
  • 또한, 캐시 효율(Cache locality)이 낮아 배열보다 탐색 성능이 떨어짐.

---

Q2. Array의 크기를 동적으로 조절하는 방법과 성능 문제는 무엇인가요?

A2.

• 일반적인 배열은 고정된 크기를 가지므로, 동적 크기 조정이 필요할 경우 동적 배열 (Dynamic Array, Python의 list) 를 사용함.
• 동적 배열은 내부적으로 배열 크기가 가득 차면 기존 크기의 2배로 확장하는 방식으로 동작.
• 기존 데이터를 새로운 메모리 영역으로 복사하는 과정에서 O(n) 시간 복잡도가 발생할 수 있음.

JS 예시 코드

// 동적으로 크기가 조정되는 배열 예제
let arr = []; // 빈 배열 선언

// 배열에 요소 추가
arr.push(1);
arr.push(2);
arr.push(3);

console.log(arr); // [1, 2, 3]

// 배열 크기 동적 조절
arr.length = 5;
console.log(arr); // [1, 2, 3, empty × 2]

// 배열 축소 (불필요한 요소 제거)
arr.length = 2;
console.log(arr); // [1, 2]

추가적인 성능 문제

• 메모리 재할당 비용: 배열이 가득 차면 새로운 크기의 배열을 할당하고 기존 데이터를 복사하는 과정에서 성능 저하 발생 가능.
• 캐시 비효율성: 크기 조정 과정에서 연속적인 메모리 블록이 보장되지 않을 수도 있어, 캐시 효율이 떨어질 수 있음.
• GC(가비지 컬렉션) 영향: 배열 크기가 줄어들거나 늘어날 때 불필요한 메모리가 할당/해제되면서 GC가 자주 발생할 가능성이 있음.

 

 

---

Q3. Array와 LinkedList 중 검색(search) 성능이 더 좋은 것은 무엇인가요?

A3.
배열(Array)이 검색에 더 유리함.

• 배열은 연속된 메모리에 저장되므로 인덱스를 통해 O(1) 시간에 특정 요소를 조회 가능.
• 연결 리스트는 처음부터 순차적으로 노드를 탐색해야 하므로 최악의 경우 O(n) 의 시간이 걸림.

 

---

Q4. Array와 LinkedList에서 삽입/삭제 연산 속도 차이는?

A4.
삽입/삭제 연산의 속도는 연산이 수행되는 위치에 따라 다름.

연산 유형	배열 (Array)	연결 리스트 (LinkedList)
끝에 추가	O(1) (동적 배열 재할당 시 O(n))	O(n) (끝까지 탐색 필요)
중간에 삽입	O(n) (이동 필요)	O(1) (포인터 변경)
중간에서 삭제	O(n) (이동 필요)	O(1) (포인터 변경)

• 배열(Array)
  • 마지막 위치에 추가하면 O(1), 하지만 중간에 삽입/삭제할 경우 요소를 이동해야 하므로 O(n) 성능 저하 발생.
• 연결 리스트(LinkedList)
  • 중간에 삽입/삭제 시 포인터 변경만 하면 되므로 O(1), 하지만 특정 위치를 찾기 위한 탐색이 필요하여 최악의 경우 O(n).

 

---

Q5. Array와 LinkedList의 실제 사용 사례는?

A5.

• Array를 사용하는 경우
  • 인덱스 기반 빠른 조회(O(1)) 가 필요한 경우
  • 데이터 크기가 고정적이며, 자주 변경되지 않는 경우
  • CPU 캐시 친화적인 고속 연산이 필요한 경우
  예제:
  • 게임 개발에서 타일 맵 저장 (2D 배열)
  • 배열 기반 스택/큐 구현
  • 해시 테이블에서 버킷 저장
• LinkedList를 사용하는 경우
  • 빈번한 삽입/삭제가 발생하는 경우
  • 데이터 크기가 가변적이고 초기에 크기를 예측하기 어려운 경우
  • 연속된 메모리를 확보하기 어려운 경우
  예제:
  • LRU Cache (이중 연결 리스트 활용)
  • Undo/Redo 기능 (이전 상태 저장)
  • OS의 메모리 할당 (Free List 구조 활용)

---

 Array vs LinkedList 선택 기준

선택 기준	Array (배열)	LinkedList (연결 리스트)
빠른 인덱스 접근	✅ O(1)	❌ O(n)
빈번한 삽입/삭제	❌ O(n)	✅ O(1)
메모리 사용 효율	✅ 연속된 공간 사용	❌ 포인터로 인한 추가 메모리 사용
CPU 캐시 효율	✅ 높음	❌ 낮음
동적 크기 조정	❌ 새 배열 할당 필요	✅ 자유롭게 크기 조정 가능

---

 

---

2. Stack과 Queue 비교

Stack (스택)

• 정의: LIFO(Last In, First Out) 원칙을 따르는 자료구조
• 주요 연산:
  • push(): 요소를 스택의 맨 위에 추가
  • pop(): 요소를 스택의 맨 위에서 제거
  • peek() (top()): 맨 위의 요소를 조회 (제거하지 않음)
• 특징:
  • 마지막에 추가된 요소가 먼저 제거됨 (후입선출, LIFO)
  • 재귀(Recursion) 호출을 처리하는 데 사용됨
  • 예시: 함수 호출 스택, 웹 브라우저 뒤로 가기

Stack 예제 (배열을 이용한 스택 구현)

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  print() {
    console.log(this.items.join(" -> "));
  }
}

let stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // 10 -> 20 -> 30

console.log(stack.pop()); // 30
stack.print(); // 10 -> 20

• 특징: 후입선출(LIFO) 구조로 함수 호출 스택과 같은 문제 해결에 사용됨.

Queue (큐)

• 정의: FIFO(First In, First Out) 원칙을 따르는 자료구조
• 주요 연산:
  • enqueue(): 요소를 큐의 뒤쪽(Rear)에 추가
  • dequeue(): 요소를 큐의 앞쪽(Front)에서 제거
  • peek() (front()): 맨 앞 요소를 조회 (제거하지 않음)
• 특징:
  • 먼저 추가된 요소가 먼저 제거됨 (선입선출, FIFO)
  • 프로세스 스케줄링, 네트워크 패킷 처리 등에 사용됨
  • 예시: 프린터 작업 대기열, BFS(너비 우선 탐색)

 

Stack vs Queue 비교 표

비교 항목	Stack (스택)	Queue (큐)
원칙	LIFO (후입선출)	FIFO (선입선출)
삽입 연산	push() (맨 위에 추가)	enqueue() (뒤쪽에 추가)
삭제 연산	pop() (맨 위에서 제거)	dequeue() (앞쪽에서 제거)
사용 예시	함수 호출 스택, 뒤로 가기 기능	프로세스 스케줄링, BFS 탐색

---

꼬리 질문 및 답변

Q1. Array와 LinkedList 중에서 데이터가 빈번하게 추가/삭제되는 경우, 어떤 것을 사용하는 것이 더 좋나요?

A1. 데이터 추가/삭제가 빈번한 경우 LinkedList가 더 적합합니다.

• Array에서는 중간에 요소를 삽입/삭제할 경우, 다른 요소들을 이동해야 하므로 O(n)의 시간이 걸립니다.
• LinkedList는 포인터만 변경하면 되므로 O(1)~O(n) 시간이 소요됩니다.
• 단, LinkedList는 포인터를 저장하는 추가적인 메모리 오버헤드가 있으므로, 삽입/삭제가 정말 자주 발생하는 경우에만 유리합니다.

---

 

Q2. Array와 LinkedList의 장점을 모두 활용한 자료구조가 있을까요?

A2. "동적 배열 (Dynamic Array)" 또는 "이중 연결 리스트 (Doubly Linked List)"

• Dynamic Array: 필요할 때 크기를 증가시키는 배열 (JavaScript의 Array가 해당)
• Doubly Linked List: 각 노드가 이전과 다음을 가리키는 포인터를 가짐 → 양방향 탐색 가능

---

Q1. Stack이 메모리 관리에서 활용되는 예시는 무엇인가요?

A1. Stack은 함수 호출 스택에 사용됨.

• 재귀 함수가 실행될 때 각 호출은 스택 프레임에 저장됨.
• 반환되면 스택에서 제거됨.
• 예제

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(5)); // 120

• 함수가 호출될 때마다 스택에 쌓이고, 반환될 때 스택에서 제거됨.

---

Q3. Queue를 활용한 네트워크 관련 문제를 설명해 주세요.

A3. "네트워크 패킷 처리"

• 네트워크에서 패킷(Packets) 은 FIFO 방식으로 처리됨.
• 패킷이 큐에 들어와서 먼저 들어온 것이 먼저 처리됨.

예제 (비동기 요청 처리)

class RequestQueue {
  constructor() {
    this.queue = [];
  }

  addRequest(request) {
    this.queue.push(request);
  }

  processRequest() {
    if (this.queue.length === 0) return;
    let request = this.queue.shift();
    console.log(`Processing: ${request}`);
  }
}

let networkQueue = new RequestQueue();
networkQueue.addRequest("Packet 1");
networkQueue.addRequest("Packet 2");

networkQueue.processRequest(); // Packet 1
networkQueue.processRequest(); // Packet 2

• 설명: 먼저 요청된 네트워크 패킷이 먼저 처리됨.

---

Q2. Array와 LinkedList의 장점을 모두 활용한 자료구조가 있을까요?

A2. "동적 배열 (Dynamic Array)" 또는 "이중 연결 리스트 (Doubly Linked List)"

• Dynamic Array: 필요할 때 크기를 증가시키는 배열 (JavaScript의 Array가 해당)
• Doubly Linked List: 각 노드가 이전과 다음을 가리키는 포인터를 가짐 → 양방향 탐색 가능

---

Q3. Stack이 메모리 관리에서 활용되는 예시는 무엇인가요?

A3. Stack은 함수 호출 스택에 사용됨.

• 재귀 함수가 실행될 때 각 호출은 스택 프레임에 저장됨.
• 반환되면 스택에서 제거됨.
• 예제

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(5)); // 120

• 함수가 호출될 때마다 스택에 쌓이고, 반환될 때 스택에서 제거됨.

---

Q4. Stack을 이용해 Queue를 구현할 수 있을까요? (또는 반대로 Queue로 Stack을 구현할 수 있을까요?)

A4. 네, 가능합니다.

• Stack을 이용한 Queue 구현 (Two-Stack Queue)
  • Stack 두 개 (stack1, stack2)를 사용하여 Queue의 enqueue 및 dequeue 연산을 구현할 수 있습니다.
  • enqueue(): stack1에 push
  • dequeue():
    1. stack2가 비어있으면, stack1의 모든 요소를 stack2로 이동
    2. stack2에서 pop
  • 시간 복잡도: O(1)~O(n)
• Queue를 이용한 Stack 구현 (Two-Queue Stack)
  • Queue 두 개 (queue1, queue2)를 사용하여 Stack의 push 및 pop 연산을 구현할 수 있습니다.
  • push(): queue1에 enqueue
  • pop(): queue1의 요소를 하나 남을 때까지 queue2로 이동 후 pop
  • 시간 복잡도: O(1)~O(n)

---

Q5. Stack과 Queue를 활용한 알고리즘 문제 예시를 알려주세요.

A5.

• Stack 활용 문제:
  • 괄호 검사 (Valid Parentheses): ({[]}) 같은 괄호가 올바르게 닫혔는지 확인 (LIFO 구조 활용)
  • 탑 문제 (Top View of Tower): 앞쪽에서 보이는 탑의 개수 구하기
  • 최대 직사각형 면적 (Largest Rectangle in Histogram)
• Queue 활용 문제:
  • 너비 우선 탐색 (BFS): 최단 경로 탐색 문제에서 사용
  • 캐시 문제 (LRU Cache 구현): 큐를 활용한 캐시 시스템
  • 미로 탈출: 최소 이동 횟수 계산 (BFS 활용)

1) Stack 활용 - 올바른 괄호 검사

function isValidParentheses(s) {
  let stack = [];
  let map = { ')': '(', '}': '{', ']': '[' };

  for (let char of s) {
    if (char in map) {
      if (stack.pop() !== map[char]) return false;
    } else {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({[})"));  // false

• 설명: 여는 괄호는 스택에 넣고, 닫는 괄호가 나오면 스택에서 꺼내어 짝이 맞는지 확인.

---

2) Queue 활용 - BFS를 이용한 최단 거리 탐색

function bfs(graph, start) {
  let queue = [start];
  let visited = new Set();
  visited.add(start);

  while (queue.length > 0) {
    let node = queue.shift();
    console.log(node);

    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
}

let graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

bfs(graph, 'A');

• 설명: BFS는 Queue를 활용하여 그래프 탐색을 수행하며, 최단 거리 문제에 사용됨.

---

Q6. Queue를 활용한 네트워크 관련 문제를 설명해 주세요.

A6. "네트워크 패킷 처리"

• 네트워크에서 패킷(Packets) 은 FIFO 방식으로 처리됨.
• 패킷이 큐에 들어와서 먼저 들어온 것이 먼저 처리됨.

예제 (비동기 요청 처리)

class RequestQueue {
  constructor() {
    this.queue = [];
  }

  addRequest(request) {
    this.queue.push(request);
  }

  processRequest() {
    if (this.queue.length === 0) return;
    let request = this.queue.shift();
    console.log(`Processing: ${request}`);
  }
}

let networkQueue = new RequestQueue();
networkQueue.addRequest("Packet 1");
networkQueue.addRequest("Packet 2");

networkQueue.processRequest(); // Packet 1
networkQueue.processRequest(); // Packet 2

• 설명: 먼저 요청된 네트워크 패킷이 먼저 처리됨.

---

Q2. Array의 크기를 동적으로 조절하는 방법과 성능 문제는 무엇인가요?  

1. Array와 LinkedList의 JavaScript 예제 코드

Array 예제 (배열 사용)

// 배열 선언 및 초기화
let arr = [10, 20, 30, 40, 50];

// 배열 요소 접근 (O(1))
console.log(arr[2]); // 30

// 배열 중간에 요소 삽입 (O(n))
arr.splice(2, 0, 25);
console.log(arr); // [10, 20, 25, 30, 40, 50]

// 배열 요소 삭제 (O(n))
arr.splice(3, 1);
console.log(arr); // [10, 20, 25, 40, 50]

// 배열의 끝에서 요소 추가/삭제 (O(1))
arr.push(60);
console.log(arr); // [10, 20, 25, 40, 50, 60]

arr.pop();
console.log(arr); // [10, 20, 25, 40, 50]

• 특징: 배열은 빠른 접근이 가능하지만 중간 삽입/삭제 시 비용이 크다.

---

LinkedList 예제 (연결 리스트 구현)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // 연결 리스트 끝에 요소 추가 (O(1))
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  // 연결 리스트의 첫 번째 요소 삭제 (O(1))
  removeFirst() {
    if (!this.head) return;
    this.head = this.head.next;
  }

  // 전체 리스트 출력
  print() {
    let current = this.head;
    let result = [];
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    console.log(result.join(" -> "));
  }
}

let list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.print(); // 10 -> 20 -> 30

list.removeFirst();
list.print(); // 20 -> 30

• 특징: 동적 크기 조정이 가능하며 삽입/삭제가 빠르지만, 직접 접근이 느리다.

---

2. Stack과 Queue의 JavaScript 예제 코드

Stack 예제 (배열을 이용한 스택 구현)

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  print() {
    console.log(this.items.join(" -> "));
  }
}

let stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // 10 -> 20 -> 30

console.log(stack.pop()); // 30
stack.print(); // 10 -> 20

• 특징: 후입선출(LIFO) 구조로 함수 호출 스택과 같은 문제 해결에 사용됨.

---

Queue 예제 (배열을 이용한 큐 구현)

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  print() {
    console.log(this.items.join(" -> "));
  }
}

let queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.print(); // 10 -> 20 -> 30

console.log(queue.dequeue()); // 10
queue.print(); // 20 -> 30

• 특징: 선입선출(FIFO) 구조로 BFS 탐색이나 프로세스 스케줄링에 적합.

---

3. Stack과 Queue를 활용한 응용 문제

1) Stack 활용 - 올바른 괄호 검사

function isValidParentheses(s) {
  let stack = [];
  let map = { ')': '(', '}': '{', ']': '[' };

  for (let char of s) {
    if (char in map) {
      if (stack.pop() !== map[char]) return false;
    } else {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({[})"));  // false

• 설명: 여는 괄호는 스택에 넣고, 닫는 괄호가 나오면 스택에서 꺼내어 짝이 맞는지 확인.

---

2) Queue 활용 - BFS를 이용한 최단 거리 탐색

function bfs(graph, start) {
  let queue = [start];
  let visited = new Set();
  visited.add(start);

  while (queue.length > 0) {
    let node = queue.shift();
    console.log(node);

    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
}

let graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

bfs(graph, 'A');

• 설명: BFS는 Queue를 활용하여 그래프 탐색을 수행하며, 최단 거리 문제에 사용됨.

 

---