BOJ

[BOJ/JAVA] 2960번: 에라토스테네스의 체

2960번: 에라토스테네스의 체에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.https://www.acmicpc.net/problem/2960키워드2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.구현..

[BOJ/JAVA] 1822번: 차집합

키워드집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램구현집합 연산 중 차집합 연산을 이용하여 구현한다.A.removeAll(B)A집합에는 속하지만, B집합에는 속하지 않게 A를 바꾼다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Set; import java.util.StringTokenizer; import java.util.TreeSet; public class java_1822 { static Set aSet, bSet; public static void main(String[] args) throws IOExcepti..

[BOJ/JAVA] 2110번: 공유기 설치

2110번: 공유기 설치도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.https://www.acmicpc.net/problem/2110키워드집에 공유기 C개를 설치가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치구현huses[] 각 집의 좌표를 오름차순으로 정렬한다.solution()인접한 두 공유기 사이의 거리를 매개변수로 이분탐색을 진행한다.초기 low는 1초기 high는 마지막원소 - 첫번째 원소 (이 때가 차이가 가장 크므로..)[low, high]에 속하면서, mid = (lo..

[BOJ/JAVA] 2343번: 기타 레슨

키워드블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.M개의 블루레이에 모든 기타 강의 동영상을 녹화하블루레이의 크기(녹화 가능한 길이)를 최소M개의 블루레이는 모두 같은 크기구현블루레이 크기를 매개변수로하여 이분 탐색을 진행한다.lectures[]강의의 누적합low = 가장 긴 길이의 강의high = 모든 강의 길이의 합canMake()mid = (low+high)/2 의 블루레이 크기로 녹화할 수 있는지 체크0부터 누적합을 계산하며 진행한다. mid보다 커지는 순간 → 현재 인덱스의 강의를 제외한 이전 강의를 현재 블루레이에 담는다.마지막 인덱스가 아닌데, 블루레이의 수가 M이상이라면 .. false 반환반복문이 끝난 경우 → 디스크가 남는 경우디스크의 크기는 항상 한 개의 강의를 넣을만큼 충분..

[BOJ/JAVA] 23631번: 진심 좌우 반복뛰기

키워드위치 x = 0에서 시작하여, 처음에는 오른쪽으로 Km를 뛴 다음 방향을 바꾼다.방향을 바꿀 때마다 이전에 움직인 거리에 Km만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.정확히 (N - 1)m만 뛸 것구현다음을 정의하자. 전부 뛴다 → 해당 뛰여야할 길이만큼을 전부 뛴다.n전부 뛴 횟수전부 뛸 수 있는 n값을 구한다.low = 0high = 5000(5000)(5000+1)/2 ≥ 10,000,000 이므로 5000을 상한선으로 정했다.n을 매개변수로 하여, 이분 탐색으로 진행한다.숫자가 매우 크므로, java에서는 BigInteger를 활용한다.n번째에서 전부 뛰었을 때 위치는 다음과 같다.이동 횟수좌표1K2-K32K4-2K53K6-4K위 표에서 알 수 있듯이 이동횟수를 보면, 좌표를 알아낼 수 ..

동적 계획법

동적 계획법이 뭔데?분할 정복에서 중복 부분문제를 캐시(cache)를 이용하여 계산 결과를 재활용하여 속도 향상을 꾀하는 기법이다.예시피보나치 수열의 [i]번째 결과값을 출력하고싶다고 하자.해당 메소드는 fibo(i)를 이용하여 값을 얻는다.int fibo(int i){ // 기저사례 if(i == 0 || i == 1){ return 1; } if(cache[i] != -1){ return cache[i]; } cache[i] = fibo(i-1) + fibo(i-2); return cache[i]; }초기 cache 상태는 다음과 같다.fibo(4)는 fibo(3) + fibo(2) 연산이 이루어진다.fibo(3)에서는 fibo(2) + fibo(1) 연산이 이루어진다.fibo(2)에서는 fibo(1..

[BOJ/JAVA] 9019번: DSLR

키워드D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.구현각 4가지 동작 방식을 구현한다.이후 너비우선 탐색을 이용하여 한 ..

[BOJ/JAVA] 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다! 세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다. 정보섬 2층은 A n×m의 격자로 표현된다.https://www.acmicpc.net/problem/17129키워드정보섬 2층은 A[n][m]의 격자로 표현어떤 A[i][j]가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다.윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다.현..

[BOJ/JAVA] 13023번: ABCDE

13023번: ABCDEhttps://www.acmicpc.net/problem/13023키워드오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성구현한 노드에서 다른 노드로의 최대 거리를 구하는 문제이다.깊이 우선 탐색을 이용하여 구현한다.최대 거리가 4 이상이면 위와 같은 친구관계가 존재하는 것이고 그렇지 않으면 존재하지 않는다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.uti..

[BOJ/JAVA] 4803번: 트리

4803번: 트리입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다.https://www.acmicpc.net/problem/4803키워드트리는 사이클이 없는 연결 요소트리는 정점이 n개, 간선이 n-1개임의의 두 정점에 대해서 경로가 유일그래프가 주어졌을 때, 트리의 개수를 세는 프로그램구현DisjontSet을 이용하여 트리인지를 판단하였다.cycle[]해당 노드가 사이클에 속하는지 판단하는 배열★merge★ :: 핵심 메소드두 노드..