[CS] CS 면접 대비 : 자료구조 2

기술면접 예상 질문 및 답변

자바에서 Hash Table과 Hash Map의 차이

자바에서 해시 테이블은 키가 같은 값을 두번 이상 넣으면 초기 값을 유지하고, 해시 맵은 나중에 들어간 값으로 덮어버린다는 차이가 있습니다.

그리고 해시 테이블은 thread-safe 하지만, 해시맵은 thread-safe하지 않기 때문에 멀티 스레드 환경이 아니라면 해시 테이블이 해시 맵보다 성능이 떨어진다는 특징이 있습니다.

또한 해시 테이블은 key에 null을 허용하지 않지만, 해시 맵은 key에 null을 허용합니다.

 

HashMap, TreeMap, LinkedHashMap 공통점과 차이점

hashmap은 내부적으로 <k,v>쌍을 갖는 entry 배열로 되어 있습니다. 따라서 검색 성능이 O(1)로 가장 좋습니다. 해당 배열의 index는 내부 해시 함수를 통해 계산됩니다.

treemap은 내부적으로 redBlack tree로 저장됩니다. 일반적으로 키 값이 알파벳 순서로 정렬되며, 트리에 저장되므로 일정한 기준으로 정렬된 상태로 출력됩니다. 키 값에 대한 Comparator를 구현하여 정렬 순서를 바꿀 수 있습니다. 키 값이 일정 기준으로 탐색될 때 사용합니다.

linkedHashMap은 linked list로 저장되어 키 값은 입력 순서대로 출력됩니다. 입력 순서가 중요한 경우 사용합니다. 그러나 랜덤 접근에 대해 O(n)의 성능을 가지므로 많은 데이터를 입력할 경우에는 비효율적입니다.

 

최대 / 최소 힙의 push / pop 과정

• pop - 루트 노드가 pop 되었을 때 제일 말단 노드가 루트 노드로 올라오고 자식 노드와 비교하여 최대 힙일 경우 더 큰 값과, 최소 힙일 경우 더 작은 값과 계속 스왑하여 자리를 맞춰 나갑니다.
• push - 말단 노드에 삽입 후 부모 노드와 비교하여 최대 힙일 경우 부모 노드가 작으면 스왑, 최소 힙일 경우 부모 노드가 크면 스왑합니다.

 

데이터가 N개 정렬되어 있을 때와 정렬되어 있지 않을 때 탐색하는 시간복잡도

• 정렬되어 있다면 이진 탐색을 통해 O(logN)
• 정렬되어 있지 않다면 선형 탐색을 통해 O(N)의 시간 복잡도 발생

 

list, set, map의 차이

• list - 데이터가 순서대로 저장되며 중복을 허용합니다.
• set - 테이터의 중복을 허용하지 않고 순서는 보장되지 않습니다.
• map - key value 형태의 자료구조로 key는 중복을 허용하지 않고 value는 중복을 허용하지 않는다. 순서도 보장되지 않습니다.

 

array, list의 차이

• array
  • 논리적 저장 순서와 물리적 저장 순서가 일치하는 자료구조입니다.
  • 처음 할당된 크기 만큼 메모리가 정해져 있습니다.
  • 데이터 접근이 빠르나 삽입 및 삭제가 이루어 질 경우 데이터를 쉬프트해야 하기 때문에 O(n) 발생합니다.
• list
  • 배열의 문제점을 해결하기 위한 자료구조입니다.
  • 크기에 자유롭습니다.
  • 포인터를 통해 다음 데이터를 가리키고 있기 때문에 삽입 및 삭제에 용이합니다.
  • 물리적으로 순차적이지 않기 때문에 순차적으로 탐색을 해야합니다. ( O(n) )

 

tree란?

노드들이 간선을 통해 사이클이 이루어지지 않도록 연결된 계층적 자료구조입니다.

 

DFS, BFS의 차이

• DFS ( 깊이 우선 탐색 )
  • stack 혹은 재귀를 사용합니다.
  • 한 분기를 끝까지 탐색 후 다음 분기를 탐색합니다.
  • 원하는 해가 분기의 끝에 있을 경우 유리합니다.
  • 해가 최적의 해라는 보장은 없습니다.
• BFS ( 너비 우선 탐색 )
  • Queue를 사용합니다.
  • 인접한 모든 노드들을 우선적으로 탐색합니다.
  • 최적의 해를 보장합니다.
  • 최악의 경우 가장 오랜 시간이 걸립니다.

 

MST 알고리즘에 대해

• 최소 신장 트리
  • 그래프의 모든 노드를 포함하며 사이클이 생기지 않게 가중치의 최소인 트리를 구하는 알고리즘입니다.
• 크루스칼
  • 간선의 가중치를 정렬 후 사이클이 만들어지지 않게 가중치가 낮은 것부터 연결합니다.
• 프림
  • 시작 정점으로부터 가중치가 낮은 간선을 찾아 사이클이 생기지 않게 확장해 나가는 알고리즘입니다.

 

플로이드 워셜이란?

• O(n^3)
• 경유하는 정점을 기준으로 최단 거리를 구해 모든 정점 간의 최단 거리를 구하는 알고리즘입니다.

 

다익스트라 알고리즘이란?

특정 정점에서 다른 모든 정점간의 최단 경로를 구하는 알고리즘입니다. 음의 가중치를 가진 간선이 있을 경우에는 사용할 수 없습니다. 우선순위 큐를 사용해 알고리즘 성능을 개선할 수 있습니다.

 

Hash의 평균 복잡도와 최악의 경우 시간 복잡도, 그 이유는?

• 평균 적인 시간 복잡도는 O(1)
  • 해싱을 통해 위치를 참조하므로
• 최악의 경우 O(n)
  • 해시가 충돌 되었고 체이닝으로 되어있을 때 원하는 데이터를 찾는다면 리스트의 탐색이 필요함

 

해싱이란?

가변적인 데이터를 해시 함수를 통해 동일한 크기의 데이터를 생성하는 것입니다.

 

해시의 충돌이 일어났을 때 대처 방법

• 다른 해시 함수를 사용하여 재해싱
• 버킷을 리스트로 구현 ( 체이닝 )
• 오픈 어드레스

 

자바에서 스택과 큐의 차이점

• 스택은 클래스로 구현됩니다.
• 큐는 인터페이스이며 LinkedList를 구현체로 사용합니다.
  • 큐는 선입 선출 구조이기 때문에 만약 arraylist로 구현했다면 데이터를 pop 했을 경우 쉬프트 해줘야 하기 때문에 삽입 / 삭제에 용이한 LinkedList를 사용합니다.
    • 번외로 큐가 인터페이스인 이유는 deque, priority queue의 확장 및 상속을 위함입니다.