수학

[백준] 2436 - 공약수 (자바 Java)

[Gold V] 공약수 - 2436 문제 링크 성능 요약 메모리: 12872 KB, 시간: 108 ms 분류 브루트포스 알고리즘(bruteforcing), 유클리드 호제법(euclidean), 수학(math), 정수론(number_theory) 문제 설명 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다. 이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 예를 들..

[백준] 2225 - 합분해 (자바 Java) : DP

[Gold V] 합분해 - 2225 문제 링크 성능 요약 메모리: 13280 KB, 시간: 136 ms 분류 다이나믹 프로그래밍(dp), 수학(math) 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. dp는 항상 막막한데 점화식만 찾으면 쉽게 풀리는 것 같다 규칙이 있을까 해서 작은 경우의 수부터 하나하나 써봤는데 규칙을 찾을 수 있었다. dp[N][K..

[알고리즘] 비트 연산자 & 부분집합 (자바/Java)

비트 연산자 &둘 다 1 이면 1 / 해당 비트가 있는지 검사! System.out.println(3 & 5); // 3 = 011 // 5 = 101 // -------- // 001 -> 1 | 하나라도 1이면 1 System.out.println(3 | 5); // 3 = 011 // 5 = 101 // -------- // 111 -> 7 ^ XOR - 서로 다르면 1 System.out.println(3 ^ 5); // 3 = 011 // 5 = 101 // -------- // 110 -> 6 A >1); // 5 / (2^1) = 2 // 101 -> 010 = 2 부분집합 N개의 원소를 가진 집합에서 전체 부분집합의 개수 = 2^N 1. 재귀 부분집합은 공집합부터 원소가 1개, 2개, … ..

[백준] 4563 - 리벤지 오브 피타고라스 (자바/Java)

[Gold V] 리벤지 오브 피타고라스 - 4563 문제 링크 성능 요약 메모리: 12928 KB, 시간: 248 ms 분류 수학(math), 정수론(number_theory) 문제 설명 피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다. A2 + B2 = C2 세 변의 길이가 모두 자연수인 직각삼각형 중에 가장 유명한 삼각형은 아래와 같다. A = 12인 경우에는 다음과 같이 두 개의 직사각형을 찾을 수 있다. A가 주어졌을 때, 빗변의 길이 C가 자연수인 직각삼각형을 만드는 자연수 B (B > A)는 몇 개가 있을까? 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는..

[알고리즘] 기본 수학 - 순열 조합 중복순열 중복조합 (자바/Java)

순열/조합 순열, 조합, 중복 순열, 중복 조합을 dfs를 이용하여 구할 수 있다. 백준의 N과 M시리즈가 순열/조합을 공부하기 좋은 문제들이다. https://www.acmicpc.net/workbook/view/2052 1. 순열 순열은 N개의 수에서 R개의 수를 뽑아 순서대로 나열하는 것이다. {1, 2, 3, 4} 4개의 수에서 2개의 수를 뽑아 나열하는 경우의 수는 {1, 2} {1, 3} {1, 4} {2, 1} {2, 3} {2, 4} {3, 1} {3, 2} {3, 4} {4, 1} {4, 2} {4, 3} 의 12가지다. $$ nPr = n*(n-1) * ... (n-r+1) $$ 순열을 구하기 위해서는 dfs를 활용한다. static void dfs(int N, int M, int cn..