DataStructure_question.md

자료구조 예상 질문

⭐ 자료구조 정의와 자료구조가 중요한 이유가 무엇인가요?

자료구조란 데이터를 저장하고 처리하는 방식을 말하며,
자료구조에 따라 데이터의 처리 속도가 달라지기 때문에 구조를 사용하는 것이 프로그램의 성능에 영향을 미칠 수 있어 중요합니다.

⭐ 자료구조와 알고리즘의 차이는 무엇일까요?

자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고,
알고리즘이란 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임

⭐ 자료구조란 무엇이며 자료구조가 중요한 이유가 무엇인가요?

자료구조란 데이터를 저장하고 처리하는 방식을 말하며,
자료구조에 따라 데이터의 처리 속도가 달라지기 때문에 상황에 맞는 구조를 사용하는 것이 프로그램의 성능에 중요한 역할을 할 수 있습니다.

⭐ Java Collection의 종류에 대해서 설명해주세요.

List, Set, Map, Stack, Queue 등이 있습니다.
List는 삽입 순서에 맞게 저장, 중복 가능
Set은 순서와 상관없이 중복저장이 불가능
Map은 Key, Value 형태로 이루어지며 Key의 중복이 불가능
Stack은 나중에 들어온 것이 먼저 나가는 후입선출(LIFO)
Queue는 먼저 들어온 것이 먼저 나가는 선입선출(FIFO)

✋ 프로젝트 진행시 Collection을 활용한 경험에 대해서 설명해주세요.

나라면 이렇게 말할 듯

같은 이미지 URL을 가진 것은 중복저장하지 않기 위해서 HashSet 을 활용해서 중복된 데이터는 저장하기 않도록 활용했습니다.

⭐ ArrayList란 어떤 자료구조인가요?

ArrayList는 논리적 저장순서와 물리적 저장 순서가 일치하는 자료구조입니다.
인덱스를 통해 데이터에 접근할 수 있기 때문에 참조에 O(1)의 시간 복잡도를 가집니다.
But❗ 데이터를 삽입하거나 삭제하는데에는 다른 데이터의 순서를 모두 옮겨야 하기 때문에 O(N)의 시간 복잡도를 가지게 됩니다.

⭐ LinkedList는 어떤 자료구조인가요?

LinkedList는 연결리스트라고도 하며, 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는 자료구조입니다.
각 원소들은 데이터와 그 다음 연결된 원소의 참조 주소를 값으로 가집니다. 그래서 주소 값을 바꾸는 것만으로 삽입과 삭제가 가능합니다.

단점1 : 원하는 원소에 접근하기 위해서는 처음부터 순회를 시작해야한다.
단점2: 접근, 삽입, 삭제 작업 모두 O(N)의 시간이 소요.

⭐ 그렇다면 ArrayList와 LinkedList는 어떤 차이를 가지나요?

ArrayList는 각 원소에 인덱스를 부여하여 값을 관리하므로 원소에 접근할 때 O(1)의 시간 복잡도를 가지지만,
LinkedList는 원하는 원소에 접근할 때 항상 첫 원소부터 순회해야 하므로 O(n)의 복잡도를 가지게 됩니다.
삽입, 삭제의 경우 O(n)으로 시간 복잡도는 동일하지만 Array리스트는 다른 원소의 위치를 모두 옮겨야 하는 반면 LinkedList는 원소의 주소값만 변경하면 삽입 삭제가 가능하다는 차이가 있습니다.

⭐ Array와 ArrayList의 차이가 무엇인가요?

Array와 ArrayList은 모든 것이 비슷합니다.

둘의 가장 큰 차이점은 길이를 조정할 수 있는가? 없는가? 입니다.

Java에서 Array는 고정길이입니다.
ArrayList는 가변길이입니다.

그러나 ArrayList도 내부적으로는 Array로 구현되어 있어서 길이가 늘어날 때 임시배열을 활용하여 이전 배열의 요소 값을 저장해놨다가 새 배열에 복사하기 때문에 Array보다는 속도가 늦습니다.

⭐ Stack과 Queue의 차이점은 무엇인가요?

스택과 큐의 가장 큰 차이는 데이터 사용 순서에 있습니다.
스택은 ~~
큐는 ~~

⭐ PriorityQueue에 대해서 설명해주세요.

PriorityQueue는 우선순위 큐라고 하며, 먼저 넣은 자료가 가장 먼저 처리되는 기존의 큐와 달리 각 자료에 우선 순위가 부여되고 우선순위가 높은 자료를 먼저 처리하는 자료구조 입니다.

일반적으로 힙 자료구조를 통해 구현됩니다.
힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도 또한 O(logN)입니다.

⭐ BST와 Binary Tree에 대해서 설명하세요.

이진탐색트리(Binary Search Tree)는 이진 탐색 + 연결 리스트를 결합한 자료구조이다.
이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다.
이진 탐색 트리는 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작아야 하고, 반대로 오른쪽 트리의 모든 값이 부모 노드보다 커야 하는 특징을 가지고 있어야 한다.
이진 탐색 트리의 탐색, 삽입, 삭제의 시간복잡도는 O(h)이다. 트리의 높이에 영향을 받는데, 트리가 균형이 맞지 않으면 워스트 케이스가 나올 수 있다.
그래서 이 균형을 맞춘 구조가 AVL Tree이다.

⭐ 해시테이블(HashTable)에 대해서 설명해주세요.

해시 테이블은 {Key:value}로 데이터를 저장하고 있는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.
빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.
각 Key 값은 해시함수에 의한 고유한 index를 가지므로 바로 접근이 가능하여 O(1)의 시간 복잡도로 조회한다.
그러나‼, index 값이 충돌할 경우 Chaining에 연결된 리스트들 까지 검색해야하므로 최악의 경우 O(N)까지 증가할 수 있다.

⭐ HashMap과 HashTable의 차이점에 대해 설명 해보세요.

1️⃣동기화 지원 여부와 2️⃣null 값 허용 여부에 따른 차이가 있다.

해시 테이블

• 병렬 처리(동기화를 고려하는 상황)를 할 때 Thread-safe하다.
  
• Null 값을 허용하지 않는다.

해시 맵

• 병렬 처리를 하지 않을 때(동기화를 고려하지 않는 상황) Thread-safe하지 않는다.
  
• null값을 허용한다.

❓ 예상 질문

📰 Reference

Array와 ArrayList의 차이 자료구조 면접 질문 모음