수학

문제 설명직사각형의 변 위에 여러 모양의 점이 있고, 같은 모양의 점은 정확히 두 개씩 있다. 단 직사각형의 꼭짓점에 놓인 점은 없다. 이제 같은 모양의 두 점을 직선이나 곡선으로 연결하려고 한다. 연결된 선은 반드시 직사각형의 내부만을 지나야 하며, 세 개 이상의 연결선이 한 점에서 만나서는 안 된다. 연결선과 연결선이 만나는 교차점의 개수를 가장 작게 하려고 할 때 최소 교차점의 개수를 구하는 프로그램을 작성하시오.예를 들어, 점이 아래 그림과 같이 주어졌다고 하자. 각 점의 위치는 두 개의 양의 정수로 표시된다. 첫째 정수는 점이 위치한 변을 나타내는데, 1은 윗변, 2는 밑변, 3은 왼쪽 변, 4는 오른쪽 변을 의미한다. 둘째 정수는 변 위에서의 위치를 나타낸다. 점이 윗변이나 밑변에 있는 경우는..

최대공약수와 최소공배수를 구하는 문제이다. 선형적인 탐색법으로 작은 수전까지 하나씩 나누어 보고 둘 다 나누어 떨어지는 수 중 가장 큰 수를 구하면 되겠지만, 다른 수학적인 방법을 이용하여 최대공약수를 구한 뒤 그를 이용하여 최소 공배수까지 구하는 방법이 있다. 임의의 수 a, b가 있다 가정하자. (단, a > b) a를 b로 나누면 몫과 나머지가 있을 것이다. 그러면 그 나머지로 나누는 수 (b)를 또 나눈다. 이를 반복하다 나누는 수 (b)가 0이 되면 나누어지는 수 a를 return 한다. 그림을 보면 x가 최대공약수라 할 때, a = 8x b = 3x a% b = 2x이다. 우리는 x를 구해야 하기 때문에, 나머지가 0이 될 때, 즉 모든 수가 나누어 떨어질 때까지 계속해서 b를 나머지로 나눈다..

정답 비율이 40%라 도전해봤는데 문제가 짧아서 당황했다. 문제를 읽어보니 문제 제목과 똑같이 입력받은 수로 어떠한 수를 나누었을 때 몫과 나머지가 같은 수들의 합을 구하면 되는 간단한 문제였다. 이런 문제 정답 비율이 왜 이렇게 낮을까 생각하고 문제 풀이를 시작했다. 입력받은 수를 n이라 했을 때 어떠한 수를 나누는 상황에서 나머지가 생기는 경우는 n-1가지의 경우이다. ( 나머지는 나누는 수 보다 무조건 작고, 1~n-1까지의 수이다. ) 이러한 원리로 1부터 n-1까지 어떠한 수의 몫과 나머지가 같은 수를 만들어 더해주면 될 거라 생각했다. 아래는 처음에 작성한 Java 코드이다. import java.util.Scanner; public class SameMod { public static voi..

초등학교 수학 문제에서 많이 봤던 문제이다. 낮에 이동하고 밤에 미끄러지기 때문에 낮에 이동했을 때 목표 거리와 비교한 뒤 만족하지 않았다면 미끄러진 높이를 계산하는 계산을 반복하면 되는 문제라고 생각했다. 하지만 결과는 시간 초과... 그래서 다음엔 배열을 이용해 봤다. 배열일 연산이 제일 빠르기 때문에 시간 초과 문제를 해결할 거라 생각했다. 낮에 이동한 거리의 배열과 미끄러진 후의 거리 배열을 생성하여 낮에 이동한 거리가 목표 높이에 도달하기까지 반복하여 index를 출력하면 될 줄 알았다. 하지만 이번에는 메모리 초과.... 한참 고민하다 해답이 떠올랐다. 결국 마지막에는 앞으로 이동을 해야 하기 때문에, 앞으로 가는 거리를 목표 높이에서 뺀 뒤 실제로 이동하는 거리(앞 - 뒤)로 나누어 주면 정..

연속되는 수 중 가장 큰 합을 찾아내는 문제이다. DP로 간단하게 해결 가능하다 배열에 수들을 저장해 해당하는 index의 수가 선택되었을 경우, 이전까지의 합과 index의 요소 중 큰 수를 골라 저장하며 풀어 나간 뒤 가장 큰 수를 찾아 출력하면 된다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class continuitySum { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); //수 배열 int[] arr = new int[num]; //큰 수 저장 배열 int[] solution = new int[num..

입력받은 숫자 중 소수가 몇 개인지 찾아내는 문제이다. 기본적인 문제 풀이 개념은 다음과 같다. 어떠한 수를 n이라 하자. 만약 n이 소수라면 n의 제곱근 이하의 어떠한 수로도 나누어 떨어지지 않는다. 약수는 제곱근을 기준으로 대칭적인 성질을 갖기 때문이다. n까지의 소수를 모두 세는 방법은 O(n^2)의 시간 복잡도를 갖지만 이 규칙을 사용하면 O(nlogn)까지 줄일 수 있다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class primeNumber { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); //수 ..