CS 문제 답변 정리
자료구조
-
좋아하는 자료구조가 있다면 이유와 함께 설명해주실 수 있을까요?
리스트- 많이 사용해본 자료구조 중 하나로 순서가 있어서 접근하기 쉽고 파이썬에 리스트를 적절히 이용할 수 있는 내장함수가 많아서 코테를 준비할 때도 많이 사용했어서 익숙해서
-
스택, 큐에 대해 설명해주실 수 있을까요?
스택: 데이터를 쌓아서 관리하는 방식. 마지막에 입력(push)된 데이터가 먼저 출력(pop)되는 특징을 가지는 데이터 구조. 이러한 관리 방식을 LIFO, FILO라고 함
큐: 데이터를 순서대로 관리하는 방식. 먼저 입력한 데이터가 먼저 출력되는 특징을 가지는 데이터 구조. 이러한 데이터 관리 방식을 LILO, FIFO라고 함
자바스크립트가 싱글 스레드 언어라서 한가지 일을 하면서 다른 일을 동시에 처리하는 것이 비동기… 오호..?
-
배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?
배열: 데이터를 빈틈없이 나열한 자료구조. 1,2,3 차원 배열이 있음. 링크드리스트에 비해 요소를 조회하는 속도가 빠름
링크드리스트: 데이터를 순서대로 나열한 자료구조. 포인터로 서로 연결되어있어 데이터가 서로 떨어져있어도 상관없음. 배열에 비해 삽입, 삭제가 용이함
-
해시테이블의 원리, 충돌 해소 전략에 대해 설명해주실 수 있을까요?
해시 테이블은 배열과 리스트를 조합한 자료구조. 특정 데이터의 해시값을 구해서 해당 데이터가 속한 그룹을 먼저 찾고 그룹의 리스트 안에서 데이터를 순서대로 검색해서 원하는 데이터를 조회함
삽입: 해시함수를 통해서 데이터를 해시값으로 변환하여 해당 해시값을 배열의 인덱스로 삼아 그 인덱스에 리스트에 데이터를 추가
검색: 해시함수를 통해서 데이터를 해시값으로 변환하여 해당 인덱스 안에서 데이터를 찾음
충돌: 많은 양의 데이터를 해시 테이블로 관리할 때 같은 배열 요소에 데이터가 여러 개 들어가게 되는 상태
충돌 해소 전략: 각 그룹이 여러개의 데이터를 관리할 수 있도록 만들어야 함 → 루트 배열의 각 요소가 리스트를 가리키도록 만들어서 해시값이 동일한 데이터를 여러 개 관리할 수 있음
-
우선순위 큐의 시간복잡도는 어떻게 되며 그 이유는 무엇인지 설명해주실 수 있을까요?
어떤 연산을 하는 데에 몇자례의 과정을 거치는지 그 횟수를 세는 방법으로 대략적인 시간 복잡도를 측정하고 빅오 표기법으로 나타냄
삽입: O(1) 자료의 맨 뒤에 자료가 삽입되는 동일한 연산이 반복 수행됨
삭제: O(1) 자료의 맨 앞에서 데이터가 삭제되는 동일한 연산이 반복 수행됨
검색: O(n) 자료를 검색할 때는 모든 요소들을 차례대로 겁색해야해서 O(n)의 시간복잡도를 가짐
우선순위 큐: 각 원소들이 우선순위를 가짐(우선 순위를 가진 데이터들을 저장하는 큐). 트리의 구조를 가짐. 최대 힙을 통해 구현함. 완전 이진트리(힙)
높은 우선 순위를 가진 원소가 먼저 처리됨
같은 우선순위를 가졌다면 큐는 선입 선출 순으로 처리됨
우선 순위 큐의 삽입과 삭제는 데이터 중 우선 순위가 가장 큰 데이터가 가장 위에 위치해야하기때문에 힙의 형태를 유지하기 위해서 원소(노드) 갯수가 n일 때 최대 높이만큼 자리 바꾸기가 반복되므로 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가짐
노드의 수가 n개일 때 완전 이진트리의 높이는 임
우선 순위 큐의 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도를 가짐
