겜돌이의 개발일지

문제 백준 3015 오아시스 재결합 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 N = 500,000이므로 O(N^2)으로 푸는 것은 불가능하다. 따라서 Monotonic Stack을 활용한다. Monotonic Stack [알고리즘] Monotonic Stack 개요 자신보다 큰 값(혹은 작은 값)이 언제 처음 오는지에 대해 구해야 할 때, 가장 쉽게 떠올릴 수 있는 방법은 2중 for 문을 쓰는 것이다. 예를 들어 다음과 같이 숫자가 있다고 할 때 3 4 1 5 2 각 ga..

개요 자신보다 큰 값(혹은 작은 값)이 언제 처음 오는지에 대해 구해야 할 때, 가장 쉽게 떠올릴 수 있는 방법은 2중 for 문을 쓰는 것이다. 예를 들어 다음과 같이 숫자가 있다고 할 때 3 4 1 5 2 각각의 숫자에 대해 그 수보다 큰 수가 처음 등장하는 인덱스(0부터 시작)를 나타내면 다음과 같다. num : 3(1) 4(3) 1(3) 5(x) 2(x) 2중 포문을 사용하게 되면, n개의 원소에 대해 시간 복잡도는 O(n^2)이다. 이를 스택을 사용하면 한 번만 순회를 돌면서, 즉 O(n)만에 자신보다 큰 인덱스를 찾을 수 있다. Monotonic Stack monotonic stack의 원리는 간단하다. stack에 들어있는 원소가 내림차순(혹은 오름차순)이 되게 정리만 해주면 된다. 1. 즉..

문제 백준 17299 오등큰수 C++ 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 오큰수 문제와 크게 다를 건 없다. 비교하는 방식만 몇번 나왔는지 횟수를 저장하고 있는 cnt 배열을 비교하는 것으로 바꿔주면 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5..

문제 백준 17298 오큰수 C++ 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 스택을 활용합니다. 처음에는 미리 입력을 스택에 다 넣어주고, 하나씩 꺼내면서 비교했는데, 이 경우에는 최악의 경우 (내림차순으로 정리되어 있을 때) O(n^2)의 시간 복잡도를 가지기 때문에 n이 백만이나 될 수 있는 해당 문제에는 시간 초과가 발생합니다. 따라서 입력을 줄 때 바로 결과를 도출할 수 있게 시간복잡도를 O(n)까지 줄여야 합니다. 1. 원소(num)를 입력을 받습니다. 2-1. 스택이 비어 있다면, 원소의 index..