[알고리즘] 용어, 우선순위 큐, 트리

 

• 복잡도 - 알고리즘 성능 척도
  복잡도가 낮아야 좋음
• 시간복잡도
  높다는건 수행시간이 길다
• 공간복잡도
  높다는건 메모리를 많이 잡아먹는다
  
  
• 빅오 표기법
  가장 빠르게 증가하는 항만을 고려함

 

우선순위 큐

• 큐 : 먼저 들어온 데이터가 먼저 나가는 자료구조
• 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 일반적인 구현법 : 힙을 이용
  • 힙 : 우선순위 큐를 위해 고안된 완전 이진트리 형태의 자료 구조
  • 완전 이진트리
    • 왼쪽부터 차례대로 삽입하는 트리
    • 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있음
  • 최소힙 (루트노드가 가장 작은 값) - 오름차순 이용할때
  • 최대힙 (루트노드가 가장 큰 값)

 

 

 

 

트리

• 트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조임
• 기본적으로 트리의 크기가 N이면, 전체 간선의 개수는 N-1개이다

트리관련용어

• 루트노드 : 부모가 없는 최상위 노드
• 단말노드 : 자식이 없는 노드
• 크기 : 트리에 포함된 모든 노드의 개수
• 깊이 : 루트 노드부터의 거리
• 높이 : 깊이 중 최댓값
• 차수 : 각 노드의 (자식방향) 간선 갯수

 

이진탐색트리

• 이진탐색이 동작할수있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종
• 왼쪽자식노드 < 부모노드 < 오른쪽 자식노드

 

트리의 순회

• 트리자료구조에 포함된 노드를 특정한 방법으로 한번씩 방문하는 방법
• 전위 순회: 루트를 먼저 방문한다
• 중위 순회: 왼쪽자식을 방문한 뒤에 루트를 방문한다
• 후위 순회: 오른쪽 자식을 방문한 뒤에 루트를 방문한다

 

 

 

 

 

 

참고

나동빈 - 이것이 취업을 위한 코딩테스트다