공부방

주어진 수들을 조합하여 3장의 카드를 골라 합이 m에 가장 근접하게 하는 문제이다. 이 문제는 선택정렬을 이용하여 풀면 간단하게 해결할 수 있다. 흔히 최소값, 최대값 또는 오름차순정렬 등을 할 때 많이 사용되는 선택정렬은 1회전에서 1번 원소를 2번 원소부터 시작해 3,4 ... n번째 원소까지 비교하고 2회전에서 2번 원소를 3번 원소부터 시작해 4,5 ... n번째 원소까지 비교하는 방식이다. 이 선택정렬을 이용한다면 1~5까지의 수 중 2개를 뽑아내어 만들 수 있는 순서쌍을 구할 수 있다. 예시를 보자 int[] a = { 1, 2, 3, 4, 5 }; for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { Sys..

두개의 좌표 (x1, y1) (x2, y2) 와 이 두 좌표로부터의 거리 r1, r2가 주어질 때 임의의 점 a (a, b) 가 존재할 수 있는 좌표의 수를 출력하는 문제이다. 계산을 편하게 하기 위해 두 점사이의 거리를 저장해두는 변수를 만들어준다. int dis2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); 제곱근을 구하려면 Math함수를 사용해야 하므로 피타고라스 공식을 이용하여 거리의 제곱을 저장해두자. 먼저 두 점과 r1, r2 가 일치할 때에는 a가 존재할 수 있는 좌표의 수는 무한대가 된다. if (x1 == x2 && y1 == y2) { if (r1 == r2) { System.out.println(-1); } } 때문에 위와 같이 이 경우의 수..

택시 기하학에서 두 점 사이의 거리가 위 조건과 같을 때, 주어진 반지름을 가진 원의 넓이를 구하는 문제이다. 언뜻 보면 복잡해 보이는 문제이지만 간단하다. 원의 정의가 유클리드 기하학과 같기 때문에 먼저 택시 기하학에서 두 점 사이의 거리가 같은 점들을 구해본다. 예를 들어 반지름이 1일 경우 유클리드 기하학에서 원은 다음과 같이 표현할 수 있다. 하지만 택시 기하학에서는 두 점사이의 거리가 |x1 - y1| + |x2 - y2| 이므로 이 거리가 1이 되는 순서쌍에는 (1, 0) (0.5, 0.5) (0, 1) (-0.5, 0.5) ... 등이 있다. 이를 그림으로 나타내보면 다음과 같다. 즉 택시 기하학에서 반지름이 r인 원 (한 점으로부터 거리가 같은 점들의 집합) 의 넓이는 대각선이 2*r 인 ..

피타고라스의 정리를 이용하여 직각삼각형인지 아닌지를 판별하는 문제. 매우 간단하다. a, b, c 값을 입력 받은 후 𝑎² = 𝘣² + 𝘤² 를 만족하는지만 확인하면 된다. 먼저 a, b, c 값이 0이라면 반복문이 종료되므로 break문을 이용해 0을 입력받으면 빠져나갈 수 있게 해 둔다. if (a == 0 && b == 0 && c == 0) break; 그 후 a, b, c 중 어떤 값이 대각선인지 모르기 때문에 if문을 활용하여 3가지의 경우로 나눈다 a가 대각선이라면 𝑎² = 𝘣² + 𝘤² b가 대각선이라면 𝘣² = 𝑎² + 𝘤² c가 대각선이라면 𝘤² = 𝑎² + 𝘣² 가 되겠다. 이를 코드로 작성해보면 다음과 같다. import java.util.Scanner; public class Ba..

세 점을 입력받고 축에 평행한 직사각형을 만들기 위해 마지막 한 점을 구하는 문제이다. 먼저 각 점들의 x, y 좌표를 나누어 입력받는다. int ax, ay, bx, by, cx, cy; ax = sc.nextInt(); ay = sc.nextInt(); bx = sc.nextInt(); by = sc.nextInt(); cx = sc.nextInt(); cy = sc.nextInt(); 축에 평행한 직사각형을 만들기 때문에 위 세 점은 각각 x좌표나 y좌표가 하나씩은 일치하는 부분이 있다. 따라서 네 점을 구했을 때 같은 x좌표가 같은것이 2개, y좌표가 같은것이 2개씩 있어야 한다. 이를 이용해 if문을 사용하여 코드를 작성해보면 다음과 같다. import java.util.Scanner; publ..

임의의 짝수 n에 대해 소수 2개의 합으로 n을 나타내는 골드바흐 파티션을 구하는 문제이다. 먼저 주어진 범위 10000만큼의 배열을 만들어 에라토스테네스의 체를 이용해 소수를 구해놓는다. int[] a = new int[10001]; int check = 0; for (int i = 2; i

위와 같은 조건을 가진 아파트에 a층 b호에 사는 사람의 수는 몇명인지 구하는 문제이다. a층의 b호에는 a-1층의 1호부터 b호까지 거주하는 사람들의 수의 합 만큼의 사람이 살고 있다. 이를 숫자로 나열해보면 0층 : 1 2 3 4 5 ... 1층 : 1 3 6 10 15 ... 2층 : 1 4 10 20 35 ... 3층 : 1 5 15 35 70 ... 4층 : 1 6 21 56 126 ... ... 이 될 것이다. 먼저 k와 n을 입력받고 이 범위만큼의 2차원 배열을 생성한다. int k, n; k = sc.nextInt(); n = sc.nextInt(); int[][] a = new int[k + 1][n + 1]; 배열은 0부터 시작하고, 이 아파트에는 0층이 있으므로 k+1, n+1 만큼의..

n보다 크고 2n보다 작거나 같은 소수의 개수를 구하는 문제이다. 소수는 자기 자신과 1로만 나누어지는 수이므로 다음과 같이 구할 수 있겠다. for (int i = n + 1; i

삼각형을 이어붙여 다음 삼각형의 변의 길이를 구하는 문제이다. 규칙을 찾아보면 처음 P(1), P(2), P(3)은 1로 고정이고 그 다음부터 P(n-2)+P(n-3) = P(n) 이 되는것을 알 수 있다. 재귀함수를 사용하여 다음과 같이 나타낼 수 있다. 다만 이렇게 만들게 된다면 큰 수를 표현할 때 시간이 엄청 오래걸리게 된다. 예를 들어 80번째의 수를 구하기 위해서는 78, 77 번째의 수를 구해야 하는데 이때 각 78 77번째의 수를 구하기 위해서는 또 75 76, 74 75번째의 수를 구해야 하고 ... 이런식으로 수없이 많은 계산을 반복해야 한다. 이 시간을 줄이기 위해 배열을 생성하여 배열에 각 값들을 저장해 두게 되면 반복되는 계산이 줄어들게 되므로 시간이 단축되는 효과가 있다. 이처럼 ..

V높이의 나무를 하루에 A만큼 올라가고 B만큼 미끄러지면서 얼마만에 꼭대기에 도달하는지 찾는 문제. 보기엔 얼핏 간단해 보이나 시간 제한(0.15초)가 걸린다. 간단히 작성해 보았다. a b v 는 주어진 보기와 같고 ht 는 달팽이의 현재 위치, 그리고 count는 날짜를 세는 용도이다. 날이 밝았을 때 a만큼 올라간 후 현재위치(ht)를 목표위치(v)와 비교하여 도달하면 반복문을 빠져나오고, 도달하지 못한다면 밤이되어 b만큼 미끄러지는 식으로 작성하였으나 결과는 역시 시간 초과. 따라서 변수를 더 추가한 후 간단히 구할 방법을 생각해보았다. 달팽이가 하루에 올라가는 높이를 구한 후 전체 높이에서 나눈다면 간단히 몇일이 걸리는지 알 수 있다. 다만 단순히 v / (a-b) 를 하게 된다면 100 99 ..