본문 바로가기

정수론

 (37)
[정수론] 1-1. Numbers and Sequences $\S$ Well-Ordering Property (WOP / 정렬 원리)란? 모든 공집합이 아닌 자연수 집합 $\mathbb{N}$의 부분 집합 $S$는 최소 원소(min element)가 존재한다. ( $\forall$ $S \subset \mathbb{N}$ and $S \neq \varnothing$, $S$ has min element.) 정수론에서는 이를 공리로써 받아들인다. 이를 넓혀, 임의의 어떤 집합 $R$의 모든 공집합이 아닌 부분 집합 $S$가 항상 최소 원소를 가지고 있다면, 우리는 이 집합 $R$이 "Well-Ordered"돼있다고 이야기한다. 예를 들어 보자. $\mathbb{N}$은 Well-Ordered 이다. $\mathbb{Z}$는 not Well-Ordered 이다. 그..
[Atcoder] ABC 280 - D. Factorial and Multiple https://atcoder.jp/contests/abc280/tasks/abc280_d D - Factorial and Multiple AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 22/12/03 업솔빙을 하며 개인적으로 백준의 8279번이 많이 떠올랐던 문제였다. https://www.acmicpc.net/problem/8279 8279번: Double Factorial For a positive integer n, its factorial is defined as the product of all integers..
[Python] 17394번 핑거 스냅 https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼 www.acmicpc.net 22/11/18 BFS와 에라토스테네스의 체를 섞은 독특한 문제로, 두 알고리즘을 모두 알고 있다면 어렵지 않게 해결할 수 있는 문제이다. 특히, 이 문제는 1697번 숨바꼭질 문제와 같은 방식으로 방문처리를 하기 때문에 1697번을 해결했었다면 이 문제 또한 쉽게 해결할 수 있을 것이다. 문제 접근 방식: 먼저 목표 범위인 $A$와 $B$의 범위를 보면 $2 \leq A \leq B \leq 100,..
[Python] 16886번 나누기 게임 https://www.acmicpc.net/problem/16886 16886번: 나누기 게임 구사과와 큐브러버는 나누기 게임을 하려고 한다. 이 게임은 돌이 N개 포함되어 있는 돌 더미 1개에서 시작한다. 두 사람은 턴을 번갈아 가지며, 구사과가 턴을 먼저 갖는다. 각 턴마다 다음을 할 www.acmicpc.net 22/11/19 2022.11.22 - [백준 문제 풀이] - [Python] 2737번 연속 합 [Python] 2737번 연속 합 https://www.acmicpc.net/problem/2737 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acm ligh..
[Python] 2737번 연속 합 https://www.acmicpc.net/problem/2737 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acmicpc.net 22/11/19 16886번을 풀다가 겸해서 풀게 된 문제로, 전형적인 수학 문제이다. 2022.11.22 - [백준 문제 풀이] - [Python] 16886번 나누기 게임 [Python] 16886번 나누기 게임 https://www.acmicpc.net/problem/16886 16886번: 나누기 게임 구사과와 큐브러버는 나누기 게임을 하려고 한다. 이 게임은 돌이 N개 포함되어 있는 돌 더미 1개에서 시작한다. 두 사람은 턴을 번갈아..
[Python] 18867번 편지 꼭 해다오 https://www.acmicpc.net/problem/18867 18867번: 편지 꼭 해다오 욱제는 2020년 04월 02일 목요일 14시 00분에 논산 육군훈련소에 입소했다. 욱제는 2020년 04월 29일 수요일에 사회로 돌아온다. 욱제에게 격려의 메세지를 남겨주자. 단, 편지의 내용은 아래의 조건을 www.acmicpc.net 22/11/16 실랜디를 하다가 만나게 된 조금 어처구니없는 문제로, 많이 틀렸었었다. 레이팅이 된 문제이긴 한데, 약간 번외 문제 느낌이 들었어서 흥미롭게 풀었던 기억이 있다. 전형적인 구성적 문제이나, 그 조건이 문자열과 정수론이 결합된 독특한 문제여서 조금 애를 먹었다. 문제 접근 방식: 1바이트 단위로 끊어서 읽는데, 이 $i$번째 문자를 int로 캐스팅 한 값을..
[Python] 4913번 페르마의 크리스마스 정리 https://www.acmicpc.net/problem/4913 4913번: 페르마의 크리스마스 정리 각 테스트 케이스에 대해서, 한 줄에 L U x y를 출력한다. 여기서 L과 U는 입력으로 주어진 값이고, x는 구간 [L,U]에 포함된 소수의 개수, y는 [L,U]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 www.acmicpc.net 22/11/13 분명 태그 하나(에라토스테네스의 체)가 보이는 문제여서 접근을 했건만, 2번의 시간초과와 여러 번의 의문의 틀렸습니다를 받고 당황했던 문제이다. 요구하는 선행지식은 누적 합의 개념과 에라토스테네스의 체이다. 문제 접근 방식: 먼저, 구간 내의 소수를 판정해야되고, $L$과 $U$의 범위가 최대 $1,000,000$까지 이므로, 에라토스테네스의 체..
[Python] 25921번 건너 아는 사이 https://www.acmicpc.net/problem/25921 25921번: 건너 아는 사이 첫째 줄에 비용의 최솟값을 출력한다. www.acmicpc.net 22/11/06 대회 도중에는 거의 접근을 가까이했지만 풀지 못했으나, 이후 살짝 고쳐서 맞았습니다를 받은 문제이다. 그래프 문제처럼 보이는 소수 판정 문제로, 참 기발하다고 생각했다. 문제 접근 방식: 음식의 가격의 합을 작게 하려면 최대한 음식을 먹는 횟수가 적어야 할 것이다. 다시 말해, 밥을 먹는 사람들의 번호를 노드, 서로 밥을 먹는 사람들끼리 잇는 것을 간선이라고 한다면, 우리는 이 간선의 개수를 최소한으로 만들어야 한다. 쉽게 이야기하자면 서로 만나서 밥 먹는 횟수가 적어야 된다. 따라서, 이 그래프에서는 사이클이 없어야 된다. ..

티스토리툴바