알고리즘
[BOJ] 2981 검문
문제 링크 https://www.acmicpc.net/problem/2981 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제는 주어진 수들 간의 차를 전부 구한 뒤, 그 값들의 최대 공약수의 약수를 구해주면 풀 수 있다. 이런 방식으로 답을 구할 수 있는 이유를 알아보자. 주어진 수들을 크기 순으로 나열했을 때, 각각의 수들을 x0, x1, x2, ... ,xn이라 하자. 각각의 수들은 임의의 수 m으로 나눴을 때 모두 동일한 나머지 k를 가지므로 다음과 같이 표현할 수 있다. x0=a0*m+k x1=a1*m+k x2=a2*m+k . . . xn=an*m+k (a0, a1, ... , an : x0부터 xn을 m으로 나눴을 때의 몫) xn과 x0의 차는 (an-a0) * m으로 나타낼 수 있다..
[BOJ] 3944 나머지 계산
문제 링크 https://www.acmicpc.net/problem/3944 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제는 입력받은 모든 자릿수를 더하고, 이를 b-1로 나눈 나머지를 구하면 답을 구할 수 있다. 자세한 식 도출 과정은 다음과 같다. 123456(7) mod 6을 예로 들어보자. 123456(7)을 10진수로 변환하면 1 * 7^5 + 2 * 7^4 + 3 * 7^3 + 4 * 7^2 + 5 * 7^1 + 6 * 7^0 이다. 이 수에 mod 6을 하면 모듈러 연산의 분배법칙을 이용하여 (1 * 7^5) mod 6 + (2 * 7^4) mod 6 + (3 * 7^3) mod 6 + (4 * 7^2) mod 6 + (5 * 7^1) mod 6 + (6 * 7^0) mod 6 ..
[BOJ] 2003 수들의 합 2
문제 링크 https://www.acmicpc.net/problem/2003 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제는 모든 경우의 수를 생각하면서 풀면 O(N^2)의 시간 복잡도가 나오게 된다(시작지점 0~N, 도착지점 0~N까지 움직이면서 경우의 수를 푸는 경우). 문제의 제한 시간이 0.5초이고 N이 최대 10000까지 나올 수 있으므로 이렇게 구하면 시간 제한에 걸릴 수 있다. 좀 더 시간 복잡도가 작은 방법이 필요하다. 수열의 처음 값을 가지고 있는 변수 sum을 생각해보자. i를 1부터 N까지 증가시키면서 sum에 A[i]의 값을 더한다. 더한 값이 M과 동일하다면 경우의 수를 1 늘려주고, M보다 크다면 sum 값이 M보다 작아질 때까지 가장 마지막에 더한 값부터 차례대로 ..