공부-코딩테스트72 6497. 전력난 (코딩테스트, 백준, 자바) 문제 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 나의 풀이 두 집 사이에 왕래를 하려면 반드시 길을 지나야 하며 길을 지나기 위해서는 불이 켜져있어야 한다. 불이 켜진 길은 거리만큼의 비용이 든다. 모든 집이 왕래가 가능해야 하기때문에 고립되어 있는 집이 없도록 해야 한다. 모든 선에는 비용정보가 있다. -> 모두가 연결되어 고립되지 않도록 하되 선들의 비용합이 최소를 선택 집 수 -1 2022. 8. 29. 연결된 그래프 합쳐졌는지 체크 (feat. 행성 터널 문제) 문제를 풀다보면 엣지와 간선이 주어졌을 때 가중치에 따른 간선선택상황이 올 수 있다. 간선 정보들이 매우 많을 때 적절히 정렬되어 있다고 가정했을 때, 필요없는 간선인지 판단하는 것과, 간선 선택시 상황을 기억하고 있는 정보들을 업데이트를 해야할 것이다. ex) 0 -1 , (2-3, 3-4) 로 연결되어 있었고 1-4간선을 발견하였다. 1-4 연결이 되면 두 집합이 하나로 합쳐졌다고 정보를 수정해야 한다. parent = new int[N]; //parent[i] = i 라고 생각 while (!queue.isEmpty()) { Edge tmp = queue.poll(); if (!isSameParent(tmp.s, tmp.d)) { System.out.println(tmp.s + " " + tmp.d.. 2022. 8. 21. 세그먼트 트리 : 구간별로 비교할 경우 (feat. BOJ : 히스토그램에서 가장 큰 직사각형 ) 세그먼트 트리의 원리 : 연속된 구간의 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 트리 원리는 쉽다. 입새노드를 좌에서 우로 순서대로 배치한다. 트리의 크기는 아무리커도 배열크기의 원소들이 입새노드가 될 수 있으면 된다. 아래 식을 확인해보면 이해할 수 있다. 부모노드는 자식노드의 합산으로 결정되고 부모값이 의미하는 바는 자식노드들의 합산이 된다. 부모노드들은 결국 해당구간의 합산을 기억하고 있으며 필요한 범위를 지정하면 접근하도록 구현하면 완성된다. 편의를 위해 루트노드의 인덱스는 1로 왼쪽 자식은 *2 , 오른쪽 자식은 *2+1 한값을 기억하도록 한다. 코드 : 자바 int h= (int) Math.ceil(Math.log(N)/ Math.log(2)); h = (int)Math.pow(2, .. 2022. 8. 20. 자바 : 해시맵 사용법 해시맵 : 다량의 데이터를 검색하는데 뛰어난 성능을 가진 맵 인터페이스 계열의 대표적인 클래스 키(key)와 값(value)의 쌍으로 이루어짐 key 값은 중복이 되지 않고, value 값은 허용 데이터 입력은 느리지만 검색은 효과적인 자료구조 import java.util.HashMap; HashMap map = new HashMap(); map.put(key,value); map.get(ket); map.getOrDefault(check_input,replace_value);//check_input키값이 존재x -> 대체값으로 리턴 map.keySet()//키 데이터들의 집합, 배열로 사용하려면 .toArray() 오브젝트 배열로 저장 사용한 문제 예시 4358번: 생태학 프로그램은 여러 줄로 이루어.. 2022. 8. 13. 자바 : 우선순위 큐 사용법 자바에서는 Heap을 위한 클래스가 따로 있진 않다. 우선순위 큐를 통해서 Heap기능을 대신할 수 있다. 우선순위 큐 : 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 Queue 특정조건에 맞게 queue를 배치하여 들어갈 때 우선순위 조건에 맞게 queue가 설정 주어진 원소들 중에서 조건에 맞게 순서대로 뽑아내고자 할 때 사용할 수 있다. 사용 방법 import java.util.PriorityQueue; PriorityQueue Q = new PriorityQueue((e1, e2) -> { //조건 등등 return e1 - e2;//예시 }); 해당 사용방식은 람다식을 사용한 형식으로 아마 코딩테스트를 하면 이런 방법으로 사용하지 않을까 싶다. 객체.. 2022. 8. 13. 자바 순열 조합 암기하면 좋은 메소드 자바는 내장함수로 순열, 조합이 없기 때문에 필요시 구현할 줄 알아야 한다. 방문탐색을 통해 구현하는 순열, 조합 코드 import java.util.Arrays; public class Perm_Combi { static int N; static int R; static int[] input; //길이 N 뽑을 대상 static int[] numbers;//길이 R 뽑힌 것 static boolean[] isSelect; //선택된거 기억 public static void main(String[] args) { N = 4; R = 3; input = new int[N]; isSelect = new boolean[N]; numbers = new int[R]; for (int i = 0; i < N; i+.. 2022. 8. 11. 이전 1 2 3 4 5 ··· 12 다음
