https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 정렬 문제. 현재 단계에서 K명이 정렬을 진행할때, 사람 혼자서 맡게되는 부분 배열의 크기는 N/K 이다. 전체 N개 크기의 배열을 N/K 개의 부분 배열로 분할해서, 그 부분만 정렬해주면 된다. 정렬에는 std::sort을 사용했다. #include using namespace std; int N,K; int arr[1234567] = {0}; int main(){..
https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 정렬 문제. 점수가 높은 팀 문제 제출 횟수가 적은 팀 마지막 제출 시간이 더 빠른 팀 순서대로 정렬해주면 되는 문제. 이것저것 관리하기 귀찮으므로 구조체를 사용했다. N이 별로 크지 않으므로 직접 비교해서 N^2 정렬을 해줘도 좋다만 sort 함수의 정렬순서를 바꾸는 비교함수를 직접 작성해보는 연습용 문제로써 나쁘지 않은듯. struct solve{ int cnt = 0; int time = 0; in..
https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 실제 등수가 1,2,3,4,5.... 차가 1로 일정한 증가하는 수열의 형태를 띄고 있고, 문제 입력으로 들어온 수열을 해당 수열과 최대한 비슷한 형태로 구성하는 문제이다. 최대한 비슷한 형태 >> 정렬된 배열을 지칭하는 말로, 입력으로 들어온 배열을 정렬해서 인덱스값+1 과 비교해서 불만도의 총 합을 구하면 된다. 입력으로 들어온 배열을 구성할 때 $i N_j$ 인 상황에서 불만도의 합인 $Total$..
알고리즘 재활 2일차. https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 랜덤으로 집어온 문제. trie 자료구조를 통해 해결할 수 있다. 전에 아호코라식 기초문제 풀면서 분명 다뤘던거같은데 까먹어서 다시 배웠다 https://rebro.kr/86 [자료구조] 트라이(Trie) 자료구조 [목차] 1. 트라이(Trie) 자료구조란? 2. 트라이(Trie)의 작동 원리 3. 트라이(Trie) 자료구조의 장/단점 4. 트라이(T..
입시를 대충 끝내고 PS재활을 시작하면서 접한 첫 문제. 거의 1년동안 문제를 안풀엇기때문에 바로 답이 안떠올라서 태그부터 까보았다. 태그는 그리디 / 정렬 정렬시켜놓고 숫자를 출력시킨 다음에 생각을 시작했는데 마지막 값으로 들어온 30이 이질적이게 큰 것을 보면서 다른 모든 숫자의 합으로 30이 만들어질수 없다는 생각을 했다. 다른 모든 숫자의 합 을 부분합으로 구해준 다음에 부분합으로 앞선 숫자들을 전부 사용해도 만들수 없는 수가 입력으로 있는 경우 부분합+1 이 답이 된다. 입력에 1이 없는 경우 숫자 1부터 만들수 없어 1을 출력해야하니 이부분에 대해서 처리가 필요할듯. AC받았다. 더보기 #include using namespace std; int arr[1234] = {0}; int prefi..
이쪽은 그냥 내가 풀다가 죽어라 헷갈리는 부분이나 새로 배우면서 흥미롭다 싶은부분 메모하는 글들이기때문에 작성방법이 묘할것이라 생각함. 세그트리 밀다가 만난 문제 유형 정렬은 그냥 무지성 std::sort 박아서 정렬을 한번쯤 정리해두는게 좋을것 같았다. 해당 유형의 문제로는 1517번, 23336번, 10090번 등등이 있다 머지소트 merge sort 머지소트는 정렬에 대해서 분할정복을 적용한 케이스라고 이해하면 되겠다. void mergeSort(int s, int e){ if(s