2023.01.07 TIL(자료구조 CS Q&A 정리)

자료구조

1. 좋아하는 자료구조가 있다면 이유와 함께 설명해주실 수 있을까요?
   
   
   
2. 스택, 큐에 대해 설명해주실 수 있을까요?
   스택 - 쌓다의 의미를 가진 스택은 후입선출[LIFO (Last In First Out)] 입니다. 한 방향으로만 입력할 수 있으며 구조 중간에 값을 끼어 넣어 저장할 수 없는 한쪽이 막힌 상자와 같습니다. 같은 크기의 자료를 정해진 한 방향으로만 Push, Pop이 가능합니다. 자료를 넣을때가 Push이고, 자료를 뺄때가 Pop입니다.. 예를 들자면 웹 서핑을 한다는 가정하에 방문한 페이지에 로그가 남을 것입니다. 마지막에 방문한 페이지에서 뒤로가기를 했을때 바로 전 페이지로 이동하는게 스택 입니다. 무언가 실행취소(Ctrl+Z) 또한 같은 예 입니다.
   
   큐 - 대기줄 이라는 의미를 가진 큐는 스택과 반대로 선입선출[FIFO (First In First Out)] 입니다. 양방향이 뚫려있는 원통 형태와 같으며, 한쪽은 데이터 입력, 다른 한쪽은 데이터 출력이 진행됩니다. 큐는 원통에 1번째로 1 이어서 2,3이 추가 되었다면 들어가는 입구 Rear(리어)이라고 하고 나오는 곳을 Front(프론트)라고 한다. Rear(리어)에서 이뤄지는 입력 연산을 enQueue(인큐)라고 하며, Front(프론트)에서 이뤄지는 출력 연산을 deQueue(디큐)라고 합니다. 은행 업무를 예로 들 수 있습니다. 먼저 온 손님이 나중에 온 손님보다 번호표를 빠르게 뽑고, 먼저 온 손님이 먼저 은행 업무를 보는 은행 번호표 체계가 큐 입니다.
   
   
   
3. 배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?
   배열(Array)는 정적 자료구조 입니다. 배열(Array)을 만들기 위해서는 미리 크기를 정해 놓게 됩니다. 그렇게 정해진 크기 만큼 연속된 메모리 주소를 할당 받게 됩니다. 연속된 메모리 주소에는 데이터가 인덱스(index)라는 것을 갖게 됩니다. (array[0] 같은 식으로 배열에 접근할 때 대괄호 안에 숫자가 index 입니다)(JS기준) index를 갖게 된다는 것은 즉 임의 접근이 가능하다는 장점이 있는 거죠. 그러므로 접근과 탐색에 용이합니다. 하지만 크기를 미리 정해놓았기 때문에 수정하는 것이 불가능합니다. 또한 이미 크기를 정해 놓은 터라 해당 배열 크기 이상의 데이터를 저장할 수 없다는 단점이 있습니다.
   
   연결 리스트(Linked List)는 배열(Array)과 반대로 동적 자료구조 이며, 동적이다 보니 크기를 정할 필요가 없습니다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않습니다. 대신 노드(Node)라는 게 존재하며, 그 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있습니다. 위에서 말한 것처럼 크기를 정해 놓지 않았기 때문에 크기의 제한이 없습니다. 그로 인해 데이터 추가, 삭제가 자유롭다는 장점이 있습니다.

1. 해시테이블의 원리, 충돌 해소 전략에 대해 설명해주실 수 있을까요?
   해시 테이블은 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조 이다. 여기서 연관배열 구조란 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다. 해시 테이블은 키(key)가 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소(bucket)에 저장이 된다.
   
   • 해시함수(Hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
   
   • 해시(Hash) : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.
   
   충돌 해결 방법으로 체이닝(Chaining)이 있다. 체이닝이란(Chaining) 충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결리스트 형태로 저장하는 방법을 말한다.
   
   
   
2. 우선순위 큐의 시간복잡도는 어떻게 되며 그 이유는 무엇인지 설명해주실 수 있을까요?
   
   
   

• 기타
  1. 프로세스와 스레드를 비교하여 설명해주실 수 있을까요?
  2. 동기와 비동기를 비교하여 설명해주실 수 있을까요?