본문 바로가기
반응형

전체 글

 (168)
구간 트리(세그먼트 트리) 세그먼트 트리 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 답할 수 있도록 하는 방법이다. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것이다. 구간 트리의 루트는 항상 배열의 [0,n-1]을 표현한다. 구간 트리에서 질의에 응답하는 시간복잡도는 O(logn)이다. 구간 트리에서 구간을 모두 저장하기 위한 배열의 길이는 n이 2의 거듭제곱이라면 2n이면 된다. 그렇지 않다면 가장 가까운 2의 거듭제곱으로 n을 올림한 뒤 2를 곱해야 한다. 하지만 간단한 방법으로 4n으로 배열의 길이를 잡으면 된다. 메모리가 낭비된다는 단점이 있지만 편리하게 쓸 수 있다. 구간 트리 초기화 static long init(int node, int s, int e) { i..
다익스트라,벨만포드,플로이드 워샬 다익스트라 한 정점에서 다른 정점까지 최소로 가는 경로를 구하는 최단 경로 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식. 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다. 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다. 음의 가중치가 있을 경우 사용하지 못한다. 시간복잡도는 일반적으로 O(V^2), 우선순위큐를 사용한다면 O(ElogV)이다. 동작과정 1. 시작 정점을 입력 받는다. 2. 거리를 저장할 D배열을 무한대로 초기화 한 후 시작점에서 갈 수 있는 곳의 값은 바꾼다. 3. 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치 합이 작다면 변경한다. 4..
XML 파싱(DOM,SAX) 파싱 문서를 구성하는 태그를 컴퓨터가 알아 볼 수 있도록 파꿔주는 과정 DOM 파싱 문서 전체를 메모리에 로드하여 원하는 노드에 바로 접근이 가능하다. - XML문서를 읽으면 모든 Element, Text, Attribute 등의 객체를 생성, 이를 Document객체로 리턴한다. - Document 객체는 트리 구조의 자바 객체로 표현되어 있다. - XML 문서가 메모리에 모두 올라가 있기 때문에 노드들의 검색, 수정, 구조변경이 빠르고 용이하다. - SAX 보다 직관적이고 단순하여 DOM 방식을 채택한다. SAX 파싱 XML 문서를 하나의 긴 문자열로 간주한다. - XML 문서를 앞에서 순차적으로 읽어가면서 노드가 열리고 닫히는 과정에서 이벤트가 발생. - 각각의 이벤트가 발생될 때마다 수행하고자 하..
[BOJ] 17398번 통신망분리 1. 이해하기 하나의 통신망을 Q번을 통해서 분리하는데 드는 비용을 구하는 문제이다. 통신탑 연결을 끊었는데 통신망이 나눠지지 않는다면 비용은 0이다. 통신망이 나눠진다면 나눠진 통신망이 가지고 있는 통신탑의 갯수를 곱한 값이 비용이다. 예를 들어 통신탑 연결을 끊었는데 3개의 통신탑, 3개의 통신탑 이렇게 두개의 통신망으로 나눠졌다면 3*3=9의 비용이 드는 것이다. 유니온 파인드를 이용해서 풀 수 있다. 유니온 파인드는 각 정점을 잇는 방법인데, 여기서는 각 정점을 끊는 방법이다. 역으로 생각하면 풀 수 있다. 끊는 통신탑에 대해서는 처음에 연결을 하지 않고 한번 더 역으로 방문하면서 이어주는 방법이다. 2. 구현하기 package algo; import java.util.Arrays; import ..
[BOJ] 15459번 Haybale Feast 1. 이해하기 음식을 준비하는데 각 음식에는 맛과 매운 정도가 있다. 한 코스를 준비하는데 그 코스의 전체 맵기는 코스 내의 전체 요리 중 가장 높은 맵기로 결정이 된다. 코스는 연속된 음식을 말한다. 이때, 적어도 M의 맛이 되면서 준비할 수 있는 코스 중 맵기가 가장 낮은 코스를 알아내는 문제이다. 유니온 파인드를 응용해서 문제를 풀 수 있다. 각 노드의 부모를 담았던 배열에 맛을 저장한다. 맵기를 기준으로 정렬할 배열이 필요하다. 이때 이 배열이 담고 있어야할 정보는 맵기와 이 요리의 인덱스이다. 인덱스가 필요한 이유는 양 옆에 코스로 만들 수 있는 음식이 있고 그 음식과 같이 함께 코스로 나갈 수 있도록 union 할 때 필요한 정보이기 때문이다. 맵기를 기준으로 정렬한 후 낮은 맵기부터 차례로 ..
[백준] 16932번 모양만들기 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. www.acmicpc.net 1. 이해하기 0과 1로 이뤄진 배열에서 1을 하나 놓음으로 1로 이뤄진 가장 큰 영역을 찾는 문제이다. 모든 0에 1을 놔보면서 크기를 비교한다. 하지만 1을 놓고 그때마다 dfs를 수행한다면 시간 초과가 일어난다. ..
특정 구간에 0~9의 숫자 갯수 찾기 start%10 가 0이 될때까지 start++를 한다. 이 과정에서 start에 나오는 숫자의 갯수를 세준다. end%10가 9가 될때까지 end--를 한다. 이 과정에서 end에 나오는 숫자의 갯수를 세준다. 0~9 모두에 (end-start+1)*t를 더해준다. 이때 t의 값은 어떤 자리수를 세는지에 따라 다르다. 예를 들어 일의 자리를 센다면 t=1이고 십의 자리를 센다면 t=10이다. 십의 자리를 셀때는 일의 자리를 셀 동안 계속해서 반복적으로 나오기 때문이다. start > end 혹은 start == 0, end == 0일때 반복을 종료한다. ans = 0; long mul = 1; while(A
next permutation 다음 순열에 해당하는 배열을 찾는 방법. 처음부터 순서대로 배열을 보면서 arr[i] = arr[i] 인 마지막 i를 찾는다. 만약 그러한 i가 없다면 이미 마지막 순열이다. 다음은 끝에서 시작하면서 arr[j] > arr[i] 인 첫번째 j를 찾는다. 이후에 swap(i,j)한다. 그 이후에 i+1부터 끝까지 정렬을 해준다. 정렬을 할 때는 앞뒤만 바꾸는 작업을 해주면 된다. 그 이유는 i+1부터 끝까지는 이미 내림차순이기 때문이다. 이 배열을 예로 들면 1번을 만족하는 i는 숫자 1을 가지고 있는 arr[2]이다. 또한 3번을 만족하는 j는 숫자 7을 가지고 있는 arr[4]이다. 따라서 i ..

티스토리툴바