[프로그래머스] 섬 연결하기(Java, Greedy, Lv3)
programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr ## 접근방법 섬을 최소의 비용으로 연결해야 한다. 이 문제를 보자마자 최소 신장트리의 개념이 떠올랐다. 가장 거리가 짧은 것들 부터 추가하면, 최소의 비용으로 모든 섬들을 연결할 수 있다. 그리디에서 자주 출제되는 유형은, 가장 거리가 짧은 것부터 찾아서 전역적 최적해를 찾는 방식이 자주 나오는 거 같다. 본론으로 돌아가서, 크루스칼 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다. 처음에 시행착오를 소개하자면, 다리 비용을 기준으로 오름차순으로 정렬을 마쳤지만, 섬을 방..
[프로그래머스] 단속카메라(Java, Greedy, 사고력, Lv3)
programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr ## 접근방법 그리디 문제는 항상 코드는 단순하지만, 생각해내기가 쉽지 않다. 이 문제는 최소의 단속카메라를 통해서, 모든 운전자들을 단속할 수 있어야 한다. 어떤 운전자부터 카메라를 배치해야할까? 단속이 안된 운전자중에서, 가장 도착 거리가 작은 운전자를 확인해야 한다. 가장 도착 거리가 작은 운전자도 카메라에 찍혀야 되므로 카메라는 두는 것은 자명하며, 가장 도착 거리가 작은 운전자부터 확인해야 다른 운전자들이 해당 단속카메라로 단속이 된다면, 카메라를 불필요하게 설치할 일이 ..
[프로그래머스] 네트워크(Lv3, BFS/DFS, 시간복잡도, Java, 정답, 코드)
programmers.co.kr/learn/courses/30/lessons/43162?language=java 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr ## 접근방법 같은 네트워크들끼리는 무조건 연결되어 있다는 점을 착안해서 문제를 풀어보자. 어떤 컴퓨터에서 탐색을 시작하면, 연결된 컴퓨터들을 모두 찾을 수 있다. 완전 탐색 기법인, BFS와 DFS를 둘다 가능하며, 시간복잡도는 O(N * N)이다. 완전 탐색 시에, 네트워크가 정해진 컴퓨터는 방문하지 않도록 체크한다. 생각보다 간단한 문제이므..
[프로그래머스] 광고 삽입(Java, Lv3, 카카오, 누적합)
programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr ## 접근방법 광고를 삽입해서, 가장 많은 시간이 누적되도록 하는 구간을 찾아야 한다. 시청자들의 출입에 관한 로그 정보들이 있다. 출입에 관한 로그 정보들을 이용해서, 1초동안 누적된 시간들을 구할 수 있다. 만약에 1초에 시청을 시작하고, 10초에 시청을 종료한다고 생각해보자. 1초의 순간에 한 명이 ..