분류 전체보기116 연결된 그래프 합쳐졌는지 체크 (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. Dockerfile docker-compose.yml Dockerfile : 컨테이너의 설계도 RUN , WORKDIR, CMD 등 활용하여 컨테이너의 기본 설정을 해주는 역할을 한다. 만들고자 하는 프로젝트내에 위치한다 docker build 명령어를 사용하고 도커 파일을 명시하여 사용하게 된다. docker-compose.yml : 다중 컨테이너 애플리케이션을 배포하려는 방법을 정리한 파일 docker-compose up 으로 설정한 내용대로 컨테이너 실행 Dockerfile이 어디에 위치되어있는지, 포트번호는 몇번을 쓸 것인지, 볼륨위치 등 명시하는 파일 Dockerfile은 이미지를 만드는 설계도, docker-compose는 설계도들의 관리자라고 볼 수 있다. 2022. 8. 14. 자바 : 해시맵 사용법 해시맵 : 다량의 데이터를 검색하는데 뛰어난 성능을 가진 맵 인터페이스 계열의 대표적인 클래스 키(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 6 7 8 ··· 20 다음
