[CS 면접질문 대비] 그래프 및 자료 구조

[그래프와 트리의 차이]

	그래프	트리
정의	노드(node)와 그 노드를 연결하는 간선(edge)를 하나로 모아놓은 자료 구조	그래프의 한 종류 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류
방향성	방향 그래프(Diredctd) 무방향 그래프(Undirected) 모두 존재	방향 그래프(Directed Graph)
사이클	사이클(Cycle) 가능 자체 간선(self-loop)도 가능 순환 그래프(Cyclic), 비순환 그래프(Acyclic) 모두 존재	사이클(Cycle) 불가능 자체 간선(Self-loop) 불가능, 비순환 그래프(Acyclic Graph)
루트 노드	루트 노드 개념이 없음	한 개의 루트 노드만이 존재, 모든 자식 노드는 한 개의 부모 노드만을 가짐
부모 -자식	부모-자식의 개념이 없음	부모-자식 관계 top-bottm 또는 botton-top으로 이루어짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS 안의 Pre-, In-, Post- order
간선의 수	그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음	노드가 N인 트리는 항상 N-1의 간선을 가짐
경로	-	임의의 두 노드 간의 경로는 유일
예시 및 종류	지도, 시작점에서 목적지까지 최단 경로	이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙)

 

참고

 

1. Pre Order
   
   1. 노드 방문
   2. 왼쪽 서브 트리 방문
   3. 오른쪽 서브 트리 방문
2. In Order
   1. 왼쪽 서브 트리 방문
   2. 노드 방문
   3. 오른쪽 서브 트리 방문
3. Post Order
   1. 왼쪽 서브 트리 방문
   2. 오른쪽 서브 트리 방문
   3. 노드 방문

 

 

[면접 질문]

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

• 스택
  • 먼저 넣게 되는 자료가 마지막에 나오는 First in Last Out(FILO) 구조이다.
  • top에서 push, pop하면서 삽입 삭제 이루어짐.
  • DFS나 역추적을 해야 할 때(ex. 문서 작업시 실행 취소) 때 사용.
• 큐
  • 먼저 넣게 되는 자료가 먼저 나오는 First in First Out(FIFO) 구조이다.
  • 한 쪽 끝에서 삽입하고, 다른 쪽 끝에서 삭제함.
  • 주로 데이터가 시간순대로 진행되야 할 때 사용함. BFS에서 사용.
• 트리
  • 정점과 간선을 이용해 사이클을 이루지 않도록 구현한 Graph의 특수 형태
  • 계층이 있는 데이터를 표현하기에 적합함
• 힙
  • 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조
  • 완전이진트리로 구성: 모든 레벨의 노드가 전부 채워져 있는 구조. 부모 키값이 자식들 키값보다 작지 않거나(최대힙), 키값이 크지 않는(최소힙) 트리. 

힙

- LinkedList와 ArrayList의 차이 

ArrayList는 데이터들이 순서대로 늘어선 배열의 형식을 취하지만, LinkedList는 자료의 주소값으로 서로 연결된 형식을 가지고 있다.

 

ArrayList

• 특정 요소에 접근하는 시간 복잡도: O(1) - Random Access 지원
• 삽입과 삭제 시간 복잡도: O(N) - 순차적으로 검색
• 저장방식이 원소들이 메모리에 연이어 저장됨
• 리스트의 크기가 제한되어 있어, 크기 재조정 시 많은 시간 걸림
• 선언 시 메모리가 컴파일 타임에 할당됨(정적 메모리 할당)
• Stack 세션에 메모리가 할당됨

- 순차적으로 검색

 

LinkedList

• 특정 요소에 접근할 때 시간 복잡도: O(N) - 순차적으로 검색 
• 삽입과 삭제 시간 복잡도: O(1)
• LinkedList에서 원소를 추가할 때 기존 원소의 앞, 뒤에 추가 가능
• 리스트 크기에 영향 없이 데이터를 추가할 수 있다.
• 선인 시 메모리가 런타임에 할당됨 (동적 메모리 할당)
• Heap 섹션에 메모리가 할당됨

 

---

References

gmlwjd9405.github.io/2018/08/13/data-structure-graph.html