겜돌이의 개발일지

문제 백준 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이 된다. 넓이를 구할 때는 특정 원소가 ..

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

문제 백준 20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N > N >> Q; for (int i = 0; i > num; int temp = num; bool canreach = true; stack st; //경로를 스택에 넣어줌 while (temp != 0) { st.push(temp); temp /= 2; } //스택 꺼내면서 경로확인 while (!st.empty()) { temp = st.top(); //경로의 해당 땅을 지나갈 수 없으면 if (check[temp] == true) { cout

문제 백준 2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 먼저 탑의 높이와 인덱스를 받는 stack을 선언합니다. 탑의 높이를 입력해주고, 뒤에서 부터 다음 과정을 실행합니다. 1. 스택이 비었을 경우에는 탑의 높이와 인덱스를 스택에 push 합니다. 2. 스택이 비어있지 않을 때는, 스택의 top과 현재 탑의 높이를 비교하여, top이 작다면 레이저가 도달한 것이므로 레이저가 닿는 탑의 위치를 저장하는 배열 receive에 탑의 위치를 저장해준 후, stack을 pop 합니다. 3. 계속해..

문제 백준 2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 N자리 숫자에서 K개만큼을 꺼내 줘야 합니다. 예제 입력 3의 경우를 보겠습니다. 10 4 4177252841 10자리 숫자에서 4자리를 제거해 가장 큰 숫자를 만들어야 합니다. 스택이 비지 않았고, 꺼낼 수 있으며, 현재 넣을 수가 stack의 top보다 클 때 stack을 pop 하고, cnt를 증가시켜줍니다. [1번째 자리] 스택에 4를 push 합니다. (stack : 4) [2번째 자리] 1은 4보다 크지 않으므로 스택에 psuh 합니다. (stack : 41) [3번째 자리] 7은 1보다 크므로 스택을 ..