[직무인터뷰] 자료구조 이야기

Stack and Queue가 뭔가?

스택은  LIFO(Last in First Out) 형식의 자료구조고, 큐는 FIFO(First In First Out)형식의 자료구조다.

만약 스택에 데이터가 하나도 없는데 pop을 하면 어떻게 되는가? 즉, 비어있는 스택을 참조하면 무슨 일이 일어날까?

비어 있는 스택에서 데이터를 pop하면 Stack Overflow가 발생한다.

스택 오버플로우는 언제 발생하는가

• 비어 있는 스택에서 pop할 때
• 스택의 최대 사이즈를 넘겼을 때
• 재귀함수를 무한 호출하거나 너무 큰 지역변수 혹은 매개변수를 사용할 때

~와 같은 상황이면 스택/큐 중에 뭘 쓰는게 나은가?

• 스택의 활용
  웹 브라우저 방문기록, 역순 문자열 만들기, 수식의 괄호 검사*, 메모리의 스택영역*
• 큐의 활용
  우선순위가 같은 작업을 예약할 때(먼저 온 순서로 처리하니까), 스케줄링 기법에서의 활용, BFS에서의 활용

그래프, 트리, 힙을 비교하라

• 그래프
  
  • 노드와 엣지로 구성되어 있다.
  • 트리는 방향성이 있지만 그래프는 방향성이 존재할 수도 있고 존재하지 않을 수도 있다.
  • 트리는 루트노드가 있지만 그래프는 방향성이 확실하지 않다보니 루트노드의 개념이 없다.
  • 트리는 부모 자식 개념이 있지만 그래프는 그런 개념이 없다.
  • 활용 예시
    • DFS는 모든 노드를 방문하고 싶을 때 사용하고, BFS는 두 노드 간의 최단 경로나 임의의 경로를 탐색할 때 사용한다.
    • 도로 길찾기(간선의 weight을 숙지해서 구현), 지하철 노선도 등
• 트리
  • 사이클이 없고 방향성이 있는 그래프
  • Root, Parent, Child, Sibling, Leaf Node, Level
    • 루트노드 : 부모가 없는 노드
    • 리프노드 : 자식이 없는 노드
    • 형제 : 같은 부모를 가진 노드
    • 레벨 : 트리의 특정 깊이를 가지는 노드의 집합

    • 

  • 종류로는 Binary Tree, Binary Heap(Min Heap, Max Heap), Binary Search Tree 등이 있다.
    • Binary Tree : 자식 노드를 2개만 갖는 트리
    • Binay Search Tree : [모든 왼쪽 자식들 <= N < 모든 오른쪽 자식들]이 성립하는 트리
      • 사전탐색, up-down 게임이 이진 검색 트리의 개념과 같다.
• 힙
  • 완전이진트리(왼쪽 자식부터 차례대로 채워진 트리)의 일종으로 우선순위 큐를 구현하기 위해 만들어진 자료구조
    • 우선순위 큐는 OS의 스케줄링에서 사용한다.
  • min heap은 부모노드가 모든 자식노드보다 작은 트리, max는 반대.

단어가 1000개 있는 사전에서 특정 단어를 찾으려고 하면 최대 몇 번만에 탐색이 가능한가?

log1000이면 2의 10승이 1024니까 10번 안에 탐색이 가능하다.

그러면 단어가 1000개가 있는데 사전순이 아니라 랜덤이라면 특정 단어를 찾는 데 얼마나 걸릴 것 같은가?

이 경우는 선형 탐색이어야 하니까 O(N)이다. 하지만 여기서 중요한게, 이걸 정렬한 다음에 이분탐색을 하겠습니다! 라고 말하면 틀린 것이다. 정렬이 무조건 N보다 크게 걸리기 때문에.

왜 하필 힙이 우선순위큐를 구현할 때 사용되는가?

만일 배열로 구현한다고 하면 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 바로 이용하면 되니 어렵지 않다. 하지만 우선순위가 중간인 것을 배열에 삽입할 때 모든 데이터의 인덱스를 뒤로 밀어야 한다.

 

연결리스트로 구현한다면 이것도 우선순위가 높은 걸 반환하기는 쉬우나, 삽입과정이 오래 걸린다. 최악의 경우로 맨 끝까지 탐색을 하게 된다면 삭제는 O(1)이지만 삽입은 O(N)이다.

 

힙으로 구현한다면 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다. 즉, 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 개수가 2배 증가하고, 비교 연산 횟수는 1회 증가한다. 따라서 삭제나 삽입 모두 최악의 경우에 O(log2N)이다. 삭제는 좀 더 오래걸려도 삽입의 시간 효율이 훨씬 월등하므로 힙을 사용한다.

 

 

정렬 알고리즘과 해시테이블을 추가할 예정이다.