CS면접 질문 - 자료구조

자료구조, 알고리즘

• 자료구조란 데이터를 원하는 목적과 규칙에 따라 저장하기 위한 구조이며 알고리즘이란 자료구조에 있는 데이터를 활용하여 어떠한 문제를 해결하는 방법이다.

스택, 큐, 트리, 힙

• 스택 : 후입선출의 구조를 가진 자료구조로 먼저 넣은 데이터가 맨 마지막에 나온다.

• 큐 : 선입선출의 구조를 가진 자료구조로 먼저 넣은 데이터가 맨 처음으로 나온다.

• 트리 : 정점과 간선을 이용해 사이클을 형성하지 않도록 만든 그래프의 특수한 형태

• 힙 : 최댓값, 최솟값을 쉽게 찾아내기 위해 고안된 완전 이진트리로 부모노드가 자식노드보다 항상 큰 값을 가지면 최대힙, 부모노드가 자식노드보다 항상 작은 값을 가질경우 최소힙이다.

• 우선순위 큐 : 우선순위 큐는 힙으로 구현된 큐로 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조이다.

해시테이블

• 해시테이블은 Key와 Value 형태로 데이터를 저장하는 자료구조 중 하나로 Key값에 해시함수를 적용하여 고유한 인덱스를 생성하고, 해당 인덱스에 value를 저장하는 형태이다.

• 해시테이블은 고유한 인덱스로 값을 조회하기 때문에 O(1)의 시간복잡도를 갖지만, Hash Collision이 발생한 경우 최대 O(n)까지 증가할 수 있다.

LinkedList, ArrayList

ArrayList

• 랜덤 Access로 데이터에 접근하며 시간복잡도는 O(1)이다.
• 리스트의 크기를 임의로 재조정하는 것은 많은 연산이 필요하다.
• 데이터의 추가, 삭제의 경우 임시 배열을 생성해 복제하는 연산을 거치기 때문에 O(n)의 시간복잡도가 필요하다.

LinkedList

• Sequencial Access(순차접근)으로 데이터를