0과 1의 쉼터

풀이 좌표 정렬하기 1에서는 x를 우선으로 오름차순 정렬 후, x의 값이 동일할 때 y의 값으로 오름차순 정렬했지만, 이번 문제에서는 반대로 y를 오름차순 정렬 후, 동일값일때 x를 기준으로 오름차순 정렬하면 해결할 수 있다. 소스코드 #include #include typedef struct{ int x, y; }Point; int compare(const void *a, const void *b){ Point p1 = *(Point*)a, p2 = *(Point*)b; if (p1.y p2.y) return 1; else { if (p1.x p2.x) return 1; retu..

풀이 이분 탐색이란, 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘이다. 이를 사용하기 위해서는 요소들이 반드시 정렬되어 있어야 한다. N개의 정수를 Quick Sort로 정렬해준 후, M개의 정수를 입력받음과 동시에 Binary Search로 탐색해 해결했다. Binary Search의 Big-O는 O(log2n)이지만, n은 최대 100,000으로 재귀 함수로 구현해도 Stack Overflow가 발생하지 않기 때문에 재귀적/비재귀적 방법으로 둘 다 사용 가능하다. 소스코드 #include #include int compare(const void *a, const void *b){ int n1 = *(int *)a, n2 = *(int *)b; if (n1 < n2) return -1; ..

풀이 x를 기준으로 오름차순으로 정렬하는데, 만약 x의 값이 동일하다면 y의 값을 기준으로 오름차순으로 정렬하면된다. 소스코드 #include #include typedef struct{ int x, y; }Point; int compare(const void *a, const void *b){ Point p1 = *(Point*)a, p2 = *(Point*)b; if (p1.x p2.x) return 1; else { if (p1.y p2.y) return 1; return 0; } } int main(){ int N; scanf("%d", &N); Point p[N]; for..

풀이 시간 제한이 2초라, 공간효율보다는 시간효율을 중시해 코드를 작성했다. 소스코드 #include #include int num[1000001]; int compare(const void *a, const void *b){ int n1 = *(int *)a, n2 = *(int *)b; if (n1 n2) return 1; return 0; } int main(){ int N; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &num[i]); qsort(num, N, sizeof(int), compare); for (int i = 0; i < N; i++) printf("%d\n", num[i..

풀이 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 두 수 N, M (N > M)을 입력받는다. N을 M으로 나누었을 때의 몫과 나머지가 N, M이 되며 이 과정을 나머지가 0이 될 때 까지 반복한다.\ 나머지가 0이 될때의 N(몫)이 최대공약수이다. 두 수 N, M의 곱은 최대공약수(GCD)와 최소공배수(LCM)의 곱과 같다. 소스코드 #include int euclidean_gcd(int n, int m){ return m ? euclidean_gcd(m, n%m) : n; } int main(){ int n, m; scanf("%d %d", &n, &m); int gcd = euclidean_gcd(n, m); printf("%d\n%d", gcd, n*m / gcd); } 출처 및 참고자료 ..

풀이 문자열과 문자열의 길이를 구조체 배열로 저장해주고, Quick Sort를 사용해 길이에 따라 오름차순 정렬 후, 길이가 같을 때는 strcmp()로 문자열을 비교해 문자열이 크고 작은지에 따라 정렬해준다. 문자열을 비교해 동일한 문자열을 가지는 구조체가 없을때만 출력해준다. 소스코드 #include #include #include typedef struct { char str[51]; int len; }Str; int compare(const void *a, const void *b){ Str s1 = *(Str*)a, s2 = *(Str*)b; if (s1.len s2.len) return 1; return strcmp(s1.s..

풀이 문자열의 길이를 알아내 문자열의 양끝을 비교하는 방식으로 문제를 해결할 수 있다. 무의미한 0이 주어지지 않으므로, num[0]의 값이 0이면 반복문을 빠져나온다. 소스코드 #include #include int main(){ char num[6]; while (scanf("%s", num) && num[0] != '0') { int len = strlen(num), palin = 1; for (int i = 0; i < len/2; i++) if (num[i] != num[len - 1 - i]){ palin = 0; break; } puts(palin ? "yes" : "no"); } } 출처 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 9999..

풀이 N * M 크기의 보드를 2차원 배열로 입력받고, (0, 0), (0, 1), (0, 2), ... 각 요소들을 기준으로 8 * 8크기의 보드를 수정해 체스판을 만들 때, 몇 개의 칸이 수정되어야 생성되는지 최소값을 기록하는 방식으로 해결할 수 있다. 맨 처음 시작좌표인 (0, 0)을 기준으로 다음과 같은 체스판을 생성하기 시작한다고 가정한다. (빨간 사각형) 기준이 되는 시작 좌표는 (row, col)이며, 이 값을 가상의 보드를 생성하는 함수로 복사한다. 시작 좌표를 기준으로 (row ~ +7, col ~ +7)의 범위 (빨간 사각형) 안에서, 체스판을 생성할 때 최소 몇개의 칸이 수정되는지 확인 검정칸 이어야 하는 곳((i + j) % 2 == 0)이 검정칸이면, white++, 아니면 bla..

소스코드 #include int main(){ int A, B; scanf("%d %d", &A, &B); printf("%d", A*B); } 출처 10998번: A×B 두 정수 A와 B를 입력받은 다음, A×B를 출력하는 프로그램을 작성하시오. www.acmicpc.net

풀이 문자열을 입력받고, 문자 '0'~'9'에 48을 뺀 아스키 코드 값이 숫자 0 ~ 9와 같다는 점을 이용해 해결하면 된다. 소스코드 #include int main(){ int N, sum = 0; char str[101]; scanf("%d %s", &N, str); for (int i = 0; i < N; i++) sum += str[i] - 48; printf("%d", sum); } 출처 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net