겜돌이의 개발일지

문제 백준 1725 히스토그램 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 풀이 오름차순 Monotonic Stack을 활용했다. startIdxs(n) 배열을 사용했는데, 이 배열은 i번째 value에 대해, 그보다 작은 값이 그전 원소들 중에서 언제 처음 등장하는지 인덱스를 담고 있는 배열이다. 작은 값이 없다면 0을 담고 있다. 예를 들어서 5 3 2 3 5에 대해 startIdxs는 idx순서대로 각각 0, 0, 0, 2, 3이 된다. 넓이를 구할 때는 특정 원소가 ..

문제 백준 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..

문제 백준 13335 트럭 C++ 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 풀이 트럭이 순차적으로 다리를 건너므로(FIFO) 큐를 이용한다. 3단계로 나눠서 풀면 편하다. 다리 위로 안 올라간 트럭들의 Queue와 다리 위에서 움직이고 있는 트럭 Queue 다리 위에서 움직이고 있는 트럭의 거리를 1증가시켜줄 임시 Queue 3개를 선언한다. 1단계 - 이미 다리 위에 있는 트럭들을 모두 1칸 앞으로 이동시킨다. 1-1 : 이 때 트럭이 다리를 건넜으면, ..

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 map을 이용해서 풀었다. 개수가 50만개라서 시간초과를 걱정하고 풀었는데, 아슬아슬했던 것 같다. 이분 탐색을 쓰면 더 효율적으로 풀 수 있는듯? map 자체도 이분 탐색이긴 하다만 upper_bound와 lower_bound를 쓰면 더 빠르게 풀 수 있다고 함. 소스 코드 map으로 해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

문제 백준 1715 카드 정렬하기 C++ 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 최소로 비교하는 방법은 작은 값부터 합치는 것이다. 방법은 다음과 같다. 1. 오름차순으로 queue를 정리한다. 2. 최소값 두 개를 꺼내고 합친 값을 queue에 다시 푸쉬 3. queue 사이즈가 1이라면 출력 소스 코드 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 ..

문제 백준 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..

문제 백준 1038 감소하는 수 C++ 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 감소하는 수의 순서는 다음과 같습니다. 한 자리 : 0 (0번째) -> 1 (1번째) ~ ... ~ 9 (9번째) 두 자리 : 10 -> 20 -> 21 -> 30 -> 31 -> 32 -> ... -> 98 세 자리 : 210 > 310 -> 320 -> 321 -> ... -> 987 네 자리 : 3210 -> ... -> 9876 ... 열 자리 : 9876543210 각 자리 수가 0~9 이기 때..

문제 백준 3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 주어진 입력에 따라서 다음을 수행합니다. 소스 코드 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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77..