자료구조 & 알고리즘 면접 요약 노트 - 1

Q1. 스택과 큐에 대해 설명해주세요 A1. 스택은 LIFO 구조이며, 큐는 FIFO 구조입니다. LIFO 구조는 마지막에 들어온 데이터가 가장 먼저 나오는 구조입니다 FIFO 구조는 처음에 들어온 데이터가 가장 먼저 나오는 구조입니다 Q2. 배열과 링크드 리스트의 차이점에 대해서 설명해주세요 A2. 배열과 링크드리스트에서 가장 큰 차이점을 보이는 부분은 검색과 삽입/삭제 연산입니다 검색에선 배열은 인덱스를 통해 바로 찾을 수 있으므로 O(1)의 시간복잡도를 가집니다. 그러나 링크드리스트는 찾는 노드까지 순차적으로 찾아 들어가야하므로 O(n)의 시간복잡도를 가집니다. 삽입/삭제에선 배열은 메모리 위치가 연속적이고 고정되어 있기 때문에 많은 시간이 소요되는 반면 링크드리스트는 삭제 시 이전 노드의 메모리 ..