알고리즘 스터디 과제 였던 백준의 11866번을 풀고 큐 개념을 강의에서 듣고 처음 적용해봐서 기억하고자 적으려 한다.
스택
스택(stack)이란 차곡차곡 쌓아 올린 형태의 자료구조 이다. 이에 따라 스택은 후입선출 방식을 따른다. 예시를 들어보면 쌓여있는 빨래더미를 생각하면 되는데, 빨래더니에서 맨 아래쪽을 빼는것은 굉장히 어렵다. 따라서 제일 마지막에 들어온것을 먼저 빼는 방식을 사용하는것이다. 그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow라고 한다. (우리가 자주 검색할때 사용하는 stackoverflow도 여기서 유래 되었다고 한다.)
스택 활용 예시
- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다. (컨트롤 z)
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
큐
큐는 스택과 반대의 개념으로 선입선출 방식을 따른다. 우리가 한정판 굿즈를 사러 갔다고 생각했을때, 맨 마지막에 온사람을 먼저 들여보내면 굉장히 불합리하다. 따라서 큐는 먼저 들어온 데이터를 먼저 빼는 방식인 데이터 자료 구조 이다.
큐의 특징
삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 연산작업만 수행한다. 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue), 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.
큐의 활용 예시
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
요세푸스 문제
아래의 문제는 반복문을 돌면서 가장 앞에 있는 데이터를 뺴야되는 로직으로 생각해 보았다.
반복을 돌면서 K번째가 아닐 경우, arr의 마지막에 data를 추가하고, k번째일경우 답안배열 ans에 push를 해준다.
