19.1 도입
큐 -- 한쪽으로 정보를 저장하고 다른 한쪽에서 정보를 꺼내는 (선입선출 FIFO) 스택 -- 한쪽으로 정보를 저장, 출력하는 (후입 선출 LIFO)
데크-- 양쪽에서 저장,출력을 하는
19.2 큐와 스택, 데크의 구현
연결리스트를 통한 구현-- 구현하기에는 가장 간단
그러나 포인터를 통해 이동하는데 시간이 걸려 가장 효율적이지는 않다!
동적배열을 이용한 구현 -- 스택의 경우에는 Vector를 이용해서 쉽게 구현 가능 (--> 한쪽으로만 저장, 출력하기 때문)
그러나 큐와 데크(덱)같은 경우는 앞부분에서도 저장 또는 출력이 일어나기에 모든 변수를 이동해야 할 수도 있음!
---> 그래서 동적배열을 이용해서 큐와 덱을 구현할 때는 첫 번째 원소를 head, 마지막 원소를 tail로 유지하고
원소 전체를 옮기는 대신 head이나 tail의 위치를 이동 시킵니다.
그러나... 이런 방법은 공간 낭비가 심하다...
--> 환형 버퍼 --> 원형 큐..? 인 것 같네요
19.3 스택과 큐의 활용
예제 문제 1. 큐를 이용한 조세푸스 문제
18장에서 풀었던 방법 --> 연결 리스트로 구성하여 죽을 사람을 가리키는 포인터를 옮김
여기서 풀방 법--> 하나의 큐에 모든 사람을 넣고 맨 앞의 사람을 한 명 한명 꺼내서 죽을 사람이면 없애고 안 죽을 사람이면 맨뒤로 보내는 작업을 두 명이 남을 때까지 반복
--> 큐를 사용해도 연결 리스트로 구현할 테지만 구현이 간단해짐!
예제 문제 2. 스택을 이용한 울타리 자르기
7장에서 풀었던 방법--> 이분법, 분할 정복을 통해 해결!
여기서 풀 방법--> 15장의 스위핑 알고리증 + 스택
스위핑 : 한쪽에서 다른 한쪽까지 훑어보기
1. 한쪽에서 탐색 시작 판자 스택에 추가
2. 스택에 들어 있는 판자와 현재 판자와의 높이 비교
--> 높으면 크기만 따로 저장
--> 낮으면 스택에 추가
3. 크기 비교 후 가장 큰 값 출력
여기까지가 19장
'공부공부 > 알고리즘!' 카테고리의 다른 글
알고스팟(algospot) 21 장 트리의 구현과 순회 (0) | 2022.05.15 |
---|---|
알고스팟(algospot) 20장 문자열 (0) | 2022.05.15 |
알고스팟(algospot) 15장 계산 기하 (0) | 2022.05.08 |
알고스팟 (algospot) 9장 동적계획법 테크닉 (0) | 2022.05.08 |
최소신장트리!(프림과 크루스칼) (0) | 2022.03.04 |
댓글