끈기 있는 개발 공간

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/152995#접근여러 사원의 석차 중에서 완호의 석차만 생각하면 되므로 인센티브를 못 받는 사원을 먼저 정하고 그 중 완호 보다 높은 점수의 사원들을 계수하면 문제를 해결할 수 있다.하지만 인센티브를 못 받는 사원을 정할 때 단순하게 이중 for문으로 순차 탐색을 할 수 없다. scores 의 길이 제한이 $1\leq{...}\leq{100,000}$ 이기 때문이다.이를 위해 $O(N\log{N})$ 의 시간 복잡도를 가지는 정렬을 이용한다.먼저 근무 태도 점수를 기준으로 내림차순 정렬 후 같은 근무 태도 점수에 대해 동료 평가 점수를 기준으로 오름차순 정렬하면 iteration할 때 근무 태도 점수에..

https://school.programmers.co.kr/learn/courses/30/lessons/161988접근sequence 의 길이 제한이 $1\leq{...}\leq{500,000}$ 이므로 $O(N^2)$ 이상의 시간 복잡도를 가지는 알고리즘으로 문제를 해결할 수 없다.연속 펄스 부분 수열의 합의 최댓값을 구하는 것이므로 펄스 수열을 DP에 대응시켜 문제를 해결할 수 있다.즉, sequence 를 iteration 하면서 현재 원소와 이전의 연속 펄스 부분 수열의 합과 비교해 더 큰 값을 계속해서 저장시킨다.단, 펄스 수열이 -1과 1 두 가지 경우로 시작할 수 있으므로 두 경우 모두 저장시키도록 DP 배열을 정의한다.dp[i][0] : sequence 의 인덱스 0부터 i까지 펄스 수열의..