공부공간

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제의 내용은 간단하다. -10억 ~ +10억에서 두점의 위치가 선으로 연결된 정보가 들어오는데.. 이를 빨간 화살표방향 (위에서) 보았을때 여러번칠해진거까지 감안해서 길이를 출력하는 문제이다. 두점 ( A,B )라 했을때 항상 Ao2[0]) { return 1; } else { return -1; } } }); int answer =0; int s = al.get(0..

https://www.acmicpc.net/problem/15812 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 맵의 모든 1의 개수가 정복되는 최소 시간을 구하는 것이므로 모든경우를 살펴야한다 ( 완전탐색 ) BFS를 이용하여, 1을 만날때마다 카운트를 증가시켜 전체의 1의 개수와 같아질때의 시간을 구한다. 모든경우의 수에서 최소시간이 정답이다 ! import java.io.BufferedReader; import java.io.IOException; import..

www.acmicpc.net/problem/11003 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 배열을 O(n)탐색하면서 현재 값보다 큰 값은 빼주고, index가 범위 밖에 있는것도 빼준다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWr..

www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 각 정점에서 최대거리 ( x + y = 1000칸 움직임 ) 에 편의점이있거나 현재 정점에서 페스티벌위치까지 갈수있는지 판단하기 위해서 재귀함수를 이용하여 매 정점을 체크해준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public st..

www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표 압축 (Coordinate Compress)은 말그래도 좌표를 압축하여 사용하는 것이다. 단독으로 이것만 나오지 않고 보통 세그먼트트리나 구현문제에서 좌표를 압축해도 문제상황이 달라지지 않는 경우에 사용한다. 배열을 정렬해주고 작은 값에 인덱스를0을 부여하며 증가시켜서 압축시키는 방식이다. 아래는 구현코드 hashmap을 이용하여 압축하였다. 배열을 써도될..

www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 수열에서 연속된 부분배열의 최댓값을 구하는 문제.. 양수면 계속더하면 최댓값이 되지만 중간에 음수가있는경우, 음수의 덧셈으로 0보다 크면 계속 더해준다. N^2 / NlogN의 풀이도 있지만, O(N)에 해결가능하다 package algorithm; import java.io.BufferedReader; import java.io.InputStreamRea..

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 클래스로 묶고 별자리 간 거리를 계산해서 우선순위 큐에 넣는다. 거리가 짧은 별자리들의 쌍이 항상 나오므로, 크루스칼 알고리즘으로 MST를 완성한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util...

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제집에서 순서가 존재하기때문에 차수를 고려한 위상정렬을 진행해준다. 다만, 문제 번호가 1-N 까지 문제중에서 차수가 0 이되었을때에 우선순위를 부여해야한다 ( 쉬운문제 부터 푼다 ) 따라서, 우선순위큐에 문제번호가 낮은 차수가 0 인 노드부터 처리해주자 import java.io.BufferedReader; import java.io.InputStreamReader; impor..