https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 골드바흐의 추측을 구현하는 문제. 언제나 그렇듯 에라토스테네스의 체를 범위에 맞게 만든 후에, 조건에 맞는 골드바흐 파티션을 찾으면 된다. 파티션이 여러개 존재하는 경우 그 차이가 제일 적은 파티션을 출력해야 하는데, 이를 어떻게 처리할까 하다가, 처음부터 주어진 수의 절반값에서 시작하여 그 차이를 벌려가다가 파티션이 발견되면 끝내는 방식으로 접근하면 됐다. #include i..
https://www.acmicpc.net/problem/2914 2914번: 저작권 창영이는 노래 여러 개를 이어서 부르는 가수이다. 유명한 노래의 비슷한 멜로디를 이어서 부르면서 언제 곡이 넘어갔는지 모르게 만드는 것이 창영이 노래의 특징이다. 이런 노래로 상업적으 www.acmicpc.net 올림된 평균값과 개수가 주어졌을때 총 저작권수의 최솟값을 구하는 문제 아니 왜 저작권을 침해해서...... 입력이 소수로 된 평균값을 올린 값이 들어오는데, 원래의 평균은 (입력된 평균 - 1) ~ (입력된 평균)사이에 있는 값이기 때문에 저작권수의 최솟값은 다음과 같이 구하면 된다. 개수 x (입력된 평균 - 1) + 1 이제 이를 코드에 적용하면 된다. #include int main () { int n, ..
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번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 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://programmers.co.kr/learn/courses/30/lessons/68935?language=cpp 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr cpp 데뷔전(?)이다. 근데 문법을 모르니 상대적으로 난이도가 많이 올랐다...... C로 푼것과 거의 비슷하게 풀었다. #include #include #include using namespace std; int solution(int n) { int answer = 0; vector ar..
https://programmers.co.kr/learn/courses/30/lessons/68935?language=c 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 자연수 n을 3진수로 변환한 후에 그 3진수를 뒤집고, 다시 10진수로 변환하는 문제. 처음부터 저장할때 뒤집어서 저장한 후에 10진수로 변환하면 된다. #include #include #include int solution(int n) { int answer = 0; int len = 0; in..
https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 비유클리드 기하학인 택시기하학에 관한 문제. 이 문제는 풀이가 어려운 것이 아닌 택시기하학에 관한 이해가 먼저인 문제이다. 백준에 올라온 설명만 가지고는 솔직히 무슨말인지 잘 몰랐다. 그래서 따로 조사하고 나서야 이해가 갔다. 유클리드 기하학의 좌표계에서는 두점(a1, b1)과 (a2, b2)사이의 거리는 다음과 같이 구해진다. 하지만 택시기하학에서는 다음과 같이 정의한다. 수평거리 + 수직거리인 셈이다. 이 문제에서는..
