경일 메타버스 20220624 12주차 4일 수업내용. 자료구조와 알고리즘-큐, 오답노트

자료

https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit

큐

• 리스트의 일종으로, 스택처럼 연산이 한 쪽 끝에서만 이뤄지는 자료구조.
  컨테이너 어댑터

• FIFO(First-In First-Out)구조 :
  가장 처음에 들어간 데이터가 처음에 나온다.

• 큐에서 삽입이 일어나는 쪽을 뒤(Rear), 삭제가 일어나는 쪽을 앞(Front)라고 한다.

• 프린트 큐 / CPU 스케줄링 / 데이터 버퍼 / BFS 등에 사용된다.

• STL 상의 구현

  • std::queue :
    https://en.cppreference.com/w/cpp/container/queue

  • std::deque :
    https://en.cppreference.com/w/cpp/container/deque

• std::queue의 사용

  2022. 06. 24 std::queue의 사용 예시 코드

• std::deque

• Double-ended Queue.
  양 끝에서 데이터 삽입 및 삭제가 가능한 자료구조.
  컨테이너 어댑터가 아니다.

• 선형 리스트와 연결 리스트를 조합한 청크 리스트(Chunk List)라는 것으로 구현되어 있다.

  • 청크 리스트(Chunk List)
    관련 논문 :
    https://arxiv.org/ftp/arxiv/papers/2101/2101.00172.pdf

  • 각각의 특징을 모두 모아서 연산이 매우 효율적이다.

    • 모든 컨테이너 어댑터의 기본 자료구조로 사용되고 있다.

    • 원형 큐 : 영상 1시간 부근

  • std::deque의 사용

    • 컨테이너 어댑터가 아니기에 중간 삽입, 순회도 지원한다.

      2022. 06. 24 std::deque의 사용 예시 코드

백준 풀이

• 오답노트 : 백준 11051

  • 백준 11051 이항 계수2
    큰 수로 인한 타입 오버, 재귀함수 사용으로 인한 시간초과 등 여러 문제가 생겼지만 동적 계획법과 파스칼의 삼각형을 사용하여 해결.
    다른 큰 수의 이항 계수에도 응용 가능.
    다른 사람들의 알고리즘도 볼 것.

  • 11866, 18258, 1021 코드 주석 확인하고 다른 방식으로도 풀어볼 것.

• 예습 : Node.js, NFT 교재를 읽어볼 것.