24.12.16 TIL

우선순위 큐

• 우선순위 큐란?
  • 일반 큐와 다르게 선입선출이 아닌 우선순위에 따라 나가는 순서가 다른 큐
• 특징
  • 우선순위 기반 처리
  • 힙 구조 사용
  • 힙을 사용하여 구현할 경우, 삽입 삭제 연산의 시간 복잡도는 O(logN)
• 구현
  • 최대 힙, 최소 힙 등이 있다
• 핵심 함수
  • Insert : 우선순위에 맞게 삽입
  • Delete : 우선순위가 가장 큰 요소 삭제
  • Peek : 우선순위가 가장 큰 요소 반환하고 삭제는 하지 않음
• 사용
  • 게임
    • 여러 이벤트 처리 : 우선적으로 처리되야 하는 이벤트들을 판단하여 처리할 수 있게 해준다
    • AI 행동 : AI가 다음 행동을 할 때 우선적으로 해야되는 행동을 하게 할 수 있다
    • 애니메이션 : 우선순위가 높은 애니메이션을 먼저 출력할 수 있게 할 수 있다
  • 알고리즘
    • A* : 출발 지점부터 도착 지점까지 최단 거리를 구할 때 사용 가능
    • 다익스트라 : 최단거리 알고리즘에서 다음에 어떤 노드를 방문할지 판단할 때 사용

코딩 태스트 기초 개념

• 시간 복잡도
  • 프로그램에서 가장 중요한 로직이 실행되는대 걸리는 시간
• 공간복잡도
  • 입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양
  • 코태에서 잘 사용하지 않음
• 누적합
  • 배열들의 요소를 더해 새로운 배열을 만들어 사용할 수 있게하는 알고리즘
• 구현
  • 문제를 그대로 단순 구현하는 알고리즘