ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • [크래프톤 정글] TIL 9일차 큐(Queue)
      카테고리 없음 2024. 9. 10. 21:57
        • 큐? 큐대? 그거 왜 쓰는데
        • 데이터를 순차적으로 처리하기 위해
        • 멀티태스킹 및 CPU 스케줄링
          • 운영체제에서 프로세스 스케줄링을 할 때, CPU는 여러 작업을 처리한다. 이 때 큐를 사용해 프로세스를 효율적으로 관리하며, 먼저 들어온 프로세스가 먼저 처리된다.
        • 데이터 스트림 처리
          • 실시간 데이터가 연속적으로 들어오는 경우, 데이터를 순서대로 처리해야 할 때, 큐를 사용.
            • ex. 네트워크 패킷을 처리하거나 메시지 큐에서 데이터를 관리할 때 사용.
        • BFS 알고리즘
          • 그래프 탐색 알고리즘 중 하나인 BFS 에서 노드를 탐색할 때, Queue 가 필수적이다. 탐색해야 할 노드를 순서대로 저장하고 처리하기 떄문이다.
        • 대기열 관리
          • 대기열이 필요한 고객 서비스나 병원 진료 시스템 처럼, 사람들을 먼저 온 순서대로 처리 하기 위해.큐 (Queue)
        • 선입선출(FIFO)의 자료구조로 대기열이라고도 한다.
        • 인큐(enqueue) :큐에 데이터 추가하는 작업
          • 접두사 en 은 ~하게 하다.
        • 디큐 (dequeue) : 데이터를 꺼내는 작업
          • 접두사 de는 분리, 제거, 떨어진,.. 등
        • 프런트(front) : 데이터를 꺼내는 쪽
        • 리어(rear)혹은(back) : 데이터를 넣는 쪽
      • Queue 의 이러한 특성 덕분에 순서 보장, 효율적인 메모리 사용, 간단한 구현 등 여러 장점이 있다.
      • 큐의 특징
        • FIFO
        • 2개의 입출력 방향이 있다.
          • enqueue시 큐의 맨 끝, dequeue시 큐의 맨 앞.
        • 데이터는 하나씩 입출력
          • queue
      • 큐의 실사용 예제
        • 야구 경기를 보기 위해 매표소에 가장 먼저 줄을 선 사람(First In)이 가장 먼저 표를 구매하고 가장 먼저 매표소를 빠져나갈 것(First Out)
      • Buffer (완충기억기)
        • 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역.
        • 컴퓨터 장치들(ex. 키보드, 프린터,..) 사이에서 data를 주고 받을 때, 각 장치 사이에서 존재하는 속도 차이나 시간 차이를 극복 하기 위해 임시 기억 장치의 자료구조로 Queue 를 사용한다.
          • 키보드 누른 뒤 마우스 클릭 했는 데, 마우스가 먼저 작동한다면 당황잼민이
        • 즉, 속도 차가 큰 두 대상이 입출력을 수행할 때 효율성을 위해 사용하는 임시 공간
      • Buffer의 예시
        • 유튜브 영상 재생 시 아직 보지 않은 부분의 회색 재생바가 늘어나는 것이 Queue 에 영상 데이터를 일시적으로 모아두는 것이다.
        • 데이터를 다운 받는 것이 CPU 처리 속도보다 느리기 때문에, CPU가 다른 작업을 처리할 동안 미리 Queue 에 영상 데이터를 다운 받아 놓고 데이터가 어느 정도 쌓이면 CPU가 재생을 시작함
        • 이 때, 재생 중 중 재생 속도보다 데이터의 다운로드 속도가 느리면 영상이 끊기는 buffering 이 발생함.
        • 프린트로 예를 들자면,
        • 프린터가 인쇄하는 속도보다 CPU 가 빠르기 때문에, CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음, 인쇄 작업 Queue 에 저장하고 다른 작업을 수행함.
        • 프린터는 인쇄 작업 Queue 에서 데이터를 받아, 들어온 순서대로 일정한 속도로 인쇄함.
        • 엥? ‘큐’가 아니라 ‘버퍼’에 저장하는 거 아닌가요?
          • FIFO 방식 사용 시 버퍼는 큐와 같은 방식으로 작동하기 때문입니다, 하지만 정확히 둘은 같은 것이 아니므로, 사용하는 맥락에 따라 구분해서 사용하자.
      • 큐의 종류를 보기 전에…
      • 일반적으로 배열의 특성상 용량(capcity)는 이미 정해져 있다.
      • 배열로 구현한 큐의 삽입, 삭제에 대해 생각해보죠.
      • 삽입과 삭제가 이루어진 후 배열의 상태를 어떻게 처리할까?
      • 용량이 5이고 이미 데이터가 1, 2, 3, 4 들어있는 배열을 생각해보자.
        • 지금 구현한 큐는 삽입, 삭제가 이루어질 때마다 실제 용량이 줄어드는 것을 알 수 있다.
      • 해결 방법
      • 선형큐(linear queue)
        • dequeue할 때마다 2번째 이후의 모든 원소를 같이 앞쪽으로 옮기는 것.
        •  
        • 프로그램의 효율성
          • 이 때, Queue 효율성은 어떨까요?
          • dequeue 를 한번 할 떄마다 처리의 복잡도는 O(n)
          • 데이터를 꺼낼 때마다, 이런 처리 작업을 수행해야 한다면 프로그램의 효율성을 기대할 순 없을 것.
      • 원형 큐(링 버퍼로 큐 구현)
        • 큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞 부분이 비게 된다는 점을 활용해서 ‘배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐.’
        • 원소의 앞 뒤를 식별하는 변수 front와 rear 이 있다.
          • 여기서 프런트와 리어는 논리적인 데이터 순서일 뿐 배열의 물리적 원소의 순서는 아니다.

          • enqueue 와 dequeue 의 모든 처리 복잡도는 O(1) 을 갖는다.
      • Linked list 을 사용해 구현한 큐
        • 배열 대신 연결 리스트로 구현하면, 요소를 제거하거나 추가할 때, 다른 원소들을 옮길 필요가 없다.
        • dequeue 시에 첫 번째 노드를 제거하고, 새로운 데이터를 삽입할 때는 맨 뒤에(rear) 에 노드를 추가하면 된다.
        • 메모리를 더 유연하게 사용할 수 있고, 데이터 이동의 부담이 없다.
      • 우선순위 큐
        •  
        • inqueue 할 때는 데이터에 우선순위를 부여하여 추가하고, dequeue 할 때는 우선순위가 가장 높은 데이터를 꺼내는 방식.
        • c.f) 파이썬에서 우선순위를 부여하는 큐는 heapq 모듈에서 제공한다. (Do it 6장 참고)
      • 이중 끝 큐 (Deque, Double-Ended Queue)
        • 양쪽 끝에서 모두 삽입과 삭제가 가능한 자료구조.
        • input-restricted Deque : 한쪽 끝에서만 삽입이 가능하고, 양쪽에서 삭제가 가능함.
        • Qutput-restriced Deqeue : 양쪽에서 삽입이 가능하고, 한쪽 끝에서만 삭제가 가능함.
        • FIFO 특성을 어기는 데 큐라고 볼 수 있나?
          • 입력과 출력 방식에 따라 FIFO 가 될 수도 있고, LIFO 가 될 수도 있다.
          • 스택 + 큐
        • Deque 는 FIFO에 제한되지 않는다. 따라서 더 유연한 자료구조라고 볼 수 있다.

      참고한 사이트

      저작자표시
    Designed by Tistory.

    티스토리툴바