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 좌표쌍을 여러 개 입력 받고, 정렬하는 문제이다. x좌표에 대해 오름차순으로 정렬하고, 만약 x좌표 값이 동일하다면 y좌표 값을 기준으로 오름차순 정렬해주면 된다. 사실 파이썬 정렬의 기본값은 오름차순이라, 아래 코드처럼 정렬 기준을 정해주지 않아도 되지만 쓸 경우가 반드시 있을 것이라 생각하므로 알아두면 좋을 것 같다! Key가 의미하..
https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 골드3치고는 풀이법이 그렇게 어렵지 않다고 느꼈다. 1. 우선 문제의 입력들을 받은 뒤, 오름차순으로 정렬해준다. 2. 현재 연료량 만큼 전진한다. 연료를 1씩 감소시키며 전진하다가 주유소를 만나면 해당 주유소에서 주유 가능한 연료량을 우선 순위 큐에 저장한다! 3. 연료가 0이 되는 순간, 큐에서 제일 앞에 있는 놈(주유 가능한 연료가 제일 많은 놈)만큼..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수를 2개씩 묶거나, 더해가면서 수열의 합 중 최대 값을 찾는 문제이다. 양수를 담을 벡터 하나, 0을 담을 벡터 하나, 음수를 담을 벡터 하나 총 3개의 벡터를 활용하였다. 양수는 내림차순으로, 음수는 오름차순으로 정렬해준 뒤, 최댓값을 계산하면 된다! 먼저 양수에서는, 나의 다음 숫자가 1인 경우가 중요하다. 양수는 거의 곱하는 것이 이득인데, 1일 때는 곱하는 것보다 더하는 것이 더 이득이..
https://www.acmicpc.net/problem/14593 14593번: 2017 아주대학교 프로그래밍 경시대회 (Large) 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)는 2009년 제1회를 시작으로 2014년 제6회까지 개최된 아주대학교 학생들을 위한 프로그래밍 경시대회이다. 2017년, 다른 학교에서 활발히 www.acmicpc.net 문제 분석 문제의 설명중 대부분은 실제 경시대회 규칙인듯하여, 중요한 부분만 뽑아 분석하자. ! 해결한 문제 점수의 총합이 높은 참가자가 더 높은 순위를 가진다. ! 점수의 총합이 같은 경우, 제출 횟수가 적은 참가자가 더 높은 순위를 가진다. ! 점수의 총합과 제출 횟수가 같은 경우, 마지막으로 점수를 획득한 문제의..
정렬 - 선택 정렬 void sort(int* a, const int n) { // n개의 정수 a[0]부터 a[n-1]까지 비감소순 정렬 for (int i = 0; i < n; i++) { int j = i; //a[i]와 a[n-1]사이에 가장 작은 정수 값을 찾음 for (int k = i + 1; k < n; k++) { if (a[k] < a[j]) { j = k; // 교환 } } swap(a[i], a[j]); } } 제일 작은 정수를 찾아 앞으로 보내는 작업을 계속 반복한다. 탐색 이원탐색(binary search) int binarySearch (int arr[], int low, int high, int key) { while (low key) high = mid - 1; else..
