본문 바로가기

전체 글105

오일러 𝜑(피 또는 파이) 함수, 서로소 개수 구하기 서로소란 1 을 제외하고 공약수가 없는 두 수의 관계입니다. 오일러 피함수 φ(n)은 n이하의 자연수 중 n과 서로소인 자연수의 개수를 의미하는 함수입니다. 예를 들어 φ(6)은 2로 1과 5의 서로소가 있음을 의미합니다. 모든 자연수는 소수들의 (prime) 곱으로 표현 할 수 있습니다. 예를들어 16은 2^4 로 표현할 수 있고 15는 3^1 * 5^1 로 나타낼 수 있습니다. φ(16)은 2, 4, 6, 8, 10, 12, 14, 16을 제외한 나머지 자연수와 서로소입니다. 여기서 알 수 있는 사실은, 자연수를 구성하는 소수들의 배수는 전부 서로소가 아닙니다. 즉, φ(16) = 16 - (16/2) = 8개로 구할 수 있습니다. ( n 이하의 k의 배수의 개수는 n/k로 구할 수 있습니다, 나머지.. 2020. 8. 13.
[BOJ] 백준 1028번: 다이아몬드 광산 https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net R, C 가 750으로 (i, j) 좌표에서 우측 하단으로의 대각선 길이 DP[i][j][0], 좌측 하단으로의 대각선 길이 DP[i][j][1], 좌측 상단으로의 각선 길이 DP[i][j][2], 우측 상단으로의 대각선길이를 구해놓고 모든 좌표에 대하여 O(R*C*750*4)의 복잡도로 가능한 다이아몬드 크기를 구할 수 있습니다. (시간초과가 날것 같지만 가지치기를 통해 충분히 시간을 줄일 수 있습니다.) #include #include #i.. 2020. 8. 12.
[BOJ] 백준 1027번: 고층 건물 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)�� www.acmicpc.net 기울기를 이용한 문제입니다. ccw 알고리즘을 이용하여 세점의 방향성으로도 풀 수 있습니다. 여기 참고 n; for (int i = 0; i > a[i]; } for (int i = 0; i -1; j--) { if (j .. 2020. 8. 12.
[BOJ] 백준 1026번: 보물 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거� www.acmicpc.net B를 재배열하지 말라고 하지만, 그 말을 듣지 마세요. #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, a[51],b[51]; cin >> n; for (i.. 2020. 8. 12.

티스토리툴바