알고리즘/수학

문제 설명정수 A가 B로 나누어 떨어지면, B는 A의 약수이고 A는 B의 배수이다.최대공약수란 정수의 공통된 약수 중 가장 큰 수를 말한다. 예를 들어, 12와 8의 공통된 약수 1, 2, 4 중에서 가장 큰 것은 4이기 때문에 12와 8의 최대공약수는 4이다.N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것을 찾는 프로그램을 작성하시오. 이때, 최대공약수는 K의 약수가 되면 안 된다.예를 들어, 정수 8, 12, 24, 36, 48에서 8을 빼면 나머지 12, 24, 36, 48의 최대공약수는 12가 되고, 12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다. 이때, 다른 수를 빼도 최대공약수가 8보다 커질 수 없다.하지만, 8, 12, 20, 32..

문제 설명세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다.https://www.acmicpc.net/problem/11688       제한 사항      풀이문제를 요약하면, a, b, L이 주어졌을 때, a, b, c의 최소공배수가 L이 되도록 하는 c의 최솟값을 구해야 한다. 우선, 해당 문제를 풀기 위해서는 gcd(최대공약수)와 lcm(최소공배수)을 구하는 방법을 알아야 한다.gcd는 다음과 같은 간단한 함수로 구할 수 있다.long long gcd(long long y, long long x){ if (x == 0) return y; return gcd(..

문제 설명소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:“이제 슬슬 비번 바꿀 때도 됐잖아”“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"“그럼 8179로 해”“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나..

문제 설명이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 1$1$번부터 N$N$번까지 심었다. 이 나무들의 초기 높이는 모두 0$0$이다.사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 2$2$개를 준비했다. 한 물뿌리개는 나무 하나를 1$1$만큼 성장시키고, 다른 물뿌리개는 나무 하나를 2$2$만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 3$3$만큼 키울 수도 있다.물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다. 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다. 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의..

문제 설명의 그림과 같은 삼각형이 있다. 작은 삼각형들은 1부터 시작해서 위와 같은 규칙으로 번호가 쭉 매겨져 있다. 이와 같은 그림에서, A가 적혀 있는 삼각형에서 B가 적혀 있는 삼각형으로 이동하려 한다.한 삼각형에서 다른 삼각형으로 이동할 때에는 삼각형들의 변을 통해서만 움직일 수 있으며, 꼭짓점을 통해서는 다른 삼각형으로 이동할 수 없다. 또한 삼각형의 밖으로 이동할 수도 없다. 이와 같이 이동을 할 때, 도중에 지나는 변의 개수가 그 경로의 길이가 된다.A와 B가 주어졌을 때, 가장 짧은 경로의 길이를 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2155      제한 사항      풀이문제를 요약하면, A, B 두 수가 주어졌을 때 그림과 같은 삼각형에..

문제 설명수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.https://www.acmicpc.net/problem/10986      제한 사항      풀이문제를 요약하면, 연속한 부분의 합이 M으로 나누어 떨어지는 (i, j)의 쌍의 개수를 구하는 것이다. 누적합을 이용하면 간단하게 풀 수 있어 보이지만 사실은 그렇지 않다.누적합을 이용하여 (i, j)의 모든 쌍을 구한다고 가정하면 N이 최대 $10^6$이기 때문에 시간초과가 발생한다.따라서, 다른 풀이가 필요하다. 문제의 핵심은 mod연..

문제 설명직사각형의 변 위에 여러 모양의 점이 있고, 같은 모양의 점은 정확히 두 개씩 있다. 단 직사각형의 꼭짓점에 놓인 점은 없다. 이제 같은 모양의 두 점을 직선이나 곡선으로 연결하려고 한다. 연결된 선은 반드시 직사각형의 내부만을 지나야 하며, 세 개 이상의 연결선이 한 점에서 만나서는 안 된다. 연결선과 연결선이 만나는 교차점의 개수를 가장 작게 하려고 할 때 최소 교차점의 개수를 구하는 프로그램을 작성하시오.예를 들어, 점이 아래 그림과 같이 주어졌다고 하자. 각 점의 위치는 두 개의 양의 정수로 표시된다. 첫째 정수는 점이 위치한 변을 나타내는데, 1은 윗변, 2는 밑변, 3은 왼쪽 변, 4는 오른쪽 변을 의미한다. 둘째 정수는 변 위에서의 위치를 나타낸다. 점이 윗변이나 밑변에 있는 경우는..

문제 설명세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1027      제한 사항      풀이문제를 요약하면, N개의 빌딩의 높이가 주어질 때 한 빌딩에서 보이는 건물의 최대 개수를 구..

문제 설명2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/11758      제한 사항      풀이문제를 요약하면, 주어진 세 개의 점이 일지선에 위치하는지, 시계방향으로 존재하는지 반시계방향으로 존재하는지 여부를 판정하는 것이다.이를 판정하는 것을 CCW라고 한다.이는 벡터의 외적과 관련되어 있다.벡터의 외적의 결과는 두 벡터의 직교하는 벡터인데, 이는 좌표계에 따라 다를 수 있지만 벡터가 존재하는 방향에 따라 결과가 달라진다는 것은 같다.즉, 세개의 점으로 두 개의 벡터를 만들고 두 벡터의 외적의 결과가 정답이 된다는 뜻이다..

문제 설명2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2166      제한 사항      풀이문제를 요약하면, 주어진 점이 이루는 도형의 면적을 구하는 것이다. 도형은 삼각형이나 사각형과 같이 면적을 구하기 쉬운 도형일 수도 있고 절대 공식으로 구할 수 없는 일그러진 도형일 수도 있다.해당 문제를 풀기위해 고민하다 그래픽스의 내용이 떠올랐다.그래픽스에서 도형을 그릴 때 도형을 삼각형으로 나눠 그린다.즉, 해당 문제도 도형을 삼각형으로 나눠 삼각형의 면적의 합을 구하면 된다고 생각했다. 하지만, 실제로 삼각형의 면적을 구하는 법이나 진행방법을 알지는 못했다.풀이..