본문 바로가기

분류 전체보기702

[백준 11651] 좌표 정렬하기 2 [C] 풀이 좌표 정렬하기 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.. 2021. 7. 16.
[백준 1920] 수 찾기 [C] 풀이 이분 탐색이란, 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘이다. 이를 사용하기 위해서는 요소들이 반드시 정렬되어 있어야 한다. 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; .. 2021. 7. 15.
[백준 11650] 좌표 정렬하기 [C] 풀이 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.. 2021. 7. 15.
[백준 2751] 수 정렬하기 2 [C] 풀이 시간 제한이 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.. 2021. 7. 15.
[백준 2609] 최대공약수와 최소공배수 [C] 풀이 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 두 수 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); } 출처 및 참고자료 .. 2021. 7. 15.
[백준 1181] 단어 정렬 [C] 풀이 문자열과 문자열의 길이를 구조체 배열로 저장해주고, 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.. 2021. 7. 15.

티스토리툴바