https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 두수의 최대공약수와 최소공배수를 구하면 되는 문제. 최소공배수는 두수의 곱을 최대공약수로 나누면 되니 최대공약수만 구하면 된다. #include int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } int main () { int a, b, temp; scanf("%d %d", &a, &b); temp = gcd(a, b); printf("%d\n%d", temp, a*b/temp);..
https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 분명 2750번보다 시간제한이 더 널널한데도 같은 퀵정렬 알고리즘으로 풀리지 않는걸 보니 테스트케이스가 난리가 났나보다. 단계별 풀이에서는 내장 정렬을 사용하는걸 추천한다고 했으니 내장정렬을 써보자. https://dojang.io/mod/page/view.php?id=638 를 참조했다. #include int compare(const void *a, const void *b) // ..
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 퀵정렬로 풀었다. 최악의 시간복잡도가 O(n^2)인데 통과한걸 보니 테스트케이스가 좀 양심이 있었나보다. #include #include void quick_sort (int * arr, int start, int end) { int pivot = arr[(start + end) / 2]; /* 오름차순 */ int i = start, j = end; int temp; do { while (arr[i] <..
https://www.acmicpc.net/problem/1356 1356번: 유진수 첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다작거나 같은 자연수이다. www.acmicpc.net 유진수란 10진수 정수에서 두 부분으로 나누어 각각의 자리수를 곱했을 때 둘이 같은 수일 때 유진수라고 한다. 예를들어 1236은 123 / 6으로 나누면 6으로 같기 때문에 유진수이다. 또한 1221도 유진수이다. 하지만 1234는 유진수가 아니다. 이 문제를 풀면서 간과했던 한가지가, 한자리 숫자는 유진수로 취급하지 않는다는 것이다. 이를 몰라서 왜 틀렸지 하다가 계속 틀렸다. #include #include int main () { char ch[11]; int len; int n1, n2; in..
https://programmers.co.kr/learn/courses/30/lessons/12922 코딩테스트 연습 - 수박수박수박수박수박수? 길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다. 제한 programmers.co.kr 길이 n의 문자열에서 수, 박을 반복하는 문자열을 반환해야 하는 문제. 리턴할 문자열을 동적할당해야하는데, 무작정 sizeof(char) * n만큼 할당하면 끝없는 맞왜틀의 굴레에 빠진다. 한글은 영어와 다르게 한 글자임에도 여러바이트를 차지한다. 이는 컴파일러에 따라 차이가 있는데 msvs의 경우 2바이트, gcc의 경우 ..
https://www.acmicpc.net/problem/9037 9037번: The candy war 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각각의 테스트 케이스의 첫 줄에는 아이의 인원 N (1 ≤ N ≤ 10)이 주어지고 그 다음 줄에 www.acmicpc.net 원래는 원형 큐를 사용하도록 하는 문제인 것 같은데 자료구조 모르니 그냥 풀고 나중에 다시 풀어보자 문제에서 시키는대로 하면 되는 문제이다. #include #include // 모든 사람이 동일한 캔디를 가지고 있는지 check // 같으면 return 1 // 다르면 return 0 int check_candys(int *candys, int n) { in..
https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net #include int main () { int a, b; while (1) { scanf("%d %d", &a, &b); if (a == 0 && b == 0) break; if (b % a == 0) { printf("factor\n"); } else if (a % b == 0) { printf("multiple\n"); } else { printf("neither\n"); } } return 0; }
https://www.acmicpc.net/problem/4892 4892번: 숫자 맞추기 게임 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n0으로 이루어져 있다. (0 < n0 < 1,000,000) 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 얼핏 보면 n0부터 n4까지 구해야 하는 문제같지만, 그럴 필요가 없다는 것을 5번째 단계에서 알려준다. n1의 경우 n0에 3을 곱하게 되는데, 짝수에 홀수를 곱하면 짝수이고 홀수에 홀수를 곱하면 홀수이므로 n1은 n0로 판단한다. n4의 경우 n1의 홀.짝에 따라 값이 바뀐다고 하지만, 결국 n0을 2로 나눈 몫이 n4가 된다. #include int main () { int n;..
