devbelly

문제 https://www.acmicpc.net/problem/5849 알고리즘 stack 풀이 inversion을 만들지 않는 소의 개수를 구하는 문제입니다. $a_i$를 u, $b_i$를 v라고 하겠습니다. inversion을 만들지 않기 위해서는 u를 기준으로 정렬했을 때, v가 오름차순의 형태를 가져야만합니다. 오름차순을 유지하기 위해 스택을 사용해서 문제를 풀면 됩니다. 스택의 top이 현재 보고 있는 소의 v보다 크다면 이는 inversion을 만들기 때문에 계속 pop을 해주고, 지금까지 확인한 v값들보다 현재 v값이 작다면 현재 v는 inversion을 만들지 않으므로 스택에 push 해주면 됩니다. 아래 코드는 이 해설과는 다른 코드입니다. 풀이만 참고하세요. 코드 #include #de..

문제 www.acmicpc.net/problem/3015 알고리즘 stack 풀이 $N$명이 사람이 서있을 때, 서로 볼 수 있는 쌍을 구하는 문제입니다. 서로 보기 위해선 각 사람 사이에 그 사람들보다 큰 키가 존재해서는 안됩니다. 문제의 단순화를 위해 모든 키가 유니크하다고 가정하겠습니다. 파악해야할 것은 키의 구간이 내림차순으로 존재한다면 해당 구간은 추후에 매칭이 될 가능성이 있는 사람들입니다. 아래 그림은 이에 대한 예시로써, 흰색사람의 키가 내림차순인 형태입니다. 이후에 나오는 주황색 사각형과 흰색 사각형들이 매칭이 됩니다. 또한 빨간색 사각형처럼 자신의 왼쪽에 있는 사람이 자신보다 키가 크다면 무슨일이 있어도 주황색 사각형의 왼쪽부분과는 매칭이 될 수 없습니다. 이러한 특징을 파악해 오름차순..