본문 바로가기
728x90

알고리즘 문제 풀이30

[백준 1977번] 완전제곱수 - C++ 풀이 https://www.acmicpc.net/problem/1977(백준 문제 링크)1. 문제 설명문제M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는 64, 81, 100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다.2. 풀이이 문제는 단순하게(Naive) 구현하는 방식으로 해결 가능합니다.M이상 N이하 구간 내의 수 A가 1부터 100까지의 수의 제곱과 같은지 검사하는 방식으로 해결합니다.예를 들어 $M=2$, $N=7$이면 구간 내의 수 A는 2, 3, 4, 5, 6, 7이 될 수 있습니다. 각각의.. 2024. 8. 30.
[백준 11051번] 이항 계수 2 - C++ 풀이 https://www.acmicpc.net/problem/11051(백준 문제 링크)1. 문제 설명문제자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $(binom{N}{K})$를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 2. 풀이이번 문제는 이항 계수를 구하여야하는 문제입니다. 이항 계수는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수입니다.조금 더 쉽게 말하자면 두개의 항을 가지는 식,예를 들어 a, b 두개의 항을 갖는 $(a+b)$ 식을 2번 거듭제곱하였을 때,$a^2 + 2ab + b^2$ 이 됩니다.위 예시에서 이항 계수는 {1, 2, 1} 입니다.참고로 고등교육과정 속에서 나오는 $nCr$은 $(binom{n}{r})$.. 2024. 8. 30.
[백준 1292번] 쉽게 푸는 문제 - C++ 풀이 https://www.acmicpc.net/problem/1292(백준 문제 링크)1. 문제 설명문제동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.2. 풀이주어진 문제는 주어진 수열의 구간 합을 구하는 문제입니다. 해당 문제는 단순하게(naive) 구현하여도 풀 수 있지만, 누적합(Prefix Sum)을 통한 풀이를 소개하겠습니다.누적합이란 주어진 수열에서 특정 .. 2024. 8. 29.
[백준 9613번] GCD 합 - C++ 풀이 https://www.acmicpc.net/problem/9613(백준 문제 링크)1. 문제 설명문제양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.2. 풀이n개의 양의 정수 수열 $a_1, a_2, a_3, ..., a_n$이 주어졌을 때, 가능한 모든 순서쌍에 대하여 GCD(최대공약수)를 구하여야합니다.이는 $(1$i$ 값의 범위인 $1$부터 $n-1$까지의 경우에 따라 $j$값이 될 수 있는 모든 경우를 찾아서 $GCD(a_i, a_j)$을 구합니다.최대 공약수는 유클리드 호제법을 통해 쉽게 구할 수 있습니다.3. 정답 코드#include#include#define endl "\n"using namespace std;long long int gcd(int.. 2024. 8. 29.
[백준 10610번] 30 - C++ 풀이 https://www.acmicpc.net/problem/10610(백준 문제 링크)1. 문제 설명문제어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.2. 풀이주어진 수를 섞어 만들 수 있는 30의 배수 중 가장 큰 것을 출력하여야합니다.우선 주어진 수를 섞었을 때, 30의 배수가 될 수 있을지를 판별해야합니다.이는 매우 단순하게 해결할 수 있습니다. 3의 배수 성질과 10의 배수 성질을 이용하면 됩니다.3의 배수는 모든 자릿수를 합한 값이 3의 배수입니다. 10의 배수는 최하위 자릿수가 .. 2024. 8. 28.
[백준 2168번] 타일 위의 대각선 - C++ 풀이 https://www.acmicpc.net/problem/2168(백준 문제 링크)1. 문제 설명문제한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다.이 직사각형에 하나의 대각선을 그렸다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 프로그램을 작성하시오.2. 풀이가로가 3, 세로가 2인 벽에 타일을 붙이면 아래 그림과 같습니다.처음 시작된 격자에서 선이 진행되다가 격자와 격자 사이 경계선에 다다르면 새로운 영역(타일)으로 나가는 것이 되며, 해당 영역(타일)에도 선이 그어지.. 2024. 8. 28.
[백준 1476번] 날짜 계산 - C++ 풀이 https://www.acmicpc.net/problem/1476(백준 문제 링크)1. 문제 설명문제준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.예를 들어, 15년은 15 15 15로 나타낼 수 있다.. 2024. 8. 27.
[백준 1094번] 막대기 - C++ 풀이 https://www.acmicpc.net/problem/1094(백준 문제 링크)1. 문제 설명문제지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.1. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막.. 2024. 8. 27.
[백준 1699번] 제곱수의 합 - C++ 풀이 https://www.acmicpc.net/problem/1699(백준 문제 링크)1. 문제 설명문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 $11=3^2+1^2+1^2$(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 $11=2^2+2^2+1^2+1^2+1^2$(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.2. 풀이이 문제는 .. 2024. 8. 27.
[백준 1789번] 수들의 합 - C++ 풀이 https://www.acmicpc.net/problem/1789(백준 문제 링크)1. 문제 설명문제서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?2. 풀이서로 다른 N개의 자연수의 합이 S가 되도록 하면서, N의 값을 최대화 하려면 합이 될 각각의 수는 최소가 되어야합니다.그러기 위해서는 제일 작은 자연수인 1부터 차례대로 사용하여야합니다. 그리고 S를 넘지 않을 때 까지 수를 더하다가 S를 넘게 될 상황이 되면, 자연수의 합 S에서 현재까지 나열된 자연수의 합 A를 뺀 만큼을 가장 마지막 원소에 더해주면 됩니다. ($S-A$)예를 들어 $S = 7$ 이라면, $A = 1 + 2 + 3$ 입니다.$S - A = 1$ 이므로,마지막 원소인 3에 이 값을 더하여.. 2024. 8. 27.
[백준 2217번] 로프 - C++ 풀이 https://www.acmicpc.net/problem/2217(백준 문제 링크)1. 문제 설명문제N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 .. 2024. 8. 27.
[백준 13458번] 시험 감독 - C++ 풀이 https://www.acmicpc.net/problem/13458(백준 문제 링크)1. 문제 설명문제총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 $A_i$명이다.감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오. 2. 풀이N개의 시험장에는 최소 1명이상의 학생이 존재하므로 시험장 하나마다 반드시 총감독관은 1명이 존재해야합니다.총.. 2024. 8. 27.
[백준 1065번] 한수 - C++ 풀이 https://www.acmicpc.net/problem/1065(백준 문제 링크)1. 문제 설명문제어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 2. 풀이등차 수열은 공차가  일때 $a_n+1-a_n=d(for all n)$을 성립해야합니다.조금 더 쉽게 설명하자면, 각 자리가 등차수열을 이룬다는 것은 각 자리 수가 $a_0, a_1, ..., a_n$ 일때, $a_0 - a_1 = a_1 - a_2 = a_2 - a_3$ 를 만족해야합니다.수열에 항이 하나밖에 없는 경우에는, 연속된 두 항의 차이를 정.. 2024. 8. 27.
[백준 4673번] 셀프 넘버 - C++ 풀이 https://www.acmicpc.net/problem/4673(백준 문제 링크)1. 문제 설명문제셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.33, 39, 51, 57, 69, 84, .. 2024. 8. 27.
[백준 23827번] 수열 (Easy) - C++ 풀이 https://www.acmicpc.net/problem/23827(백준 문제 링크)1. 문제 설명문제모든 원소가 양의 정수이고, 길이가 N인 수열 $A_1, A_2, ..., A_N$이 주어진다. 1≤i $(i, j)$에 대해 $A_i$ × $A_j$의 합을 1,000,000,007로 나눈 나머지를 구하시오.입력첫째 줄에 수열 A의 길이 N이 주어진다.둘째 줄에 수열 $A_1, A_2, ..., A_N$이 공백으로 구분되어 주어진다.출력 1≤i 1000000007로 나눈 나머지를 출력하여라.제한 2 ≤ N ≤ 500000 1 ≤ $A_i$ ≤ 500000 2. 풀이이 문제는 수학에서 "분배의 법칙"이라고 불리는 연산법칙을 이용하여 해결 가능합니다. 수열의 원소로 $A_1$, $A_2$, $A_3$ 를 .. 2024. 8. 25.
[백준 24060번] 알고리즘 수업 - 병합 정렬 1 - C++ 풀이 https://www.acmicpc.net/problem/24060(백준 문제 링크)문제오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p 입력첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 .. 2024. 8. 23.
[백준 11279번] 최대 힙 - C++ 풀이 https://www.acmicpc.net/problem/11279(백준 문제 링크)문제널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.출력입력에서 0이 주어진 횟수만큼 답을 출.. 2024. 8. 15.
[백준 2559번] 수열 - C++ 풀이 https://www.acmicpc.net/problem/2559(백준 문제 링크)문제매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,3 -2 -4 -9 0 3 7 13 8 -3모든 연속적인 이틀간의 온도의 합은 아래와 같다.이때, 온도의 합이 가장 큰 값은 21이다.또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,이때, 온도의 합이 가장 큰 값은 31이다.매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.입력첫째 줄에는 두 개의 정.. 2024. 8. 11.
728x90

티스토리툴바