자료구조 면접 질문 정리

[Choisehyeon]

• Array vs ArrayList
• Array vs LinkedList
• PriorityQueue에 대해 설명해주세요.
• 해시 테이블과 시간 복잡도에 대해 설명해주세요
• 해시 충돌은 무엇이고 해시 테이블에서 충돌 문제를 해결하기 위한 방법
• Hash Map과 Hash Table의 차이점
• BST(Binary Search Tree, 이진탐색트리)에 대해 설명
• BST의 최악의 경우의 예와 시간복잡도에 대해서 설명해주세요.
• AVL 트리와 Red-Black 트리는 무엇인가요?
• DFS, BFS에 대해서 설명
• Stack 두 개를 이용하여 Queue를 구현해 보세요
• Queue 두 개를 이용하여 Stack을 구현해 보세요
• 힙은 무엇인가요?
• 이진 탐색 트리, 포화 이진 트리, 완전 이진 트리에 대해 간단하게 설명해주세요.
• Red-Black 트리의 조건에 대해 설명해주세요.
• List와 Set의 차이를 사용해본 경험이 있으면 설명해주세요.
• deque과 이중 연결 리스트의 차이가 무엇인가요?
• JCF의 ArrayList와 Kotlin Collection의 ArrayList는 어떤 차이가 있나요?
• ArrayList가 어떻게 가변적인 크기를 가지나요?
• Iterable과 Iterator의 차이는 무엇인가요?
• 단일 링크드 리스트와 이중 링크드 리스트의 차이는 무엇인가요?
• 단일 링크드 리스트가 이중 링크드 리스트에 비해 가지는 장점은 무엇인가요?
• Graph vs Tree 차이점
• JCF가 무엇인지와 주요 인터페이스들 각각의 특징
• List와 Set 시간복잡도의 차이
• List distinct함수를 사용하는 것과 Set을 사용하는 것의 차이
• 우선순위 큐의 내부 구조
• Arary, List, ArrayList, MutableList의 차이는 무엇인가요?
• 큐와 스택, 덱 각각의 특성이 무엇인가요? 어디에서 주로 사용되나요?
• 각 자료구조 메서드와 시간복잡도는 어떻게 되나요?(리스트, 배열, 해시 등)
• Java에서 스택과 큐를 어떻게 구현할 수 있나요?
• JCF에서 Set 인터페이스의 특징은 무엇인가요?
• 비전공자애개 큐와 스택을 설명해보세요.

---

• 라이브 코딩 -> 본인 코드의 시간/공간 복잡도 말하기
• Tree 예시를 주고, 해당 tree에서 삽입/삭제 등이 어떻게 이뤄질 것인지 설명하기

[sujin9]

Array vs ArrayList

Array는 크기가 정해진 배열이고,
ArrayList는 배열의 크기가 넘어가면 동적으로 크기가 늘어난다.

[s9hn]

Array vs LinkedList

Array는 정적자료구조이며, LinkedList는 동적자료구조이다.

[no1msh]

PriorityQueue에 대해 설명해주세요.

우선순위큐는 우선순위를 정하는 로직을 바탕으로 큐의 맨처음 front로 갈 데이터를 정하는 방식의 자료구조입니다.
일반적으로 힙으로 구현하여 사용합니다.

[hyemdooly]

해시 테이블과 시간 복잡도에 대해 설명해주세요

해시테이블은 key-value로 이루어진 자료구조입니다.
이 때 key를 hash function에 넣어 hash를 얻을 수 있는데, 얻은 hash를 index값으로 하여 이 hash값을 참조하면 value를 얻을 수 있습니다.
시간복잡도는 평균적으로 O(1)입니다.

[Choisehyeon]

해시 충돌은 무엇이고 해시 테이블에서 충돌 문제를 해결하기 위한 방법

해시 충돌은 다른 키를 넣었는데 같은 해시 값이 나오는 경우를 말합니다.

충돌 해결법

1. 체이닝 방식

• 해시 충돌이 발생하면 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식

2. 개방 주소법

• 선형 조사법: 해시 충돌이 일어나면 다음 인덱스로 이동하면서 빈 공간을 찾는 방식
• 이차 조사법: 해시 충돌이 일어나면 거듭제곱한 인덱스만큼 이동하면서 빈 공간을 찾는 방식
• 이중 해싱: 해시 충돌이 발생하면 다른 해시 함수를 한 번 더 적용하는 방법

[krrong]

Hash Map과 Hash Table의 차이점

Hash Map은 key에 null 값을 허용하지만 Hash Table의 경우 null 값을 허용하지 않습니다.
Hash Table의 모든 Data 변경 메소드는 synchronized로 선언되어 있어 멀티 쓰레드 환경에서 데이터의 무결성을 보장해줍니다.

[sujin9]

BST(Binary Search Tree, 이진탐색트리)에 대해 설명

한 노드의 왼쪽 서브 트리는 해당 노드보다 작은 값,
한 노드의 오른쪽 서브 트리는 해당 노드보다 큰 값을 가진 노드들로 구성되어 있는 트리입니다.

균형 잡힌 이진 탐색 트리의 경우, 검색해야 할 노드 개수가 절반으로 줄어들어 검색에 O(logn)이 소요됩니다.

[s9hn]

BST의 최악의 경우의 예와 시간복잡도에 대해서 설명해주세요.

평균적으로 O(logn)이 소요되며, 불균형 이진 탐색 트리는 최악의 경우이다. 이 경우 O(n)이 소요되므로 이진탐색 트리를 이용하는 장점이 사라진다.

[no1msh]

AVL 트리와 Red-Black 트리는 무엇인가요?

둘 다 균형 이진 탐색 트리의 일종으로
레드 블랙 트리는 검은색과 빨간색으로 이루어진 노드로 이루어진 트리이며 정해진 조건에 따라 노드의 색을 바꾸거나 회전시켜 균형을 유지합니다.
AVL 트리는 밸런스 팩터를 사용하여 불균형을 인지하고 회전시켜 균형을 맞추는 트리입니다.

[hyemdooly]

DFS, BFS에 대해서 설명

DFS는 깊이우선탐색으로 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색합니다. 최대 깊이의 정점에 도달한 후에는 방문한 정점을 역순으로 다시 재방문하면서, 또 탐색 가능한 정점이 있다면 반복해서 그 정점부터 최대 깊이의 정점까지 탐색합니다. 재귀 호출이나 스택으로 구현할 수 있습니다.
BFS는 너비우선탐색으로 시작 정점에서 가까운 정점을 먼저 탐색합니다. 방문한 정점을 체크하면서 인접한 정점을 탐색하며 큐에 삽입합니다. BFS를 사용하면 비가중치 그래프에서 시작 정점부터 특정 정점까지의 최단 거리를 알 수 있습니다.

[Choisehyeon]

Stack 두 개를 이용하여 Queue를 구현해 보세요

Queue는 FIFO 방식으로 먼저 넣은 데이터가 먼저 나오는 방식입니다.

1,2,3,4를 넣은 경우 1,2,3,4 순으로 나오게 하기위해 stack 2개를 사용하려면

1. stack1에 1,2,3,4 순으로 push를 합니다.
2. stack1이 empty가 될 때까지 stack1을 pop하고 pop한 데이터를 stack2에 push합니다.
3. 그다음 stack2가 empty가 될 때까지 pop을 하면 1,2,3,4순으로 나옵니다.

[krrong]

Queue 두 개를 이용하여 Stack을 구현해 보세요

A, B큐가 있고 N개의 데이터가 있다고 가정합니다.

1. A큐에 모든 데이터를 넣고 데이터가 하나 남을 때까지 B큐에 옮깁니다.
2. A큐에 남은 데이터를 반환하고 B큐에 있는 데이터를 다시 A큐에 옮깁니다.
3. 1 -> 2 의 과정을 반복합니다.

[sujin9]

힙은 무엇인가요?

완전 이진 트리의 일종으로, 최대값 또는 최소값 및 우선순위가 높은 노드를 빠르게 찾을 수 있는 자료구조입니다.
우선순위 큐를 구현하는 데 주로 사용됩니다.

[s9hn]

이진 탐색 트리, 포화 이진 트리, 완전 이진 트리에 대해 간단하게 설명해주세요.

완전 이진 트리 : 트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며 마지막 레벨은 왼쪽에서 오른쪽으로 노드가 채워져 있다.

포화 이진 트리 : 트리의 마지막 레벨까지 노드가 모두 채워져 있다. 포화 이진 트리는 완전 이진 트리이다.

이진 탐색 트리 : 한 노드의 왼쪽 서브트리는 해당 노드보다 작은 값, 오른쪽은 해당 노드보다 큰 값으로 구성된다.

[no1msh]

Red-Black 트리의 조건에 대해 설명해주세요.

• 모든 노드는 검은색 또는 빨간색이다.
• 루트 노드는 검은색이다.
• 모든 단말노드(NIL)는 검은색이다.
• 빨간색 노드의 자식 노드는 검은색이며 빨간색 노드가 연속으로 나올 수 없다.
• 루트 노드에서 임의의 단말 노드까지 경로에 검은색 노드의 개수는 모두 같다.

[hyemdooly]

List와 Set의 차이를 사용해본 경험이 있으면 설명해주세요.

List는 순서가 보장되고 중복 요소가 들어갈 수 있는 경우 사용합니다.
Set은 순서가 보장되지 않고 중복 요소가 들어가지 않는 경우 사용합니다.
List은 인덱싱하거나 슬라이싱해야하는 경우, Set은 집합과 같은 구조를 구현해야하는 상황에 사용했습니다.

[Choisehyeon]

deque과 이중 연결 리스트의 차이가 무엇인가요?

deque은 이중연결리스트 + 큐로 구현할 수 있어서 has-a 관계라고 할 수 있습니다.
deque은 삽입, 삭제시 앞 뒤로만 할 수 있지만 이중 연결리스트는 중간부분에서도 삽입, 삭제가 가능합니다.

[krrong]

JCF의 ArrayList와 Kotlin Collection의 ArrayList는 어떤 차이가 있나요?

val a = ArrayList<Int>()
val b = mutableListOf<Int>()

의 차이는 무엇인가요?

ArrayList는 List를 상속받는 ArrayList가 반환됩니다.
mutableListOf는 MutableList를 상속받는 ArrayList가 반환됩니다. (이렇게 쓰는거 추천)

[sujin9]

ArrayList가 어떻게 가변적인 크기를 가지나요?

ArrayList에 값이 꽉 차면,
내부적으로 grow() 메소드가 호출됨으로써 기존에 갖고 있던 크기의 1.5배로 그 크기가 증가하게 됩니다.
이러한 방식을 통해 동적으로 크기가 증가함으로써 가변적인 크기를 가질 수 있습니다.

[s9hn]

Iterable과 Iterator의 차이는 무엇인가요?

전자는 인터페이스이고, 후자는 메서드이지만, Iterator에 대한 반환타입을 찾아보면 인터페이스로도 존재한다.

[no1msh]

단일 링크드 리스트와 이중 링크드 리스트의 차이는 무엇인가요?

크게 차이나는 점은 노드에 있습니다.
단일 링크드 리스트의 경우 다음 노드를 가리키는 포인터와 데이터로 이루어져 있으며,
이중 링크드 리스트는 더불어서 이전노드를 가리키는 포인터가 추가로 있습니다.

이럼으로써 이중 링크드 리스트는 가진 노드들의 맨 마지막 부분부터 탐색이 가능하지만, 단일 링크드 리스트에 비해 공간적 효율이 떨어지는 단점을 가지고 있습니다.

[hyemdooly]

단일 링크드 리스트가 이중 링크드 리스트에 비해 가지는 장점은 무엇인가요?

이중 링크드 리스트는 이전 노드의 값도 가지고 있기 때문에 단일 링크드 리스트보다 더 많은 메모리 공간을 필요로 합니다.
따라서, 단일 링크드 리스트가 이중 링크드 리스트보다 메모리 공간을 적게 사용합니다. 또한 이중보다 단일 링크드 리스트가 구현하기 더 쉽습니다.

[Choisehyeon]

Graph vs Tree 차이점

Graph는 정점과 간선으로 구현된 자료구조이고 Tree는 그래프의 한 종류로 사이클이 없이 계층적 관계를 표현하는 자료구조 입니다.

[krrong]

JCF가 무엇인지와 주요 인터페이스들 각각의 특징

Java Collection Framework의 줄임말입니다.
크게 Iterable 인터페이스와 Map인터페이스로 나뉘며 Iterable 인스터페이스는 다시 List, Set, Queue로 나뉩니다.

• List
  • 인덱스를 사용하여 데이터에 접근할 수 있습니다.
• Set
  • 중복 요소를 저장하지 않습니다.
  • 순서를 유지하지 않습니다.
  • 중복 요소를 걸러내기 위해 equals와 HashCode를 사용합니다.
• Queue
  • (Priority) 우선순위에 따라 요소가 먼저 나가는 방식입니다.

[sujin9]

List와 Set 시간복잡도의 차이

List는 순서가 있고, 중복이 허용되는 데이터의 집합입니다.

• ArrayList의 경우, 배열의 형태로 저장되므로 인덱스로 접근할 수 있다는 특징이 있습니다.
  다만, 삽입 또는 삭제의 경우 다른 요소들의 이동 연산이 필요합니다.
  • 검색: O(1)
  • 삽입/삭제: O(n)
• LinkedList의 경우, 노드를 이용해 선형적으로 연결된 구조로 저장됩니다.
  데이터를 찾기 위해 처음부터 탐색을 해나가야 합니다.
  • 검색: O(n)
  • 삽입/삭제: 연산 자체는 O(1)

Set은 순서가 없고, 중복이 불가능한 데이터의 집합입니다.

• HastSet은 Hash Table을 사용하여 데이터를 저장합니다.
  • 검색/삽입/삭제: O(1)
  • hash충돌이 자주 발생할 경우 성능이 저하될 수 있습니다.
• TreeSet은 이진 검색 트리 (BST)를 사용하여 데이터를 정렬한 상태로 저장합니다.
  • 검색/삽입/삭제: O(logn)

[s9hn]

List distinct함수를 사용하는 것과 Set을 사용하는 것의 차이

public fun <T> Iterable<T>.distinct(): List<T> { return this.toMutableSet().toList() }
LinkedHashSet 으로 뱉는다.

따라서 전자는 순서가 보장되며 후자는 보장x

[no1msh]

우선순위 큐의 내부 구조

JVM의 우선순위 큐(Priority Queue)를 기준으로 설명드리겠습니다.
내부에 Comparable 인터페이스가 있어서 compareTo() 메서드를 오버라이드 해야 사용할 수 있습니다.
이 compareTo()메서드를 통해 A가 B보다 크다면 1 같다면 0 적다면-1 이런식으로 내부에서 데이터를 비교하는 기준을 가지고 있으며 힙으로 구현 됩니다.

[hyemdooly]

Arary, List, ArrayList, MutableList의 차이는 무엇인가요?

Array는 정적 할당으로 선언 시 크기를 지정하거나 초기화를 해주어야합니다. 또한, 요소의 변경은 가능하지만 추가나 삭제는 불가능합니다.
ArrayList는 요소 변경, 추가 ,삭제 모두 가능합니다.
List는 interface로, 요소 수정이 불가능합니다.
MutableList는 interface로, 요소 변경, 추가, 삭제 모두 가능합니다.
ArrayList와 MutableList의 차이는 ArrayList를 사용하면 Java의 ArrayList가 사용되며, mutableListOf 함수를 사용하면 Kotlin에 정의된 ArrayList가 사용됩니다.

[Choisehyeon]

큐와 스택, 덱 각각의 특성이 무엇인가요? 어디에서 주로 사용되나요?

큐는 FIFO 방식(선입선출)으로 OS에서 실행을 기다리는 준비큐에 사용됩니다,
스택은 LIFO 방식(후입선출)으로 웹 브라우저 뒤로가기에서 많이 사용됩니다.
덱은 스택 + 큐를 합친 구조로 앞, 뒤에서 넣을 수 있고 나올 수 있는 구조로 스택, 큐를 사용하는 곳에서 다 사용할 수 있습니다.

비전공자애개 큐와 스택을 설명해보세요.

스택은 프링글스를 예시로 들어 나중에 넣은 것부터 꺼낼 수 있음을 설명합니다.
큐는 선입선출 방식으로 음식점이나 편의점에서 아르바이트할 때 물건을 진열시 먼저 들어온 물건을 맨 앞으로 진열하도록 하여 손님이 앞에 물건을 먼저 가져갈 수 있도록 함을 설명합니다.

[krrong]

각 자료구조 메서드와 시간복잡도는 어떻게 되나요?(리스트, 배열, 해시 등)

• 배열
  • 탐색 : O(1) -> 인덱스를 사용하여 접근하기 때문에 상수시간안에 접근이 가능합니다.
  • 삽입 : O(1) -> 인덱스를 사용하여 접근하기 때문에 상수시간안에 접근이 가능합니다.
  • 삭제 : O(1) -> 인덱스를 사용하여 접근하기 때문에 상수시간안에 접근이 가능합니다.
• 리스트(링크드 리스트)
  • 탐색 : O(N) -> 처음부터 데이터를 찾아야 하기 때문에 선형시간이 걸립니다.
  • 삽입 : O(N) -> 삽입 자체의 시간 복잡도는 O(1)이지만 데이터를 특정 위치에 데이터를 넣어야 한다면 처음부터 데이터를 찾아야 하기 때문에 선형시간이 걸립니다. / 만약 처음이나 마지막에 데이터를 추가하면 O(1)이 걸립니다.
  • 삭제 : O(N) -> 삭제 자체의 시간 복잡도는 O(1)이지만 데이터를 특정 위치에 데이터를 넣어야 한다면 처음부터 데이터를 찾아야 하기 때문에 선형시간이 걸립니다. / 만약 처음이나 마지막에 데이터를 추가하면 O(1)이 걸립니다.
• 해시 테이블
  • 탐색 : O(N) -> Hash function에 영향을 받고, 하나의 해시 값에 모든 데이터가 몰릴 수 있기 때문에 최악의 경우 선형시간이 걸립니다.
  • 삽입 : O(N) -> Hash function에 영향을 받고, 하나의 해시 값에 모든 데이터가 몰릴 수 있기 때문에 최악의 경우 선형시간이 걸립니다.
  • 삭제 : O(N) -> Hash function에 영향을 받고, 하나의 해시 값에 모든 데이터가 몰릴 수 있기 때문에 최악의 경우 선형시간이 걸립니다.

[sujin9]

Java에서 스택과 큐를 어떻게 구현할 수 있나요?

List, Deque를 통해 스택을 구현할 수 있고,
List, Queue 및 Deque를 통해 큐를 구현할 수 있습니다.

[s9hn]

JCF에서 Set 인터페이스의 특징은 무엇인가요?

중복 요소를 저장하지 않으며 순서 또한 보장되지 않는다.