본문 바로가기

Algorithm/Sweeping

 (9)
(C++) - LeetCode (easy) 643. Maximum Average Subarray I https://leetcode.com/problems/maximum-average-subarray-i/description/ Maximum Average Subarray I - LeetCode Can you solve this real interview question? Maximum Average Subarray I - You are given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return thi leetcode.com 누적합으로 해결한 문제였습니다. 📕 ..
(C++) - 백준(BOJ) 20366 : 같이 눈사람 만들래? https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net two pointer로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 눈사람 수 n, 정답을 출력할 변수 ans, 눈덩이의 지름을 저장할 일차원 배열 snow를 선언한 후 적절히 입력받습니다. 📔 풀이과정 i ~ j까지의 눈사람이 다음과 같이 있을 때 i, j지름의 눈덩이로 눈사람을 만들고 i+1, j-1지름의 눈덩이로 다른 눈사람을 만든다고 볼 수 있습니다...
(C++) - 백준(BOJ) 15565번 : 귀여운 라이언 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 연속합 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 어피치 인형은 확인할 필요가 없습니다. 라이언 인형의 위치만 저장해 확인합니다. n, k를 입력해서 이를 vector 변수 lionIdx에 저장합니다. 📔 풀이과정 저장된 라이언 인형들의 인덱스 정보들만 확인해줍니다. 예제를 통해 설명하자면 저장된 인덱스들의 정보는 이렇습니다. lionIdx = [0, 4, 6, 9]여기서 k를 포함하는 ..
(C++) - 백준(BOJ) 2018번 : 수들의 합 5 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net sliding window로 풀었습니다. 📕 풀이방법 📔 입력 및 초기화 l = 1, r = 1로 출발합니다. 답을 출력할 변수 ans, 연속구간의 누적합을 저장할 변수 sum, 입력받을 변수 n을 선언합니다. 📔 풀이과정 l > n; while(l
(C++) - 백준(BOJ) 1689번 : 겹치는 선분 https://www.acmicpc.net/problem/1689 1689번: 겹치는 선분 첫째 줄에는 선분의 개수(1 ≤ N ≤ 1,000,000)가 입력으로 들어온다. 그 다음 N개의 줄에 선분의 시작 좌표와 끝나는 좌표가 입력으로 들어온다. 선분의 좌표는 절댓값이 10억보다 작거나 같은 정수 www.acmicpc.net priority_queue를 이용한 sweeping 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 선분 시작좌표, 선분 끝 좌표를 pair로 한 vector형 자료구조 v를 선언하고 n만큼 입력받습니다. 2. v를 오름차순으로 정렬해줍니다. 기준은 first먼저 그 다음 second로 정렬됩니다. 3. min heap인 priority_queue 변수 pq를 선언해줍니다. 4...
(C++) - 백준(BOJ) 2467번 : 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net two pointer문제였습니다. 풀이방법 1. l = 0, r = n-1로 시작해 두 용액의 합을 찾습니다. 2. 두 용액의 합에 대해 절댓값이 더 작다면 현재 합을 갱신해줍니다. 그리고 정답에 대한 index 또한 갱신해줍니다. 3. 현재 l과 r의 값 합이 0이면 loop를 탈출, 양수라면 양수가 있을 확률이 있는 r을 --, 음수라면 더 큰 값을 더해야하므로 l을 ++해주면서 원하는 ..
(C++) - 백준(BOJ) 1911 : 흙길 보수하기 www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 n >> l; while(n--){ int x,y; cin >> x >> y; waterHole.push_back({x,y}); } sort(waterHole.begin(),waterHole.end()); for(auto &w : waterHole){ if (x >= w.second) continue; x = max(x, w.first); int cnt = (w.second - (x + 1)) / l + 1; ans += cnt; x += l * cnt; } cout
(C++) - 백준(BOJ) 2170번 : 선 긋기 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net sweeping문제였습니다. *c와 동기화를 끊지 않으면 시간초과가 나는데 이유를 잘 모르겠습니다. 아시는 분은 댓글 달아주시면 감사하겠습니다. ㅠㅠ 풀이방법 1. vector pair 자료구조인 point라는 변수에 x,y값을 n번만큼 입력받습니다. 2. first를 기준으로 오름차순 first가 같다면 second 기준으로 오름차순 정렬해줍니다. 그 후 startPoint는 가장..

티스토리툴바