끈기 있는 개발 공간

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까지 펄스 수열의..

https://school.programmers.co.kr/learn/courses/30/lessons/181186접근여러 경우의 수를 고려해야 하는 DP 문제다.규칙성을 찾기 위해서는 $n$ 이 증가함에 따라 새로 추가되는 영역을 봐야 한다.일단 문제에서도 확인할 수 있듯이 $n=3$ 인 경우의 수는 10이다.여기서 $n=4$ 에서 재사용할 수 있는 경우는 90도 회전된 $3\times{1}$ 타일이 있는 경우다.나머지 $3\times{1}$ 타일이 있는 경우는 $n=1$ 에서의 결과를 재사용하고, ㄱ자 타일로만 구성된 $3\times{2}$ 타일에서는 $n=2$ 에서의 결과를 재사용해야 하기 때문이다.다음으로 $n=4$ 에서 재사용 가능한 경우는 다음과 같이 두 개다.90도 회전된 $3\times{1..

https://school.programmers.co.kr/learn/courses/30/lessons/214288접근문제에서 요구하는 바는 멘토를 적절히 배정했을 때 참가자들이 기다린 시간의 합의 최솟값이다.따라서 이 문제는 멘토를 적절히 배정하는 문제와 참가자들이 기다린 시간의 합의 최소를 구하는 문제로 나눌 수 있다.우선 멘토를 적절히 배정하는 문제는 제한사항에 따라 멘토를 배정하는 모든 경우의 수를 구하면 된다고 생각했다.멘토가 각 유형별로 아무리 많아봤자 $n-k=15$ 이기 때문에 문제를 해결하는 데 시간은 충분하다.다음으로 참가자들이 기다린 시간의 합의 최소를 구해야 한다.최적화를 고려하면 분마다 iteration 하는 것보다는 reqs 을 그대로 iteration하여 각 차이를 계산하여 결..

https://school.programmers.co.kr/learn/courses/30/lessons/214289접근처음엔 그리디 알고리즘인가 했는데 처리해야 하는 케이스가 너무 많았다.그렇다고 백트래킹으로 하기에도 문제 제한사항을 만족하기 어렵다.다음으로 생각해본 게 DP인데 각 분마다 모든 온도에 대해 최소 비용을 저장하면 문제 해결이 가능하다고 생각했다.단, 제한사항에 temperature의 범위가 $-10\leq{...}\leq{40}$ 이기 때문에 memoization하기 위해서는 온도에 관련된 입력 변수들에 10씩 더해 양의 정수로 만들어줘야 한다.memoization을 위한 dp[i][j] 의 정의는 i 분에서 j 온도가 되기 위한 최소 비용이다.최소 비용을 저장할 때 총 네 가지의 케이스..

https://school.programmers.co.kr/learn/courses/30/lessons/258705접근전형적인 DP 문제다.$n$ 을 점점 늘려 최종 결과를 산출하는 과정에서 $n-1$ 과 $n$ 에서의 연산 결과의 연관성을 찾으면 된다.일단 $n=1$ 일 때는 경우의 수가 $4$ 임을 쉽게 알 수 있다. 윗 변에 공유하는 정삼각형이 없는 경우의 수는 $3$ 이다.$n=2$ 이고 윗 변에 공유하는 정삼각형이 있는 있는 경우를 확인해보자.$n=1$ 의 결과에서 새로운 영역(빨간색 영역)의 경우의 수를 곱하는 경우의 수가 결과에 포함됨을 알 수 있다.하지만, 이 새로운 영역이 추가됨에 따라 타일에 의해 공유하는 영역도 생겼다.이 공유 영역(보라색 영역) 또한 고려해줘야 모든 경우의 수를 알아..

https://school.programmers.co.kr/learn/courses/30/lessons/258707#접근그리디 알고리즘 문제다.이 문제는 작정하면 정말 까다로워질 수 있는 문제다.그래도, 문제에서 제한을 많이 주었기 때문에 그런 상황은 피할 수 있었다.cards 의 원소가 중복되지 않고 n 과 cards 의 길이가 같기 때문에 coin 의 비용이 가장 적게 드는 경우를 우선 선택하면 된다.가장 적게 드는 비용은 동전 1개이고, $\frac{n}{3}$ 번 이하의 카드를 포함하는 조합에서만 가능하다.하지만 비용이 크다고 해서 선택하지 않고 다음 라운드로 넘어가면 정작 필요할 때 그 카드를 사용하지 못할 수 있다.그래서 각 라운드마다 제출하는 카드를 고정시키지 않고 이전 라운드의 카드를 선택..

https://school.programmers.co.kr/learn/courses/30/lessons/258709접근A와 B가 있다. 먼저, n개의 주사위 중 $\frac{n}{2} $ 개를 선택하는 조합을 구해야 한다.그리고 각 주사위 조합에 대해 주사위 점수 합산을 계산하여 저장한다.마지막으로, A 주사위 조합 중 점수 합산에서 가장 큰 승률을 가진 조합을 찾아 반환한다.이 문제는 총 세 문제로 구분할 수 있다.첫 번째, 주사위 조합을 구하는 문제는 생각보다 쉽게 구현할 수 있다.재귀를 사용하여 조합을 구현하면 된다. 나의 경우에는 주사위를 선택하는 경우와 선택하지 않는 경우로 구분하여 모든 조합을 구했다.두 번째, 주사위 점수 합산을 계산하는 문제는 합산만 저장하는 게 아니라 그 합산이 어떤 주사..