좀 만 더..

[Silver II] 베르트랑 공준 - 4948 문제 링크 성능 요약 메모리: 39384 KB, 시간: 840 ms 분류 수학, 정수론, 소수 판정, 에라토스테네스의 체 제출 일자 2023년 12월 19일 20:31:18 문제 설명 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수..

[Silver III] 소수 구하기 - 1929 문제 링크 성능 요약 메모리: 48592 KB, 시간: 216 ms 분류 수학, 정수론, 소수 판정, 에라토스테네스의 체 제출 일자 2023년 12월 19일 16:02:04 문제 설명 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. import math def prime(x, y): arr = [False, False] + [True] * (y-1) for i in range(2, int(math.sqrt(y)) + 1):..

[Silver IV] 다음 소수 - 4134 문제 링크 성능 요약 메모리: 33240 KB, 시간: 1456 ms 분류 브루트포스 알고리즘, 수학, 정수론, 소수 판정 제출 일자 2023년 12월 18일 23:34:21 문제 설명 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 출력 각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다. import math import sys input = sys.stdin.readline def prime(x): if x == 0..

[Silver IV] 가로수 - 2485 문제 링크 성능 요약 메모리: 40952 KB, 시간: 116 ms 분류 유클리드 호제법, 수학, 정수론 제출 일자 2023년 12월 18일 22:55:47 문제 설명 직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다. 편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, ..

[Silver III] 분수 합 - 1735 문제 링크 성능 요약 메모리: 31120 KB, 시간: 44 ms 분류 유클리드 호제법, 수학, 정수론 제출 일자 2023년 12월 16일 14:05:00 문제 설명 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈..

[Silver V] 숫자 카드 - 10815 문제 링크 성능 요약 메모리: 125176 KB, 시간: 672 ms 분류 이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 정렬 제출 일자 2023년 12월 13일 16:41:54 문제 설명 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫..

[Silver III] 서로 다른 부분 문자열의 개수 - 11478 문제 링크 성능 요약 메모리: 240712 KB, 시간: 508 ms 분류 자료 구조, 해시를 사용한 집합과 맵, 문자열, 트리를 사용한 집합과 맵 제출 일자 2023년 12월 13일 16:17:36 문제 설명 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 입력 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로..

[Silver IV] 대칭 차집합 - 1269 문제 링크 성능 요약 메모리: 80432 KB, 시간: 216 ms 분류 자료 구조, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵 제출 일자 2023년 12월 13일 15:32:08 문제 설명 자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다. 예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다...

[Silver IV] 듣보잡 - 1764 문제 링크 성능 요약 메모리: 37092 KB, 시간: 3820 ms 분류 자료 구조, 해시를 사용한 집합과 맵, 정렬, 문자열 제출 일자 2023년 12월 13일 14:41:16 문제 설명 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의..

[Silver IV] 나는야 포켓몬 마스터 이다솜 - 1620 문제 링크 성능 요약 메모리: 55700 KB, 시간: 240 ms 분류 자료 구조, 해시를 사용한 집합과 맵 제출 일자 2023년 12월 13일 14:27:53 문제 설명 안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어. (뚜벅 뚜벅) 얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터볼~ (펑!) 헐랭... 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가...ㅜㅠ (터벅터벅) 어? 누구지? 오박사 : 나는 태초마을의 포켓몬 박사 오민식 박사라네. 다솜아, 포켓몬을 잡을 때는, 일단 상대 포켓..