https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 요세푸스 문제는 큐를 이용하여 풀어도 되고, dp를 이용해도 되고, 재귀식을 이용해 풀어도 됩니다. 하지만 현재 문제의 메모리가 매우 제한적이므로, 큐나 dp 등 큰 메모리를 사용하는 것을 사용할 수는 없고, 재귀를 이용하여도, 스택에 function call 메모리가 계속 쌓이므로 사용이 안 됩니다. 따라서 기존 요세푸스 문제 점화식을 loop로 풀어서 적용하면 됩니다. 코드는 다음과 같습니다. #include using namespace std; int main() { ..
https://www.acmicpc.net/problem/13926 13926번: gcd(n, k) = 1 자연수 n이 주어졌을 때, gcd(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 주어진 정수 n에 대해서 오일러 피 함수 값을 구하는 문제입니다. ( __int128 을 안 써서 시간초과가 뜬 거라고는 예상하지 못했다..... ) n의 최대 입력이 10^18 이므로 약 2^60 정도됩니다. 따라서 곱셈 연산 등에서는 __int128 타입으로 계산을 진행해야 합니다. 로직은 다음과 같습니다. 1. n에 대해 폴라드 로 알고리즘으로 소인수를 구한다. 2. 해당 소인수가 prime인지 여부를 밀러 라빈 소수 판정법으로 계산한다...
https://www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 피자가 어떤 모양으로 주어질 지는 모르지만 볼록 다각형이라는 힌트가 있습니다. 이 때 가장자리에 4개의 점을 찍었을 때 4조각으로 나뉘는 지 판단하는 문제입니다. 피자 모양과 상관없이 4개의 점을 기준으로 4조각으로 나누려면 두 선분이 교차하면 됩니다. 단 이 때 교차의 조건으로 한 점이 다른 선분 위에 있으면 안 됩니다. 위 조건을 만족시키려면 CCW를 계산하였을 때 하나는 시계, 하나는 반시계 방향을 만족하..
https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 주어진 수열에 대해 *a+b 꼴의 패턴이 존재하는 지를 판단하는 문제입니다. 입력은 절대값 100 이하의 정수로 주어지고, a,b 도 정수입니다. 전체 개수 n, 주어진 수 x1, x2, ..., xn 이라 할 때 n=1 인 경우, 뒤에 무슨 수든 올 수 있으므로 답은 A 입니다. n=2인 경우, x1=x2이면, a=1, b=0 or a=0, b=x1 이 되고, 두 패턴 모두 동일한 x1을 정답으로 얻으므로 답은 x1입니다. x1 != x2 인 경우, 여러 값이 ..
https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 처음에 문제를 보고 엣지 길이가 항상 1일거라 생각하고 예제를 봤는데 도저히 나올 수 없는 트리 구조여서 어떻게 하나 막막했던 문제였습니다. (하지만 문제를 다시 읽어보니 엣지 가중치가 있었다.....) 1000개 노드를 대상으로 탐색을 진행하고, 1000개 쿼리가 발생할 수 있으므로 그냥 다익스트라로 접근해도 뭔가 풀릴 거 같지만, 안전하게 우선순위 큐를 이용한 다익스트라로 ..