Algorithm/수학&기타
-
[Java]누적 합(Prefix Sum , Cumulative Sum)Algorithm/수학&기타 2021. 4. 22. 13:46
*누적 합(Prefix Sum, Cumulative Sum) -> 누적 합이란, 말 그대로 나열된 수의 누적된 합을 말한다. -> 조금 더 엄밀히 말하면, 수열 An에 대해서, 구간 [1, 1]의 합, 구간 [1, 2]의 합, 구간 [1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다. ※ 따라서 Prefix Sum의 각 요소는 해당 해당 인덱스까지의 부분 합(Partial Sum)을 의미한다. 부분 합은 급수에서 말하는 그 부분합의 의미가 맞다. *누적 합의 사용 -> 누적 합은 그 목적에 따라 다양한 문제에 활용이 가능하다. -> 대표적으로 누적 합을 사용하는 문제는 카운팅 정렬(Counting Sort), 구간 합 구하기가 존재한다. *단순 반복을 이용한 구간 합 구하기 -> 이 글의..
-
[Java]거듭 제곱의 계산Algorithm/수학&기타 2021. 4. 20. 17:17
*거듭 제곱의 계산 -> 거듭 제곱을 구현하는 방법은 간단하다. 기본적으로는 그 정의 그대로 어떤 수를 n번 곱하여 거듭제곱을 구현 가능하다. 하지만 n번 곱하기 때문에 시간복잡도는 O(n)이 걸린다는 것을 알 수 있다. *개선된 거듭 제곱의 계산 -> 이러한 거듭 제곱은 분할 정복을 기반으로 시간복잡도를 O(logN)까지 줄일 수 있다! -> 기본적인 아이디어는 다음과 같다. 예를 들어 5^10을 계산한다고 생각하였을 때, 아래와 같은 과정을 거쳐서 그 값을 구하는 것 이다. -> 따라서, 재귀를 이용하여 다음과 같은 거듭제곱을 구현할 수 있음을 알 수 있다. *구현 -> 점화식도 구하였으니 그대로 구현하기만 해주면 된다. import java.util.Scanner; public class Expon..
-
페르마의 소정리(Fermat's Little Theorem)Algorithm/수학&기타 2021. 4. 20. 00:36
*페르마의 소정리(Fermat's Little Theorem) -> 우선 페르마의 소정리를 활용하기 위해서는 기본적으로 모듈러 산술(연산)과 합동식에 대한 이해가 선행되어야 한다. 다음 포스팅을 참고하도록 하자. sskl660.tistory.com/75 모듈러 산술(Modular Arithmetic) *모듈러 산술(Modular Arithmetic) -> 모듈러 산술(모듈러 연산)은 정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법을 말한다. -> 쉽게 말해 나머지를 이용한 산술 연산이라고 생 sskl660.tistory.com -> 페르마의 소정리는 특정한 상황에서 어떤 수의 나머지를 빠르게 구할 때 사용이 가능하다. 특정한 상황은 아래 정리를 참고하도록 하자. 쉽게 말해 a^(p -..
-
모듈러 산술(Modular Arithmetic)Algorithm/수학&기타 2021. 4. 19. 23:54
*모듈러 산술(Modular Arithmetic) -> 모듈러 산술(모듈러 연산)은 정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법을 말한다. -> 쉽게 말해 나머지를 이용한 산술 연산이라고 생각하면 된다. 사칙 연산과 마찬가지로 정수의 나머지에도 연산과 관련된 개념이 존재한다. -> 모듈러 연산은 정수론, 컴퓨터 과학의 보안 등 여러 분야에서 유용하게 사용될 수 있다. 알고 있다면 알고리즘 문제에서 몇몇 연산을 편하게 할 수 있는 방법을 생각하는 기반이 될 수 있다. 모듈러 연산 자체를 응용한 문제는 그렇게 많지 않지만, 이를 기반으로한 수학적 개념(정수론)의 기반이 되기 때문에 이해해두도록 하자. *모듈러 산술 연산과 합동(Congruent) -> 모듈러 산술 연산 : 쉽게 말해 ..
-
[Java]유클리드 호제법(Euclidean Algorithm)Algorithm/수학&기타 2021. 4. 19. 18:16
*유클리드 호제법(Euclidean Algorithm) -> 유클리드 호제법은 두 개의 자연수 or 두 개의 다항식의 최대공약수를 구하는 방법이다. ※ a는 b의 피제수(즉, 나누어지는 수)이므로 a > b이다. ※ 따라서 수식의 q는 몫, r은 나머지를 의미한다(따라서 r은 0보다 같거나 크고 b보다는 작아야 한다). -> 유클리드 호제법은 최대공약수를 구하는데 사용한다고 하였다. 최대공약수는 수학적으로 두 수의 모든 약수를 나열한 뒤 공통되는 약수 중 최대를 선택하거나 소인수 분해를 이용한 방법이 있지만, 유클리드 호제법을 이용하면 더 빠른 시간 안에 최대공약수를 구할 수 있다. *유클리드 호제법의 사용 -> 피제수가 제수에 의해 나누어 떨어진다면, 그 피제수와 제수의 최대공약수는 제수이다. 이 명제..
-
[Java]좌표 이동/탐색Algorithm/수학&기타 2020. 9. 25. 21:21
*좌표 이동/탐색 -> DFS/BFS 문제를 접하다 보면, 좌표의 성질을 갖는 대상의 원소에서 다른 원소로 이동하거나, 그 주변을 탐색해야하는 로직이 빈번하게 사용된다. *2차원 배열 좌표와 행렬 -> 2차원 배열의 인덱스별 값이 생기는 위치를 시각화하여 생각해보면 평면을 떠올릴 수 있고, 평면은 일상 생활에서 보통 좌표를 이용하여 나타낸다. -> 일반적으로 수학에서 좌표의 1사분면은, 다음과 같은 모양을 가진다. 즉, x값이 증가할수록 오른 쪽으로 이동하고, y값이 증가할수록 위 쪽으로 이동하는 구조를 가진다. 그렇지만, 일반적으로 2차원 배열을 형성하는 경우 인덱스 별 값이 생기는 위치는 논리적으로 좌표 평면 1사분면의 구조처럼 평면이 만들어지지 않는다. -> 2차원 배열을 형성하는 경우는 다음과 같..