본문 바로가기

분류 전체보기313

[백준/Python] 6549번 - 히스토그램에서 가장 큰 직사각형 HTML 삽입 미리보기할 수 없는 소스 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는.. 2024. 1. 4.

[백준/Python] 11444번 - 피보나치 수 6 HTML 삽입 미리보기할 수 없는 소스 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. HTML 삽입 미리보기할 수 없는 소스 첫.. 2024. 1. 4.

[백준/C++] 10830번 - 행렬 제곱 HTML 삽입 미리보기할 수 없는 소스 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. HTML 삽입 미리보기할 수 없는 소스 행렬의 곱을 구하기 위해서는 행렬의 성질을 알아야 한다. 일반적으로 행렬의 곱은.. 2024. 1. 4.

[백준/C++] 11401번 - 이항 계수 3 HTML 삽입 미리보기할 수 없는 소스 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N) HTML 삽입 미리보기할 수 없는 소스 (N, K)를 1,000,000,007로 나눈 나머지를 출력한다 HTML 삽입 미리보기할 수 없는 소스 이항계수는 nCk로 쉽게 구할 수 있는데, 곱셈간의 나머지를 구하기는 쉽지만 나눗셈이 포함 될 경우 나머지를 계산하기가 어렵기 때문에 페르마의 소정리를 이용해서 풀었다. HTML 삽입 미리보기할 수 없는 소스 $$a^{p-2} \equiv a^{-1} \pmod{p}$$.. 2024. 1. 4.

[Algorithm/기타지식] 페르마의 소정리 HTML 삽입 미리보기할 수 없는 소스 페르마의 소정리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 수론에서 페르마의 소정리(Fermat小定理, 영어: Fermat’s little theorem)는 어떤 수가 소수일 간단한 필요 조건에 대한 정리이다. 추상적으로, 소수 크기의 유한체 위 ko.wikipedia.org 페르마의 소정리는 어떤 수가 소수일 간단한 필요 조건에 대한 정리이다. p가 소수이고, a가 정수 일 때, 페르마의 소정리에 따르면, $$a^{p} \equiv a \pmod{p}$$ 임의의 정수 a의 p승을 p로 나눈 나머지는 a를 p로 나눈 나머지와 같다. HTML 삽입 미리보기할 수 없는 소스 먼저 a가 p의 배수라면 좌변과 우변 모두 나머지가 0이므로 성립함을.. 2024. 1. 4.

[백준/C++] 1629번 - 곱셈 HTML 삽입 미리보기할 수 없는 소스 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. HTML 삽입 미리보기할 수 없는 소스 제곱의 횟수가 매우 많기 때문에 이를 구하기 위해서는 제곱하는 횟수 B를 B/2 로 나눈 뒤, B/2번 제곱했을 경우의 값을 구하고 B/2를 곱하는 방법으로 문제를 풀었다. B/2번 곱하는 것은 재귀로 만들었다. 그리고 .. 2024. 1. 4.

[백준/C++] 25682번 - 체스판 다시 칠하기 2 HTML 삽입 미리보기할 수 없는 소스 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시.. 2024. 1. 4.

[백준/C++] 1780번 - 종이의 개수 HTML 삽입 미리보기할 수 없는 소스 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. .. 2024. 1. 4.

[백준/C++] 2630번 - 색종이 만들기 HTML 삽입 미리보기할 수 없는 소스 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 .. 2024. 1. 4.

[백준/Python] 1931번 - 회의실 배정 HTML 삽입 미리보기할 수 없는 소스 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝.. 2024. 1. 4.

[백준/Python] 11399번 - ATM HTML 삽입 미리보기할 수 없는 소스 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 .. 2024. 1. 4.

[백준/C++] 11047번 - 동전 0 HTML 삽입 미리보기할 수 없는 소스 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. HTML 삽입 미리보기할 수 없는 소스 처음에는 동전이 배수로 .. 2024. 1. 4.

[프로그래머스/C++] 숫자 게임 HTML 삽입 미리보기할 수 없는 소스 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 한다. 이때 규칙은 아래와 같다. 모든 사원이 무작위로 자연수를 하나씩 부여받는다. 각 사원은 딱 한 번씩 경기를 합니다. 각 경기당 A팀, B팀에서 한 사원씩 나와 서로의 수를 공개하고, 그때 숫자가 큰 쪽이 승리하며 승리한 사원이 속한 팀은 승점을 1점 얻게 된다. 만약 숫자가 같다면 누구도 승점을 얻지 않습니다. 이 때, 전체 사원이 숫자를 부여받았으며, A팀은 자신들의 출전 순서를 전부 공개했다. B팀이 A팀의 출전순서를 보고 최대 승점을 얻는다면 얼마를 얻게 되는지 결과를 return하면 되는 문제다. HTML 삽입 미리보기할 수 없는 소스 A B result [5,1,3,7] [2,2,6.. 2024. 1. 4.

[백준/C++] 10986번 - 나머지 합 HTML 삽입 미리보기할 수 없는 소스 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. HTML 삽입 미리보기할 수 없는 소스 처음에는 이전에 풀었던 누적 합.. 2024. 1. 3.

[백준/C++] 11659번 - 구간 합 구하기 4 HTML 삽입 미리보기할 수 없는 소스 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. HTML 삽입 미리보기할 수 없는 소스 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. HTML 삽입 미리보기할 수 없는 소스 구간합 구하기 문제인데 N개의 원소를 입력받고 M개의 구간의 합을 출력하는 문제였다. M개의 구간마다 원소를 더해서 출력하기에는 시간이 오래 걸릴 것 같아서 숫자를 입력받.. 2024. 1. 3.

이전 1 ··· 16 17 18 19 20 21 다음

티스토리툴바