선장 일지

monotone stack

monotone stack은 특정 index에서 주변을 탐색하며 개수를 구해줄 때 특정상황에서 O(n)으로의 시간복잡도로 줄여주는 알고리즘 입니

다.

사용 방법

stack의 원소들을 오름차순 or 내림차순 상태로 유지시키는 방법입니다. 

예시

1 3 10 50 20 16 19 49 30이 있다고 가정해봅시다. 오름차순으로 stack에 넣으려고 합니다.

1 3 10 50 까지는 오름차순이기 때문에 pop 과정이 없지만, 20을 넣는 순간 오름차순이 깨지기 때문에 pop과정이 발생합니다.

1 3 10 50 20이 되고 모든 데이터를 넣으면  3 10 50 20 16 19 49 30 으로 3 10 16 19 30만 남아 있는 상태가 됩니다.

사용 이유 

이렇게 스택의 원소를 정렬하면, 특정 index 보다 왼쪽에 있는 값 중에서 처음으로 나오는 특정 index 미만의 수의 값을 바로 알 수 있습니다.

관련한 문제

문제를 풀어보면 모든 위치에서 오른쪽으로 볼 수 있는 정원의 개수를 구하는 문제입니다. 문제의 설명대로 구현한다면 최악의 경우 O(n^2)의 시간복잡도로 풀어야 정확하게 풀 수 있습니다. 하지만, monotone stack을 사용한다면 O(n)의 시간복잡도로 풀어낼 수 있습니다. 고민해보며 풀어보고 생각이 나지 않는다면 아래의 풀이 방법을 이해해보세요.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);

        int n = in.nextInt();
        Stack<Integer> s = new Stack<>();
        long answer = 0;
        for(int i = 0; i < n; i++) {
            int building = in.nextInt();

            while(!s.isEmpty()) {
                if(s.peek() > building) break;

                s.pop();
            }
            answer += s.size();
            s.push(building);
        }
        System.out.println(answer);
    }
}

AVL 트리는 스스로 균형을 잡는 이진 탐색 트리로 일반적인 이진 탐색 트리의 최악의 경우를 보완하기 위해 만들어진 트리입니다. 모든 노드에 대해서 노드의 왼쪽 자식 노드와, 오른쪽 자식 노드의 높이 차이가 1이하인 이진탐색트리입니다.

AVL 트리는 어떤 시점에서 왼쪽 자식의 노드와 오른쪽 자식 노드의 높이 차이가 1보다 커지면 AVL 트리 속성을 유지하기 위해 스스로 균형을 잡습니다.

AVL 트리의 검색, 삽입, 삭제는 평균과 최약의 경우 모두 O(log N)의 시간복잡도가 걸립니다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있습니다.

AVL 트리의 속성을 유지하기 위해 4가지(LL, RR, LR, RL)의 문제가 발생했을 때 균형을 잡기위해 트리를 회전합니다. 예시와 해결 방법은 아래와 같습니다.

LL 문제

• 왼쪽으로 노드가 쏠리는 문제입니다.  (부모노드의 균형도가 양수)

해결 방법: 부모노드를 좌측 자식 노드의 우측 자식 노드로, 좌측 자식 노드의 우측 노드를 부모노드의 좌측 자식 노드로 연결합니다.

RR 문제

• 오른쪽으로 노드가 쏠리는 문제입니다.  (부모노드의 균형도가 음수)

해결 방법: 부모 노드를 우측 자식 노드의 좌측 자식노드로 연결하고, 우측 자식의 좌측 노드를 부모노드의 우측 자식노드로 연결합니다.

LR 문제

• 부모 노드 균형 2, 좌측 자식 노드 균형이 -1인 경우

해결 방법

RL 문제

• 부모 노드 균형 -2, 오른 자식 노드 균형이 1인 경우

해결 방법: 위의 LR 문제 해결 방법의 순서를 반대로 LL 문제 해결과 동일하게 해준 뒤, RR 문제 해결방식으로 해결해주면 됩니다.