문제https://www.acmicpc.net/problem/19577시간 제한메모리 제한solved.ac 티어1초 (추가 시간 없음)1024MB플래티넘 5풀이 밀린 문제 정리하기, 그중에서도 오일러 피함수 두번째 문제이다. 이번 문제는 대놓고 나 오일러 피함수요 하고 있다. 다만 형태가 좀 특별한데, x * phi(x) = n을 만족하는 x를 찾는 문제이다. n은 입력으로 주어진다. 우리는 이 식만으로 힌트를 얻을 수 있다. 우선, 오일러 피함수의 결과값은 무조건 자연수이다. 오일러 피함수의 정의가 phi(n) = (n 이하의 n과 서로소인 정수의 개수)이기 때문에, 무조건 자연수이다. x와 n, 그리고 phi(x)는 모두 자연수이기 때문에 phi(x) = n/x라는 식을 유도할 수 있고, n/x는 ..
문제https://www.acmicpc.net/problem/4355시간 제한메모리 제한solved.ac 티어1초128MB골드 1풀이 오랜만에 밀린 문제 정리하기이다. 아마 내가 지금 당장 정리하고 싶다는 욕망이 드는 문제가 아니고선, 풀었던 문제를 알고리즘별로 묶어서 한번에 처리하지 않을까 싶다. 지금까지도 풀었던 최단경로 문제부터 정리했었다. 이번 문제가 알고리즘별로 묶어서 정리하는 그 시초가 될 것 같다. 이번 알고리즘은 오일러 피함수, 오일러 토션트함수이다. 사실 정수론, 해석학, 대수학등, 수학 과학을 꽤 좋아하는 입장에서, 수학적인 알고리즘도 굉장히 좋아한다. 뭐... 그걸 딥하게 파고들어서 이해하는건 별개의 몫이지만 말이다. 오일러 피함수는 자연수 n에 대해 자연수 n과 서로소인 n이하의..
문제https://www.acmicpc.net/problem/15681시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이 트리를 배웠다면 아주 간단한 문제이다. 쿼리로 들어오는 정점을 루트로 가지는 서브트리의 정점의 개수를 구하는 문제이다. 풀이방법은 간단하다. 입력으로 들어온 루트노드로부터, 자식 노드로 dfs하며, 정점의 개수를 저장하고 세어준다. 이때, 모든 정점은 적어도 자기 자신을 트리로 가지고 있기 때문에, 서브트리의 정점 개수를 저장할 배열을 1로 초기화한 후, 각 서브트리로 재귀하며 개수를 세어준다.코드#include #define endl '\n'using namespace std;int n, r, q;vector> tree;vector query, child;void in..
문제https://www.acmicpc.net/problem/2258시간 제한메모리 제한solved.ac 티어2초128MB골드 4풀이 이 문제를 풀면서 내가 자꾸 하는 실수를 되짚어보았다. 이 문제를 정리하면 임의의 고기의 가격 미만의 고기는 공짜로 얻을 수 있을 때, 원하는 고기의 양을 만들기 위한 최소비용을 구하는 문제이다. 구현에 문제는 거의 없었지만, 정말 많은 실수를 하면서 무수한 WA를 받았다... 변명이나 해보자면 전날 저녁도 제대로 못먹고, 3시간 반정도 자고 일어나자마자 문제를 풀고 있지만... 사실 지금까지 비슷한 실수(물론 이쯤되면 실수라고 하면 안될거 같다)를 여러번 해왔기 때문에 항상 주의해야할 것 같다. 문제를 보자마자, "아 이거 정렬하고 무게 누적합해가면서 최소가격 찾으면 ..
문제https://www.acmicpc.net/problem/11779시간 제한메모리 제한solved.ac 티어1초256MB골드 3풀이 이번 문제는 최단경로 문제이면서, 동시에 최단경로도 찾아야 하는 문제이다. 정점의 개수가 1천개밖에 되지 않기 때문에 플로이드 워셜, 다익스트라 모두 가능한 문제일 것이다. 아직 플로이드 워셜 최단경로 역추적을 공부하지 않아, 다익스트라 역추적을 이용해 풀어보았다. 조만간 플로이드 워셜 역추적도 공부해서 풀어보도록 하겠다. 다익스트라 알고리즘에서 최단경로를 역추적하는 방법은 경로를 저장하는 배열을 하나 더 만든다. 각 배열의 인덱스는 정점 번호에 맞추고, 각 배열의 값에는 해당 정점에 오기 전에, 어느 정점을 거쳤는지를 저장한다. 코드로 설명을 하면, prev라는 배열..
문제https://www.acmicpc.net/problem/13172시간 제한메모리 제한solved.ac 티어1초512MB골드 4풀이 문제가 이렇게 긴건 오랜만에 보는 것 같다. 결국은 모든 주사위를 한번씩 던졌을 때의 눈의 합의 평균을 나머지가 1000000007인 모듈러 역원을 통해 나타내라는 것이다. 모듈러 역원을 나타내는 방법은 여러가지가 있다. 문제에서는 소수 모듈러일때 가능한 페르마 소정리를 소개하고 있다. 페르마 소정리를 간단하게 설명하면, 소수 p는 임의의 정수 a에 대해 a^p ≡ a (mod p)이며, a와 p가 서로소라면 a^(p-1) ≡ 1 (mod p) 을 만족하는 소수의 필요조건을 의미한다. 문제에서 말하듯, 여기서 한발 더 나아가면 a의 모듈러 역원은 a^(p-2) mod ..
문제https://www.acmicpc.net/problem/28707시간 제한메모리 제한solved.ac 티어1초1024MB골드 1풀이 가지고 있는 연산으로 배열을 오름차순으로 정렬시킬 수 있는지, 또한 최소비용이 얼마인지를 알아내는 문제이다. "최소비용"을 구해야 하는 문제이다. 이 문제를 보고 들었던 방법은 매우 많다. 처음에는 백트래킹, BFS를 떠올렸고, BFS를 쓰던 중, 다익스트라로 처리를 할 수 있을 것 같았다. 입력의 제한을 잘 보면 배열의 길이와 연산의 개수가 그리 크지 않다는 점을 알 수 있다. 그래서 배열을 몇번을 복사하던 그리 큰 시간이 들지 않을 것이라 판단했다. 또한 방문체크와 비용을 체크하기 위해선 배열을 만드는 것이 일반적이지만, 어떤 배열이 나올지 알 수 없기 때문에 u..
문제https://www.acmicpc.net/problem/7453시간 제한메모리 제한solved.ac 티어12초1024MB골드 2풀이 이 문제는 단순무식한 문제이지만, 그래도 배울만한 점이 꽤 있는 문제이다. 시간제한이 12초라는 듣도보도 못한 엄청난 수치에 그래도 배열 길이가 4천밖에 안되기 때문에 완탐을 하는게 아니고선 어지간해서 통과될거라 생각했다. 문제를 보자마자 떠올린 풀이는, a배열과 b배열, c배열과 d배열의 각 원소의 합을 저장한 원소를 ab, cd배열이라고 하자. ab배열과 cd배열에는 중복되는 원소가 존재할 수도 있고 아닐수도 있다. 그렇기에 unordered_map에 원소와, 해당 원소가 등장하는 횟수를 기록한다. unordered_map은 해시이기에 평균적으로 탐색에 O(1)이다..
