징검다리 건너기
programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 처음에 이 문제를 접근할 때 DP로 생각했었다. 왜냐하면 K개 이상의 연속된 돌 중에서 가장 큰 값이 건널 수 있는 인원 수이기 때문이다. K개의 돌 중에서 가장 값이 큰걸 기준으로 DP배열에 기록해두고, 이후에 진행할 때는 덱을 사용하여 먼저 넣었던 원소를 빼고, 그 다음 원소를 추가 및 최댓값을 갱신하여 다시 DP 배열에 기록하는 방식이다. 그런데 정확성은 모두 통과했지만 효율성을 통과하지 못했다. 의심되는 원인으로는 최댓값을 구하기 위한 방법으로 max_element를 K개의 범위에서..
합승 택시 요금
programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 문제의 특징은 묵시적 그래프인 것과 최단거리를 구하는 것, 합승하는 경우를 계산하는 것이다. 일반..
구명보트
처음 문제를 보고 생각한건, 무게 제한을 만족하는 최대 인원 수가 최적해라고 생각하여 우선순위 큐를 사용하여 가장 작은 무게를 가진 사람부터 빼내는 방법을 사용했지만 오답이라고 나왔다. 왜냐하면 구명보트의 인원 제한이 2명이라는걸 인지하지 못했다. 다른 코드를 참고해본 결과, 무게 제한에 가장 근접하면서도 인원 제한을 만족하는 원소들이 최적해라는걸 알았다. 이해를 돕기 위해 예를 들어보겠다. 무게제한 : 100 [30, 40, 50, 60] 무게가 가장 작은 인원부터 빼내면 횟수가 3번이지만 (30, 40), (50), (60) 무게 제한에 가장 근접하게 빼내면 2번이다! (30, 60), (40, 50) 이 점에서 Greedy의 특성이 나타난걸 알 수 있다. 또한 탐색 범위를 효과적으로 줄이기 위해 투..