[CS] 신입 개발자 기술면접 질문 - 자료구조 편

작업 중인 포트폴리오입니다... 쿄쿄...

 

기술면접 질문 "자료구조 편" 시작합니다 :)

 

! 시간 복잡도는 알고리즘에서 더 자세히 다루겠습니다. (ㅎㅎ)

0. 시간 복잡도가 무엇인가요?

시간 복잡도는 입력한 데이터의 크기에 따라 실행 시간이 어떻게 증가하는지를 설명하는 개념입니다.

 

*빅오 표기법

O(1)	상수 시간 복잡도	입력 크기 무관하게 일정한 실행 시간
O(log n)	로그 시간 복잡도	입력 크기에 따라 로그 정도로 증가하는 실행 시간
O(n)	선형 시간 복잡도	입력 크기에 비례하여 증가하는 실행 시간
O(n^2)	제곱 시간 복잡도	입력 크기에 제곱에 비례하여 증가하는 실행 시간

 

 

1. 선형 자료구조에 대해 아는 대로 설명해 주세요.

선형 자료구조란 데이터를 일렬로 나열한 구조로,
주로 배열과 연결 리스트가 대표적인 선형 자료구조로 사용됩니다.

 

1-1. Array(배열)과 Linked List(연결 리스트)를 비교하여 아는 대로 설명해 주세요.

배열은 데이터를 물리적으로 연속된 공간에 저장하는 자료구조입니다.
빠른 *Random access가 가능하지만,
데이터를 삽입하거나 삭제할 때 모든 요소를 밀거나 당겨야 하기 때문에 비용이 발생한다는 단점이 있습니다.

연결 리스트는 노드와 링크를 구조화한 자료구조입니다.
데이터의 삽입과 삭제가 용이하지만, 조회할 때는 선형적으로 탐색해야 하기 때문에 속도가 느립니다.

*Random access : 배열에서 인덱스를 통해 데이터에 직접 접근하는 능력 (특정 위치의 데이터를 빠르게 가져올 수 있다.)

 

1-2. 배열과 연결 리스트의 시간복잡도에 대해 설명해 주세요.

배열에서 데이터를 삽입, 삭제할 때에는 해당 지점 이후의 모든 요소들을 이동시켜야 하므로
O(n)의 시간 복잡도를 가집니다.

그러나 조회할 때에는 인덱스를 통해 직접 접근할 수 있어
O(1)의 시간 복잡도를 가집니다.

연결 리스트에서 데이터를 삽입, 삭제할 때에는 해당 위치의 노드 포인터(주소)만 변경하면 되기 때문에
O(1)의 시간 복잡도를 가집니다.

그러나 조회할 때에는 특정 노드에 직접 접근하기 위해 처음부터 순차적으로 찾아야 하므로
O(n)의 시간 복잡도를 가집니다.

 

1-3. 연결 리스트에 대해 아는 대로 설명해 보세요.

연결 리스트는 데이터, 다음 요소를 가르키는 링크(포인터)로 이뤄진 자료구조입니다.
그 종류로는 단일 연결, 이중 연결, 원형 연결 리스트가 있으며
next 포인터만 있는지, prev 포인터와 next 포인터가 있는지
그리고 마지막 노드가 첫 번째 노드를 가리키는 원형의 형태인지에 따라 구분됩니다.

 

1-4. Stack(스택)과 Queue(큐)의 특징에 대해 설명해 주세요.

스택은 후입선출 구조로, 함수를 호출하거나 브라우저의 뒤로 가기와 같은 상황에서 사용됩니다.
큐는 선입선출 구조로, 운영체제의 작업 대기열이나 네트워크 패킷을 처리하는 데에 활용됩니다.

 

1-5.  Stack(스택)과 Queue(큐)의 시간복잡도에 대해 설명해 주세요.

스택과 큐는 모두 시간복잡도가 O(1)인 효율적인 자료 구조입니다.

맨 위나 맨 앞, 맨 뒤에 있는 데이터에 대해 작업을 진행하기 때문에 시간복잡도가 O(1)입니다.

 

1-6. 큐의 종류와 특징에 대해 설명해 주세요.

큐에는 선형, 원형, 우선순위 큐가 존재합니다.
선형 큐는 배열을 이용하며,
원형 큐는 배열의 처음과 끝을 연결해 순환 구조를 만듭니다.
우선순위 큐는 각 요소마다 우선순위를 가지고 있어, 우선순위가 높은 요소가 먼저 처리됩니다.

 

1-7. Stack(스택)과 Queue(큐)를 손코딩 해주세요.

class StackWithMaxSize {
  constructor(maxSize) {
    this.items = [];
    this.maxSize = maxSize;
  }
  
  // 스택에 요소 추가
  push(item) {
    if(this.stack.length < this.mazSize) {
      this.stack.push(item);
    } else {
      console.log("스택의 최대 크기에 도달했습니다.");
    }
  }
  
  // 스택에서 요소 꺼내기 및 반환
  pop() {
    if(!this.isEmpty()) {
      return this.stack.pop();
    } else {
      console.log("스택이 비었습니다.");
    }
  }
  
  // 스택의 최상단 요소 확인
  peek() {
    if(this.isEmpty()) {
      console.log("스택이 비었습니다.");
    } else {
      return this.items[this.items.length - 1];
    }
  }
  
  // 스택이 비어있는지 확인
  isEmpty() {
    return this.items.length === 0;
  }
  
  // 스택의 크기 확인
  size() {
    return this.stack.length;
  }
  
  // 스택의 내용을 문자열로 반환
  toString() {
    return this.items.toString();
  }
}

// 최대 크기가 3인 스택 생성
const stack = new StackWithMaxSize(3);

// 스택에 요소 추가
stack.push(1);
stack.push(2);
stack.push(3);

// 더이상 스택에 요소 추가 불가
stack.push(4); // 출력: "스택의 최대 크기에 도달했습니다."

// 스택의 크기 확인
console.log("스택의 크기는? ", stack.size()); // 출력: 스택의 크기는? 3

// 스택에서 요소 꺼내기
console.log(stack.pop()); // 출력: 3
console.log(stack.pop()); // 출력: 2
console.log(stack.pop()); // 출력: 1

// 스택이 비어있는지 확인
console.log("스택이 비어있는가?", stack.isEmpty()); // 출력: 스택이 비어있는가? true

class QueueWithMaxSize {
  constructor(maxSize) {
    this.items = [];
    this.maxSize = maxSize;
    this.rear = -1;
  }

  // 큐에 요소 추가
  enqueue(item) {
    if (this.size() < this.maxSize) {
      this.items.push(item);
      this.rear++;
    } else {
      console.log("큐의 최대 크기에 도달했습니다.");
    }
  }

  // 큐에서 요소 꺼내기 및 반환
  dequeue() {
    if (!this.isEmpty()) {
      this.rear--;
      return this.items.shift();
    } else {
      console.log("큐가 비었습니다.");
    }
  }

  // 큐의 가장 앞 요소 반환
  front() {
    if (this.isEmpty()) {
      console.log("큐가 비었습니다.");
    } else {
      return this.items[0];
    }
  }
  
  // 큐의 가장 뒷 요소 반환
  rear() {
    if(this.isEmpty()) {
      console.log("큐가 비었습니다.");
    } else {
      return this.items[this.rear];
    }
  }

  // 큐가 비어있는지 확인
  isEmpty() {
    return this.items.length === 0;
  }

  // 큐의 크기 확인
  size() {
    return this.items.length;
  }

  // 큐의 내용을 문자열로 반환
  toString() {
    return this.items.toString();
  }
}

// 최대 크기가 3인 큐 생성
const queue = new QueueWithMaxSize(3);

// 큐에 요소 추가
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

// 더 이상 큐에 요소 추가 불가
queue.enqueue(4); // 출력: "큐의 최대 크기에 도달했습니다."

// 큐의 크기 확인
console.log("큐의 크기는? ", queue.size()); // 출력: 큐의 크기는? 3

// 큐에서 요소 꺼내기
console.log(queue.dequeue()); // 출력: 1
console.log(queue.dequeue()); // 출력: 2
console.log(queue.dequeue()); // 출력: 3

// 큐가 비어있는지 확인
console.log("큐가 비어있는가?", queue.isEmpty()); // 출력: 큐가 비어있는가? true

// 큐의 가장 뒷 요소 조회
console.log("큐의 가장 뒷 요소는? ", queue.rear()); // 출력: 큐의 가장 뒷 요소는? undefined (비어있는 경우)

 

 

2. 비선형 구조에 대해 설명해 보세요.

비선형 구조는 일렬로 나열하지 않고 자료의 순서나 관계가 복잡한 구조를 말합니다.
이러한 비선형 구조에는 트리와 그래프가 있는데요.

*트리는 순환구조가 없는 계층적인 구조로, 부모-자식 관계를 표현합니다.

그래프는 노드와 간선으로 이뤄져 순환이나 계층 구조가 있을 수도 없을 수도 있습니다.
이런 그래프는 다양한 관계를 표현할 수 있기 때문에 더 유연한 구조를 가지고 있습니다.

*트리 : 간선 수 = 노드 수 -1

 

2-1. 이진 트리에 대해 설명해 주세요.

이진 트리는 각 노드가 최대 2개의 자식 노드를 가지는 트리 구조입니다.
이진 트리의 종류로는 이진 탐색 트리, AVL 트리, 레드블랙 트리가 있습니다.

 

2-2. 이진 탐색 트리에 대해 아는 대로 설명해 보세요.

이진 탐색 트리는
왼쪽 자식 노드가 현재 노드보다 작은 값을 가지고
오른쪽 자식 노드는 현재 노드보다 큰 값을 가지는 이진 트리를 말합니다.

이진 탐색 트리에서 데이터 조회할 때 평균 시간 복잡도는 O(log n)입니다.
이는 데이터를 반으로 나누어 검색하기 때문에 빠른 검색이 가능하다는 것을 의미합니다.

(최악의 경우) 그러나 데이터가 완전히 한쪽으로 치우친 경우,
트리의 모든 노드를 순회해야 하기 때문에 시간 복잡도가 O(n)이 될 수 있습니다.

 

2-3. AVL 트리에 대해 아는 대로 설명해 보세요.

AVL 트리는 균형 이진 탐색 트리의 한 종류로,
전체 노드에서 왼쪽과 오른쪽 서브 트리의 높이 차이를 1 이하로 유지하며 균형을 맞춥니다.
이로 인해 검색, 삽입, 삭제의 시간 복잡도는 항상 O(log n)이며, 이것을 유지하기 위해 *회전 연산을 사용합니다.

*회전 연산이 뭐예요? 회전 연산은 트리 구조 변경을 통해 노드의 높이 차이를 조절하는 연산

'비용이 든다'의 의미는 무엇일까 ? 특정 작업이 소요하는 자원, 얼마나 많은 시간을 소비하는지, 혹은 메모리를 소비하는지를 나타낸다.

 

2-4. 레드블랙트리에 대해 아는 대로 설명해 보세요.

레드블랙트리는 균형 이진 탐색 트리의 한 종류로,
레드, 블랙의 색상 규칙을 따라야 합니다.

루트 노드와 모든 *리프 노드(NIL)는 블랙이어야 하며, 연속된 레드 노드는 허용하지 않습니다.
또한 노드의 시작부터 끝까지 도달하는 모든 경로에는 동일한 수의 블랙 노드가 있어야 합니다.

이러한 균형 조건을 통해 검색, 삽입, 삭제에 대해
O(log n)이라는 시간 복잡도를 보장할 수 있습니다.

*NIL : 노드의 자식이 없을 경우, 자식으로 가리키는 포인터는 NIL 값을 저장한다.

 

2-5. 그래프의 종류에 대해 설명해 주세요.

그래프는 크게 방향 그래프와 무방향 그래프로 나뉩니다.

방향 그래프는 간선에 방향이 있어 A에서 B로 가는 간선, 또 B에서 A로 가는 간선이 다르게 존재합니다.
무방향 그래프는 간선에 방향이 없어 A와 B를 연결하는 간선은 양방향으로 표현됩니다.

 

2-6. 그래프를 표현하는 방법에는 어떤 것이 있나요?

그래프를 표현하는 방법으로는 인접 행렬과 인접 리스트가 주로 사용됩니다.

인접 행렬은 그래프의 연결 관계를 행렬(2D 배열)로 나타낸 것으로,
노드 간의 연결 여부를 0과 1로 표현합니다.
그래프의 크기가 작거나 밀도가 높을 때 효율적으로 사용될 수 있습니다.

인접 리스트는 그래프의 연결된 노드들을 리스트로 저장한 것으로,
매우 큰 그래프나 희소 그래프에 적합한 방법입니다.

인접 행렬

-   | A | B | C | D |
--- |---|---|---|---|
A   | 0 | 1 | 1 | 1 |
B   | 1 | 0 | 0 | 1 |
C   | 1 | 0 | 0 | 1 |
D   | 1 | 1 | 1 | 0 |

인접 리스트

A -> B -> C -> D
B -> A -> D
C -> A -> D
D -> A -> B -> C

 

 

3. 해시 테이블이 뭐예요?

해시 테이블은 키와 값을 저장하는 자료구조로, 키를 통해 값을 빠르게 찾을 수 있습니다.
해시 테이블은 해시 함수를 사용해 각 키를 고유한 인덱스로 매핑해 값을 저장하거나 검색할 수 있습니다.

해시 함수는 키에 대해 해시 코드를 생성하는 역할을 하는데,
이 때 서로 다른 키가 같은 해시 코드를 가질 수 있습니다.

이것을 해시 충돌이라 하는데, 이는 개방 주소법과 폐쇄 주소법을 사용하여 해결할 수 있습니다.

 

3-1. 해시 함수는 일대일 대응이 되나요?

해시 함수는 일반적으로 일대일 대응이 되지 않습니다.
서로 다른 입력값에 대해 동일한 해시값이 나올 수 있다는 것인데요, 이를 해시 충돌이라고 합니다.

해시 충돌은 해시 함수의 특성상 피할 수 없는 현상이기 때문에,
충돌을 최소화하는 것이 이상적인 해시 함수라고 볼 수 있습니다.

 

3-2. 해시 충돌의 해결 방법에 대해 설명해 주세요.

해시 충돌이 발생하면,
새로운 빈 버킷을 찾아 저장하는 개방 주소법과
충돌한 키를 같은 버킷 안에 연결 리스트나 트리로 함께 저장하는 폐쇄 주소법을 사용할 수 있습니다.

 

3-3. 해시 테이블의 시간 복잡도에 대해 설명해 주세요.

해시테이블은 고유한 인덱스로 값을 조회하기 때문에 평균적으로 O(1)의 시간 복잡도를 갖습니다.
그러나 인덱스 값에 충돌이 일어날 경우 인덱스에 연결된 데이터를 모두 조회할 수 있기 때문에
O(n)의 시간 복잡도를 가질 수 있습니다.

 

 

4. 힙(Heap)에 대해 아는 대로 설명해 보세요.

힙은 규칙에 따라 정렬된 이진 트리 구조로, 최대값과 최솟값을 빠르게 찾기 위해 사용합니다. O(log n)

최대 힙은 부모가 자식이 가진 값의 이상을 가지며,
최소 힙은 부모가 자식이 가진 값의 이하를 갖습니다.

새로운 데이터가 들어올 경우, 힙의 마지막 노드에 이어 삽입하고 부모와 크기를 비교하며 교환하는 것을
재귀적으로 수행하여 힙의 성질을 유지합니다.

데이터를 삭제할 경우, 루트 노드를 삭제와 함께 힙의 마지막 노드를 루트 노드의 자리로 옮깁니다.
이후 자식과 비교하여 위치를 조정하고 힙의 성질을 유지합니다.

- 힙 (Heap) 예시:

      10
     /  \
    20   15
   / \
  25  30

 

5. 맵(Map)에 대해 아는 대로 설명해 보세요.

맵은 키와 값을 저장하는 자료구조로, 키를 사용해 값을 검색하고 저장합니다.
JavaScript의 Object가 맵의 예시 중 하나입니다.

- 맵 (Map) 예시:

  | Key   | Value    |
  |-------|----------|
  | "A"   | "Apple"  |
  | "B"   | "Banana" |
  | "C"   | "Cherry" |

 

5-1. 맵을 손코딩 해주세요.

const contact = new Map();

contact.set("김한슬", "010-0000-0000");
contact.set("홍길동", "010-0000-0000");

console.log(contact.get("김한슬"); // 출력: "010-0000-0000"
console.log(contact.get("아무개"); // 출력: undefined

 

 

6. 셋(Set)에 대해 아는 대로 설명해 보세요.

셋은 중복되지 않는 값을 저장하는 자료구조로, 유일한 원소들이 모여있습니다.

- 셋 (Set) 예시:

  | Element |
  |---------|
  | "Apple" |
  | "Banana"|
  | "Cherry"|

 

6-1. 셋을 손코딩 해주세요.

const fruits = new Set(["apple", "banana", "orange"]);

// 중복 제거
fruits.add("apple");
fruits.add("kiwi");

console.log(fruits); // 출력: Set { 'apple', 'banana', 'orange', 'kiwi' }

// 멤버십 테스트
console.log(fruits.has("banana")); // 출력: true
console.log(fruits.has("grape"));  // 출력: false