https://blog.6r33n.kr/ 6R33N A minimal, responsive and feature-rich Jekyll theme for technical writing. blog.6r33n.kr
전체 글
문제 1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이분 탐색에 대해 알아볼 수 있는 좋은 문제입니다. 제한 시간이 1초인데, 만약 A 배열과 X를 모두 비교한다면 $O(N^{2})$의 시간 복잡도를 가지게 되므로 시간 초과가 발생합니다. 그러므로 다른 방법을 사용해야 하는데, C++에는 친절하게도 binary_search라는 훌륭한 이분 탐색 함수가 존재합니다. 그저 시작 부분, 끝 부분, 찾을 숫자만을 넣..
문제 11003번: 최솟값 찾기 (acmicpc.net) 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 저번에 풀어본 [백준] 15678 - 연세워터파크 (C++) — 6R33N 에 이어서 또다른 덱 활용 문제입니다. 이번 문제는 주어진 수열에서, L 크기의 구간에서 지속적으로 최솟값을 찾아야 하는 문제입니다. A가 2 1 5 4 2, L이 3인 경우를 예로 들어보겠습니다. 먼저 dq에 첫번째 숫자가 들어가므로 2가 저장됩니다. (2) 1이 들어오는데, 2보다 작으므로 2..
문제 15678번: 연세워터파크 (acmicpc.net) 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net 풀이 오랜만에 만나 본 단조 큐 문제입니다. 단조 큐가 무엇인지는 이곳에서 다루지 않겠습니다. 좌측에서 우측으로 이동하면서, 구간 내의 최댓값을 유지해야 하는 문제이므로 덱을 사용하였습니다. 먼저 i - D보다 작은 값들은 모두 제거하여 건널 수 없는 징검다리를 제거합니다. 그리고 지속적으로 현재 dp[i]와 다음 징검다리의 번호를 더한 값(K[i])을 비교하여 최댓값을..