알고리즘 재활 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..
inversion counting 연습 문제 사실 코이앞두고 이게 뭐하는짓인가 싶긴한데 몰?루 https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 교차하는 케이블을 하나 풀어내는데 필요한 연산이 버블소트에서의 swap 연산과 같고, 버블소트에서의 swap 연산 횟수는 inversion 의 갯수와 같기 때문에 이 문제는 inversion counting 으로 볼수 있게 된다. 목적하고자 하는 결과값이 정렬된 쌍이 아니기 때문에 입력된 숫자 a1 ..
처음 보고 뇌절할뻔;; https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 처음에 든 생각은 일단 구간을 나누는 순서는 중요하지 않다 정도? 그냥 구간을 결과적으로 K-1개만큼 나누면 어찌저찌 잘 K개 나눠진 구간이 나옴. 이걸 나이브하게 완탐을 돌리면 nCr(3e5, K-1) 번 연산해야할거고 이건 너무나도 큰 숫자니까 이걸 줄여봐야함. 그리고나서 테스트케이스를 봤더니 1 3 5 6 10 에서 10만 따로 떨어져있는데, 이거랑 나눠진 (1,..
https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 도토리가 들어간 상자번호를 구해내는 문제. 간격을 d로 두며, 구간 [a,b] 에서 도토리가 들어가있는 상자의 개수는 min(b,now)/d - a/d +1이다. now 는 내가 정한 상자번호. /d 로 묶어보면 좀 더 자명해지는데, (min(b,now) - a)/d + 1로, b보다 now가 더 작으면 세면 안..
https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제에서 제시한 B[K] 가 K번째로 큰 수 이니까 K를 다르게 해석해보자면 B[K] 보다 작거나 같은 수가 K개 있는 것이 된다. 그래서 B[K]를 mid로 잡고 파라메트릭 서치하면서 개수만 세주면 K에 대한 답을 구할 수 있다. B[K] 가 mid로 잡힌거기때문에 파라메트릭 구간의 끝값이 N*N 인줄 알았는데 AC코드까보니까 K도 된다고하는데 왜인지는 모르겠다. ..