. '알고리즘' 태그의 글 목록
본문 바로가기

알고리즘2

[그리디, 힙] 단속카메라 코딩테스트 연습 - 단속카메라 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 그리디 문제라고는 하지만, 생각만큼 쉽진 않을 것 같다. 포인트는 두개인 것 같다. '최대한 많이겹치는 경로'랑 '모든 경로를 한 번은 지나쳐 가야한다.' 그렇다면, 출발지 기준으로 sort를 한다. heapify가 괜찮을 것 같다. 그리고 맨 처음 경로를 뽑아내 키값으로 만들고, 그 다음 경로들이 키값에 포함되어 있으면 pop을 한다. 그리고 키값에 포함되어있지 않는 경로가 나올때까지 pop을 한다. 그리고 그 경로가 나왔다면, 그 경로를 새로운 키값으로 하고 같은 행동을 반복한다. .. 2021. 5. 11.
[이분탐색] 징검다리 코딩테스트 연습 - 징검다리 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 내가 제일 싫어하는 이분탐색이다. 이분탐색은 항상 어렵다. 사실 어떻게 풀어야 될지도 모를 것 같기 때문이다. 일단 이분탐색으로 업다운 할 것을 정해야한다. 쉬운 이분탐색 문제라면 답으로 구할 것을 이분탐색하겠지만, 이 문제에서는 어떨까? 이 문제의 목적은 '최솟값 중에 가장 큰 값'이다. 일단 바위를 제거하지 않고 순회를 돈다. 예시에선 바위가 [2, 11, 14, 1.. 2021. 5. 10.