https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 소인수분해에 관한 문제. 소인수분해를 하려면 일단 소수로 나눠야 해서 에라토스테네스의 체를 쓰려다가, 조금만 생각해보니 일단 2부터 나누고, 안나눠지면 1을 더해서 나눈다. 합성수로 나눠질수도 있다고 생각이 들었었지만, 애초에 2,3,5부터 나눠서 안나눠질때까지 나눠버리기 때문에 합성수가 끼어들 틈이 없다. #include int main () { int n; scanf("%d", &n); int a = 2; while (n != 1) { if (n % a == 0) { printf("%d\n", a); n /= a..
https://www.acmicpc.net/problem/15829 15829번: HashingAPC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정www.acmicpc.net자료형에 바이트가 정해진건 정말 귀찮다. 그냥 다 더하고 마지막에 나누면 오버플로우가 나게 된다. 이걸 어떻게 해결하지 하다가 포기했던 문제인데, 나머지 연산(모듈러 연산)법칙에 관해 알게되어 어찌저찌 풀게 되었다. 나머지 연산의 법칙중 분배법칙을 이용해서 풀면 된다.이중 1번째와 3번째를 이용하게 된다. 덧셈에 관한 증명은 여기서(https://sexycoder.tistory.com/66) 여기까지..
https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 말은 번지르르하지만 결국 두 원의 위치관계를 묻는 문제. 다만 두 원의 위치관계인 만큼 외접할 때만 따지는 것이 아니라 내접할 때도 따져야 한다. 내접을 까먹었다가 꽤 고생했다. 두 원의 위치관계는 구글에게 물어보자. #include int powi (int a, int exp) { int result = 1; for (int i = 0; i < exp; i++) { result *= a; } return result; } int main () { ..
https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 비유클리드 기하학인 택시기하학에 관한 문제. 이 문제는 풀이가 어려운 것이 아닌 택시기하학에 관한 이해가 먼저인 문제이다. 백준에 올라온 설명만 가지고는 솔직히 무슨말인지 잘 몰랐다. 그래서 따로 조사하고 나서야 이해가 갔다. 유클리드 기하학의 좌표계에서는 두점(a1, b1)과 (a2, b2)사이의 거리는 다음과 같이 구해진다. 하지만 택시기하학에서는 다음과 같이 정의한다. 수평거리 + 수직거리인 셈이다. 이 문제에서는..
https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 범위 내의 소수들의 합과, 그 소수들중 최솟값을 출력하는 문제. 역시 에라토스테네스의 체 가져다가 복붙하니 끝났다. 단, M=1, N=2일때를 주의해야 한다. #include #define MAX_SIZE 10001 int main () { /* 에라토스테네스의 체 */ int seive[MAX_SIZE] = {0,}; // 0부터 시작 for (int i = 2; i < MAX_SIZE; i++) { se..
https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 범위가 엄청나게 큰 수의 합을 출력하는 문제. 내부적으로 엄청 큰 숫자를 자동으로 처리해주는 파이썬이지만, 솔직히 C로 풀 자신이 없어서 일단은 python으로 풀었다. 근데 이거 C로는 어떻게 풀지...... a, b = map(int, input().split()) print(a+b)
https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 3개의 점이 주어졌을 때, 수평, 수직축에 평행한 직사각형을 만들기 위한 4번째 점을 찾는 프로그램. 축에 평행하지 않은 경우를 고려하게 했다면 문제가 더 어려워졌을지도 모른다. 그냥 단순히 x축, y축의 값의 종류가 2개씩 나오면 되므로 1개만 나온 값을 찾아준다. #include int main () { int arr[6];/* x1, y1, x2, y2, x3, y3 */ int x, y; for (int i = 0; i < 6; i++) { scanf("%d", &arr..
https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 낮에 a만큼 올라가고 밤에 b만큼 미끄러지는 달팽이가 높이 v만큼의 막대를 며칠만에 올라가는지에 관한 문제. 시간제한이 꽤 짧아 당황했다. 처음에는 그냥 반복문으로 풀려고 했지만, 시간제한에 걸려 결국 시간초과로 오답. 그래서 어떻게 하지 하다가 관계식을 도출해서 풀어버렸다. 올라가는데 n일이 걸린다고 하자. 그렇다면 달팽이는 a만큼 n번 올라가고 b만큼 n-1번 미끄러질 것이다. 이 식을 정리하면 다음과 같이 정리된다. 이때 (v-b)/(a-b)가 나누..
