Programmers - 단속 카메라 with JAVA
문제 - 차량의 이동 경로가 주어진다. - 이 때, 최소한의 카메라를 설치하여 모든 차를 한번이라도 단속할 때 설치해야하는 카메라의 수의 최소값을 구하라. 예를 들어, 다음과 같은 경우가 주어진다. 차량1 : [-20, -15] -> 차량1은 -20지점에서 고속도로에 진입해 -15지점에서 고속도로를 빠져나간다. 차량2: [-14, -5] 차량3 : [-18, -13] 차량4 : [-5, -3] 이 때, -15지점과 -5지점에 카메라를 설치하면 모든 차량을 한번은 감시하면서 최소한의 카메라를 설치한 경우가 되는 것이다. 로직 우선, 첫번째 인덱스를 기준으로 차량 데이터를 정렬한다. [-20, -15], [-18, -13], [-14, -5], [-5, -3] 순서대로 1지점, 2지점, 3지점, 4지점이라고..
최종 순위
문제 - 팀별 작년 순위가 주어진다. - 이번 년도에 순위가 바뀐 두 팀이 주어진다. (2, 4)일 시 만약, 팀2가 팀4보다 순위가 높았다면 이번에는 팀4가 팀2보다 순위가 높음 - 순위 변경을 확인해 이번년도 순위를 구하고 구할 수 없다면 Impossible을 출력 로직 위상정렬을 사용한다. indegree(진입차수)가 낮을수록 높은 순위를 의미. 예를들어, 작년 순위가 5, 4, 3, 2, 1 일 때, 진입차수는 0, 1, 2, 3, 4 임을 의미한다. 또한 팀별 연결 여부를 통해 누가 더 높은 순위인지 체크한다. 예를 들어, 위와 같은 경우에서는 5 - 4, 3, 2, 1 보다 크다. 4 - 3, 2, 1 보다 크다. 3 - 2, 1 보다 크다. 2 - 1 보다 크다. 1 - 이를 true로 설정..
도시 분할 계획
문제 - 도시들이 서로 연결된 간선이 주어진다. - 간선으로 도시들 간 그룹을 만든다. - 그룹을 두개로 나눌 것이다 - 각 그룹은 적어도 하나의 도시로 이루어진다. - 간선 비용을 최소로 하고 싶다. 아이디어 - 그룹 지은 후에 선을 하나 삭제 시 그룹은 두개로 나뉜다. 코드 public class Question2 { public static void main(String[] args){ int[][] data = { {1, 2, 3}, {1, 3, 2}, {3, 2, 1}, {2, 5, 2}, {3, 4, 4}, {7, 3, 6}, {5, 1, 5}, {1, 6, 2}, {6, 4, 1}, {6, 5, 3}, {4, 5, 3}, {6, 7, 4} }; Arrays.sort(data, Comparat..
팀 결성
문제 - 학생들이 0번부터 N번까지 존재한다. 팀 합치기, 같은 팀 여부 확인 연산을 실행하라. - 데이터가 주어질때, 앞자리가 0이면 합치기 연산, 1이면 같은 팀 확인 여부 연산을 실행한다. 구현 - 서로소 집합 알고리즘 - 경로 최적화 코드 public class Question1 { public static void main(String[] args){ int[][] data = { {0, 1, 3}, {1, 1, 7}, {0, 7, 6}, {1, 7, 1}, {0, 3, 7}, {0, 4, 2}, {0, 1, 1}, {1, 1, 1} }; int[] parents = new int[8]; for(int i=0; i parent2) ? parent2 : parent1; parents[parent2..
