[프로그래머스] 단속카메라 / 탐욕법, Greedy / C++ 풀이
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 주어진 구간에 대한 배열 routes를 정렬하고 앞에서부터 구간이 겹치게 단속 카메라를 설치할 수 있는 구간을 찾는다. 주어진 예시 [[-20, -15], [-14, -5], [-18, -13], [-5, -3]] 로 생각해보자. 위를 정렬하면 [[-20, -15], [-18, -13], [-14, -5], [-5, -3]]이고, 정렬된 routes를 앞에서부터 살펴보면서 구..
[프로그래머스] 연속 펄스 부분 수열의 합 / Prefix Sum, 구간 합
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/161988# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 풀이 전략 주어진 sequence 수열에 [1, -1, 1, -1, ...]이 곱해진 수열과 [-1, 1, -1, 1 ...]이 곱해진 수열을 만든다. 두 수열 에서 특정 구간을 더했을 때 그 합이 제일 큰 것을 구하면 답이다. 이 아이디어를 구현할 때 sequence의 길이가 50,000까지 가능하다는 점에 유의해야 한다. 시간 복잡도를 고려하여 O(n) 시간에 정답을 구..
