https://www.acmicpc.net/problem/1629 1629번: 곱셈첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.www.acmicpc.net 단순히 계속 곱했다가는 오버플로우되는 문제. 하지만 모듈러 연산을 적용한다고 해도, 일반적인 반복문으로 접근한다면 시간제한에 걸린다 O(n)이니까. 결국 이 문제의 핵심은숫자가 오버플로우되지 않도록 모듈러연산을 계속해서 적용한다.O(n)으로 접근해서는 안된다.모듈러 연산은 https://codejin.tistory.com/68를 참조하자. 이를 통해 다 곱하고 나누는 것이 아니라, 나머지를 계속 곱하면서 최종적인 값을 찾아야 한다. 그러면 오버플로우는 해결했고 이제..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 처음으로 풀어보는 탐색문제이다. 처음에는 탐색알고리즘이라는걸 모른 채로 그냥 for문 계속 돌리면서 풀었는데, 역시나 시간초과가 나오고 포기했던 문제이다. 하지만 이진탐색(binary search) 알고리즘을 알게 되어 이 문제를 다시 풀었고 맞췄다. 이진탐색은 생각보다 우리가 자주 쓰는 알고리즘이다. 0~100부터 아무 숫자나 하나 정하고, 업다운..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표값이 몇번째에 있는지 출력하는 문제. 특이하게도 이 문제는 정렬하는것이 아닌, 중복을 제거하는 과정에서 애를 먹었다. 컨테이너에서 앞부분에 unique한 원소들로 채워넣고, 뒷부분에는 남은 원소들로 채운다음, 뒷부분의 포인터를 반환하는 unique함수의 동작원리때문에 애먹었다. std::move()함수를 통해 동작하기 때문에, 이를 이해하려고 ..
https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번에는 입력받은 숫자를 정렬하는 문제. 각 자리수로 분해해서 정렬하면 된다. // C solution #include #include int compare (const void * a, const void * b) { int x = *(int *)a; int y = *(int *)b; return x < y; } int main () { int temp, len = 0; int number[10]; scanf("%d", &temp); for (int i = 0; temp != 0;..
https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 입력받은 숫자들의 통계값을 출력하는 문제. 개인적으로 최빈값을 출력하는 과정이 제일 힘들었다. N이 홀수로 제한되어있기 때문에 중앙값은 구하기 쉽다. 평균의 경우 반올림에 주의하자. 최빈값의 경우, 등장횟수를 다 저장한 후에, max_element 함수를 이용해서 해결했다. max_element의 경우, 주어진 범위 내에서 가장 큰 요소의 첫번째 위치를 반환한다. 예를 들어, {1, 2, 3(1), 2, 3(2..
https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net https://codejin.tistory.com/102 y y) return -1; else if (p1->y > p2->y) return 1; else { if (p1->x x) return -1; else if (p1->x > p2->x) return 1; } return 0; } int main () { int ..
https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 같은 나이에 대해 안정정렬을 하는 문제...인거 같은데 어째서인지 그냥 정렬로 해도 풀리는 느낌이다. 비교함수가 어찌저찌 잘 맞아 떨어졌나보다. // C solution // 왜 되는거지? #include #include typedef struct { int age; char name[101]; }User; int compare(const void * a, const void * b) { User * ..
https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 좌표를 정렬하는 문제. x좌표 먼저 비교하고, 그다음 y좌표를 비교하자. 그리고 동적할당을 할때는 할당 해제하는 것도 잊지말자.... // C solution #include #include // 좌표 구조체 typedef struct { int x; int y; }Pos; // stdlib.h에 있는 qsort에 쓰기 위한 함수. int co..
