[Codility] MaxNonoverlappingSegments, 코딜리티 그리디 greedy
문제는 다음과 같다. 풀이 방법으로 생각했던 것은 다음과 같다. 모든 세그먼트를 하나의 평면으로 통합시키면, 중복은 전부 연결이 된다. 이 때 떨어져있는 세그먼트들의 수를 세면 된다. 통과되는 답은 다음과 같다. 계속 50프로만 되다가 다른 블로그를 보고 참고했는데.. public class MaxNonoverlappingSegments { public static void main(String args[]) { int count = solution(new int[] {1, 3, 7, 9, 9, 10}, new int[] {5, 6, 8, 9, 10, 10}); System.out.println(count); } public static int solution(int[] A, int[] B) { if (..
프로그래머스 - 여행경로,DFS,백트래킹, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,backtracking,깊이우선탐색
// DFS 문제에서 backtracking인 것은 알았는데, stack으로 푸려다가 며칠간 고통받다가 그냥 재귀로 품 // Process // 1. Input tickets, make map // 2. Sort adjacents (알파벳순으로 들러서 먼저 나오는 것을 찾아가도록) // 3. DFS, backtracking. Start from ICN // 4. Return airport names 포인트는.. 안쓰는 티켓이 없어야 한다는 것. 그래서, DFS로 돌면서 그냥 연결된 공항을 그냥 다 순회한다는 개념이 아니라.. - 각 공항에서 연결된 공항을 따라가면서 방문한 공항은 제거해준다(방문 제외 개념). - 이 때, 더이상 공항에서 연결되어 방문할 공항이 없으면, 모든 티켓을 쓴 상황이어야 한다 (..
백준 11725 - 트리의부모찾기,시뮬레이션,우선순위큐, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,dfs, priority queue
// Process // 1. Input n, edges // 2. Make node lists with adjacents // 3. Make stack, and put first root node // 4. Iterate while stack is not empty // 4.1. Iterate adjacents // 4.1.1. Set parent number, if this adjacent is not visited yet // 5. Print all parent numbers from 2 to end // 6. Finish import java.io.*; import java.util.*; class FindParentTree { public static void main(String[] args)..
백준 10775 - 공항,시뮬레이션,우선순위큐, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,dfs, priority queue
// Process // 1. Input countGate, countAirplane, airplanes // 2. Iterate airplanes while docking status true // 2.1. 비행기입력번호 이하의 게이트 위치에 도킹이 가능한 곳을 찾아 채운다. // 2.2. 도킹하면 개수 센다. // 2.2.1. 없으면 종료한다. // 3. 개수 출력한다. import java.util.*; class Airport { public static void main(String[] args) { int count = 0; Scanner scanner = new Scanner(System.in); int countGate = scanner.nextInt(); int countAirplanes..
백준 16236 - 아기상어,시뮬레이션,우선순위큐, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,dfs, priority queue
// Process // 1. Input n of nxn, nxn matrix // 2. 먹을 수 있는 물고기가 있으면 반복한다. // 2.1. 먹을 수 있는 물고기 중, 가장 가깝고, 맨 위의 왼쪽에 있는 물고기와의 거리를 센다. // 2.2. 해당 위치로 상어를 이동시킨다. // 2.3. 총 거리에 센 거리를 더한다. // 2.4. 사이즈업까지 남은 고기수를 줄인다. // 2.5. 빈칸으로 만든다. // 3. 총 거리를 반환한다. import java.io.*; import java.util.*; class BabyShark { static List eatable; public static void main(String[] args) throws IOException { // 1. BufferedRe..
백준 11000 - 강의실배정,우선순위큐, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,dfs, priority queue
// Process // 1. Input lecture count, lecture start and end times // 2. lecture times를 시작시간 기준 오름차순으로 정렬한다. // 3. 강의실 사용 우선순위큐를 만들어 종료시간을 기준으로 오름차순 poll 되도록 한다. // 4. 강의시간을 전체 반복한다. // 4.1. 강의실 사용 시간들 중, 가장 먼저 끝나는 시간의 강의실에 강의를 넣을 수 있는지 확인해서 // 4.1.1. 있으면 -> 끝나는 시간 변경한다. // 4.1.2. 없으면 -> 강의실 새로 추가해서 끝나는 시간 넣는다. // 5. 필요 강의실 개수 반환한다. // 퍼포먼스를 위해서는 priority queue 써서, 강의실 사용 시간 중 가장 먼저 끝나는 시간을 계속 최신..
