[기술면접] CS 기술면접 - 자료구조

공부한 것을 바탕으로 정리하는 것이지만 잘못된 부분이 있을 수 있습니다. 오류는 댓글로 알려주시면 감사하겠습니다!

 

자료구조란?

• 데이터를 원하는 규칙 혹은 목적에 맞게 저장하는 구조

알고리즘이란?

• 자료구조에 쌓인 데이터를 활용해 문제 해결을 위한 동작들 모임

스택, 큐, 트리, 힙 구조 설명

• 스택 : 세로로 된 바구니 구조, 먼저 넣은 자료가 가장 마지막에 나오는 First In, Last Out (FILO) 구조를 가짐
• 큐 : 가로로 된 통 같은 구조, 먼저 넣은 자료가 가장 먼저 나오는 First In, First Out (FIFO) 구조를 가짐

스택, 큐 구조 비교

• 트리 : 정점, 간선 (노드, 링크) 을 이용해 사이클을 이루지 않도록 구상한 Graph 특수형태로 계층이 있는 데이터를 표현하기에 적합함
• 힙 : 완전이진트리로, 최대값 혹은 최솟값을 찾는 연산을 쉽게 하려고 고안한 구조
  • 부모노드값 > 자식노드값 이면 최대힙구조, 부모노드값 < 자식노드값 이면 최소힙구조

 

ArrayList VS LinkedList

ArrayList

• 데이터들이 순서대로 늘어선 배열 형태
• 원하는 데이터 무작위 접근 가능 (접근 시간 상대적으로 빠름)
• 데이터 추가 혹은 삭제시, 임시배열 생성 후 복제하는 과정을 거치기에 상대적으로 시간이 오래 걸림 (비효율적 메모리 사용)
• 하지만 순차적 추가, 삭제시에는 더 빠름

LinkedList

• 자료의 주소값으로 서로 연결된 형태
• 무작위 접근이 불가 (징검다리처럼 하나씩 이동), 순차접근만 가능 (접근 시간 상대적으로 느림)
• 데이터 추가를 위해 새로운 노드만 생성하면 되기에 중간에 데이터 추가 혹은 삭제시 상대적으로 빠른 속도

LinkedList, ArrayList 비교

Queue, Stack 구현하는 방법

• 큐 : 삽입, 삭제 용이한 LinkedList가 적합 (ArrayList일경우 poll() 후 데이터를 앞당겨야 하는 과정을 거쳐야함)
• 스택 : ArrayList가 더 적합 (데이터 삭제시 삭제하는 과정을 거칠 필요 없이 index 줄이고 초기화하기에 더 간단함)

 

알고 있는 알고리즘에 대해 설명해주세요.

• 정렬 관련 알고리즘에 대해서 알고 가면 좋다. 주로 퀵정렬에 대해 물어보는 경우가 많다고 한다.