𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 앞서 1978번 소수 찾기에서 풀었던 특정 수에 대한 소수 판정을 확장하여 특정 범위 내의 소수를 모두 구하는 알고리즘인 에라토스테네스의 체를 이용하여 풀 수 있는 문제이다. 말이 어렵지만, 원리가 간단하다. 2 이상의 구하고자 하는 범위 내에 존재하는 자연수를 모두 나열한 뒤, 2의 배수부터 3의 배수, 4의 배수, ... 등 차례로 그 수의 배수들을 지워나간다. 예를 들어, 다음과 같이 2부터 50까지의 범위 내에..

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 소수를 찾는 알고리즘을 이용하여 풀 수 있는 문제. 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 자연수를 의미한다. 2, 3, 5, 7, 11 .. 등의 자연수가 소수로 속한다. 첫번째로 가장 기본적인 소수를 찾는 방법은 2부터 N까지의 수를 조사하는 방법이다. 2부터 N까지의 수 i로 N을 나눠보면서 나머지가 0이 나오는지 판별하는 것이다. 2부터 N까지 모든 경우의 수를 계산해보기 때문에 시간복잡도는 O(N)이 나온다. boo..

문제 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) 출력 첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다. 2609번 최대공약수와 최소공배수 를 이용하여 풀면 간단하게 풀 수 있는 문제이다. 코드 #include..

문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 유클리드 호제법을 이용하여 푸는 문제이다. 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. a > b 인 두 수가 있을 때, a를 b로 나눈 나머지가 r일때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 같은 원리로 계속 값을 구하여 나머지가 0이 됐을 때의 나누는 수가 a와 b의 최대공약수가 된다. 예를 들어 414와 72의 최대공약수를 구하..

문제 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 출력 A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. 정렬을 이용하여 풀 수 있는 문제. 수를 입력을 받은 뒤, sort 함수를 이용하여 정렬한 뒤 K번째 수를 출력하면 되는 간단한 문제다. 코드 #include #include #include using namespace std; int main(void) { int n, k; scanf("%d %d", &n, &k); vecto..

문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 출력 첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다. 정렬을 이용하여 풀 수 있는 문제. 카드에 적혀있는 숫자와 그 숫자 카드의 장수를 매치시키기 위해 map이라는 자료구조를 사용하였다. iteration을 ..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 정렬을 이용한 문제. ..인데 시간 제한이 3초고 메모리 제한이 8MB고 입력받을 수 있는 수의 개수 범위가 [1, 10000000] 이다. 즉 다른 정렬 문제처럼 수를 모두 배열에 입력받은 뒤, STL 함수나 일반 정렬 알고리즘을 통해 정렬하는 방식으로 풀지 말라는 뜻이다. 대신 수의 범위가 [1, 10000]이기 때문에 1부터 10,000까지의 인덱스를 표시할 수 있..

문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 입력 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자..

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 정렬을 이용하여 푸는 문제. 11650번 좌표 정렬하기 와 동일하게 풀면 된다. 병합 정렬을 사용하여 풀었고, y좌표가 증가하는 순으로 - y좌표가 같으면 x좌표가 증가하는 순으로 정렬해야되기 때문에 11650번 문제 풀때랑 살짝만 다르게 ..

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 정렬을 이용하여 푸는 문제. 병합 정렬을 사용하여 풀었고, x좌표가 증가하는 순으로 - x좌표가 같으면 y좌표가 증가하는 순으로 정렬해야되기 때문에 조건문을 하나 더 붙였다. 코드 #include void merge(int** sorted,..