Stack & Queue
Stack
스택의 특징:
- 후입선출(LIFO : Last In FIrst out) 구조
- 단방향 입출력 - 데이터의 들어오는 방향과 나가는 방향이 같음
- 데이터를 하나씩만 넣고 뺌
Monotonic Stack(단조 스택)
→ 기본적인 스택 기능을 가지면서 모든 원소들이 오름차순(혹은 내림차순)을 유지하도록 한다.
쉽게 얘기해서 원소들은 특정 원소를 제거해서 정렬하는 방식
문제 1 : BOJ 10773 제로:
→ 가장 쉬운 문제
알고리즘 설명
- 정수 K를 입력 받는다.
- 입력 받은 값이 0일 경우
pop()
- 아닐 경우 push()
→ 스택을 쓰지 않고도 변수를 선언해서 계산이 가능함
문제 2 : BOJ 2494 탑:
→ 위에서 설명한 Monotonic Stack(단조 스택)
을 활용하면 문제가 편함.
알고리즘 설명
- 왼쪽부터 오른쪽 방향으로 세우고 왼쪽 방향으로 레이저를 발사한다.
- 가장 만나는 단 하나의 탑을 수신하는 것이니까 왼쪽에 있는 탑중 현재 자신의 값보다 큰 탑중 가장 가까운 탑이여야 함
- 그럼 스택에 있는 원소들이 이러한 규칙을 맞춘다면?
- 현재 탑의 크기보다 큼
- 오름차순으로 정렬됨(Top이 가장 가까운 큰 탑)
- 그렇게 된다면 어차피 큰 탑에 가로 막히고 왼쪽에 작은 탑들은 신경쓰지 않아도 된다.
문제 3: BOJ 3015 오아시스 재결합:
→ 문제를 풀면서 알아둬야 할 점들
- 현재 크기보다 작은 것이 나올 때 어떻게 해야할지
- height가 어떻게 연산을 해야할까.
- 스택이 비어있을 때는 어떤 경우고 비어있지않다면 어떤 경우인가.
- N은 최대 500,000이므로 첫째줄부터 50만이라고 치고 순서대로 나올 때 (1,2,3,~~500,000) → 등차수열의 합 (500000(500001) / 2)으로 오버플로우 생각해야 함
알고리즘 설명
- 키 순대로 정렬 했을 때 자신보다 큰 사람이 사이에 있다면 그 뒤에 있는 사람은 볼 수 없음
- 새로 들어온 입력 값이 스택의 top보다 크다면, top은 더 이상 들어오는 입력 값을 볼 수 없음(중간에 들어온 사람이 키가 커서 막히기 때문에) →
pop
→ 키가 같은 경우일 시 count 값을 누적 시켜줌(볼 수 있으니까)
- stack 작은 키 , 동일한 키에 대한 연산을 처리 한 후에도 스택에 값이 남아있다면 그 큰 사람이랑도 볼 수 있기 때문에 count 1 증가
Queue
큐의 특징:
- 선입선출(FIFO : First In FIrst Out) 구조
- 양방향 입출력 - 데이터의 들어오는 방향과 나가는 방향이 다르다
- 한 쪽은
프론트(Front)
로 정하여 삭제 연산만 수행한다. - 반대 쪽은
리어(rear)
로 정하여 삽입 연산만 수행한다.
문제 1: BOJ 10845 큐 :
→ 너무 기본적인 문제여서 설명 생략
문제 2: BOJ 2164 카드2:
→ 가볍게 큐로 풀 수 있음
알고리즘 설명
- front에서 제거, 제거 한 원소를 rear에다가 넣어줌
- queue의 사이즈가 1이 될 때까지 반복
Deque(덱)
→ Double Ended Queue의 줄임말로 큐의 양쪽에서 삽입과 삭제를 수행할 수 있는 자료구조
문제 1: BOJ 5430 AC:
→ 원래는 프론트 부분을 버림
알고리즘 설명
- 프론트 부분을 버리는 언어 AC에서 R을 입력하면 리어가 프론트로 변한다.
→ 플래그 함수 세워서 상황에 따라 다른 메서드 사용하기
문제 2: BOJ 11003 최솟값 찾기:
→ L사이즈 크기의 덱을 갖고 있다고 가정하고 생각하면 편함
알고리즘 설명
- Monotonic Stack과 비슷한 메커니즘으로 정렬된 덱이 있다고 생각하자.
- 덱안에는 뭐가 됐든 값을 넣으면서 value값이 더 크면
PollLast
혹은removeLast
해주고 오름차순이 유지 할 수 있도록 한다. - 그 후 첫번째 원소의 인덱스를 확인한다. i - L + 1보다 작으면 Valied한 원소가 아님으로
pollFirst
혹은removeFirst
를 해주어 덱의 크기가 L만큼(혹은 더 적게 유지) 할 수 있도록 한다.
'CS > 알고리즘' 카테고리의 다른 글
Dijkstra algorithm (0) | 2024.01.11 |
---|---|
Backtracking (1) | 2023.10.24 |
Priority Queue (1) | 2023.10.23 |