본문 바로가기

백준9

[자바] 백준 2042 - 구간 합 구하기 세그먼트 트리 문제다. 세그먼트 트리는 한 번도 그 어디에서도 들어본 적도 없었는데, 아래 글 읽으니까 어느 정도 이해가 됐다. www.crocus.co.kr/648 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 요청하는 쿼리에 대해 방식이 달라질 수 있으나, 모든 쿼리를 다룰 수 없기에 구간 합에 대한 세그먼트 트리를 정리해 두었습니다. 내용이 길지만 그만큼 자세히 설 www.crocus.co.kr # 세그먼트 트리 - 시간 복잡도 : O(logN) - tree 배열과 array 배열은 다른 데이터다. array 배열은 1부터 N까지의 값이 들어가 있는 배열이라면, tree 배열은 구간합들이 들어가있는 배열이다. 트리의 노드를 각 배열에 대치시킨 것이라고 생각하면 된다.. 2021. 1. 6.

[자바] 백준 4386 - 별자리 만들기 각 별(=노드)의 위치를 좌표평면 상에 주고, 별들 간 거리는 알아서 계산한 다음에, 최소 스패닝 트리를 구하는 문제. n이 최대 100이기 때문에 거리를 구하는 데에는 100x99의 연산이 필요하니까 큰 문제는 없을 것 같은데 좀 귀찮네 ㅎㅎ 게다가 실수값이라 더 귀찮다. 1. 배열을 만들어서 각 별들의 x,y 좌표 담아두기 2. 이중 for문 이용해서 각 별들간 거리 구하고 그 값들은 PriorityQueue에 담아두기 3. PriorityQueue를 while문으로 탐색해서 최소 스패닝 트리값 구하기 DefimalFormat이라는 클래스를 써봤다. 그리고 다른 통과자들 코드를 보니까 PQ 이용하는 것보다는 ArrayList가 더 빠른가보다. /* 2021.01.05(화) */ import java... 2021. 1. 5.

[자바] 백준 1717 - 집합의 표현 유니온 파인드 문제 1. 내 부모가 누구인지 담는 배열 parent[i]을 일단 나 자신으로 초기화 한다. 2. 파인드 - 내 부모가 정말 최상위 부모인지 계속 찾아 나가면서, 최상위가 아닐 때에는 상위의 부모로 값을 교체한다. private static int find(int x) { if(parent[x]==x) return x; else return parent[x] = find(parent[x]); } 3. 유니온 - 두 숫자의 부모를 확인해서, 부모 값이 다르다면 부모 값을 a나 b의 부모값으로 교체해준다. 어떤 값의 부모를 넣을 것인지는 상관없다. private static void union(int a, int b) { a = find(a); b = find(b); if(a!=b) { par.. 2020. 12. 29.

[자바] 백준 1956 - 운동 시작점과 도착점이 정해져 있지 않고, 경로의 합이 가장 작은 사이클을 찾으면 된다. 사이클을 어떻게 찾아낼지에 대해 어렵게 생각했는데, 플로이드 워셜 알고리즘 이용해서 dist[1][1], dist[2][2], ..., dist[V][V]의 값들을 확인하면 되는 문제였다. 도시의 개수는 최대 400개이고, 간선의 개수도 최대 V(V-1)라고 했으니 최대 16만개로 보면 된다. 최대값들을 기준으로 생각했을 때, 간선은 16만번을 읽으면 되고, 플로이드 워셜 알고리즘은 400 x 400 x 400이니까 6천 4백만 정도의 연산만 필요하다. 이 문제가 플로이드 워셜을 이용하면 된다는 걸 알고 나면 엄청 쉬운데, 그걸 알아챌 짬이 부족하다 /* 2020.12.24(목) */ import java.io.Buffe.. 2020. 12. 24.

이전 1 2 3 다음

티스토리툴바