공부공간

https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net Long 범위에서 제곱근을 찾는다. sqrt의 결과를 두번곱한것이 입력된 숫자와 같다면 제곱근이고, 아니라면 +1한숫자를 리턴한다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 정렬된 두 배열이 문제 조건에 있다면, 투포인터 알고리즘을 의심해봐야 한다. 배열이정렬되어있으므로 앞쪽부터 두 배열을 비교하여 하나의 정렬된 배열을 만들어주자 같으면, 어느쪽을 먼저넣어도 상관없음이 보장된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

https://programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr i번째의 signs값이 true면 + 를 false면 -한 값을 더해준다. class Solution { public int solution(int[] absolutes, boolean[] signs) { int answer = 0; for(int i=0;i

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 특정한 수열의 숫자가 차례대로 주어질때에, 그 중간의 값을 계속 출력하면 된다. 두 가지 자료구조가 있다고생각하면 편하다, 항상 루트노드에 큰값이 오게 정렬되는 Max Heap과 반대인 Min Heap이 있다고 가정하면 이 둘을 붙였을때 온전한 수열이 된다고 생각한다. 그러면 중간값은 각 루트의 있는 값을 비교해서 선택하면 된다. 우선순위큐가 이러한 구조로 정렬되어있기때문에 사용하..

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..

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/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/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 모 기업 코딩테스트에서 출제되었던 문제이다. 배열의 앞,뒤로 탐색하면서 나보다 큰 벽을 만났을때, 그 중간 벽들과의 차이를 더해준다. 시간복잡도 O(2*500)으로 처리가능하다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 빗물 { publi..