본문 바로가기

분류 전체보기307

[백준/Python] 2635번 - 수 이어가기 HTML 삽입 미리보기할 수 없는 소스 다음과 같은 규칙에 따라 수들을 만들려고 한다. 첫 번째 수로 양의 정수가 주어진다. 두 번째 수는 양의 정수 중에서 하나를 선택한다. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다. 첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 .. 2024. 1. 5.

[백준/Python] 11286번 - 절댓값 힙 HTML 삽입 미리보기할 수 없는 소스 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 .. 2024. 1. 5.

[백준/Python] 11279번 - 최대 힙 HTML 삽입 미리보기할 수 없는 소스 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. HTML 삽입 미리보기할 수 없는 소스 입력.. 2024. 1. 5.

[백준/Python] 10816번 - 숫자 카드 2 HTML 삽입 미리보기할 수 없는 소스 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되.. 2024. 1. 5.

[프로그래머스/C++] 풍선 터트리기 HTML 삽입 미리보기할 수 없는 소스 n개의 풍선이 일렬로 나열되어 있다고 하자. 이 때, 모든 풍선에는 서로 다른 숫자가 써져 있다.다음 규칙에 따라 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터뜨리려고 한다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터뜨린다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생기면, 빈 공간이 없도록 풍선들을 중앙으로 밀착 시킨다 여기서 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터뜨리는 행위는 최대 1번만 할 수 있도록 제한 되어있다.즉, 한번이라도 인접한 두 풍선 중 번호가 더 작은 풍선을 터뜨리면 이후에는 번호가 큰 풍선만 터뜨려야 한다. 이 규칙에 따르면 어떤 풍선은 어떤 방법을 쓰더라도 절대 마지막까지 남길 수 없다. 이때, 최후까지 남.. 2024. 1. 5.

[프로그래머스/C++] 경사로의 개수 (2023 현대모비스 알고리즘 경진대회 예선) HTML 삽입 미리보기할 수 없는 소스 문제 설명 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/214290 위와 같이 맵이 주어지면 방문할 수 있는 경사로를 [1, -2, -1, 0, 2, 1, -2, -1, 0, 2]와 같은 형태로 주고, 얼마나 경사로를 반복할지 횟수 k를 알려준다. 한번에 이동할 수 있는 경사로는 상하좌우로만 이동할 수 있으며 이전에 방문한 경사로도 방문 할 수 있다. 이때 위 조건을 만족하는 경로의 수를 전부 구해 1000000007로 나눈 나머지를 return하면 된다. HTML 삽입 미리보기할 수 없는 소스 3 ≤ grid의 길이 = n ≤ 8 3 ≤ grid[i]의 길이 = m ≤ 8 0 ≤ grid[i][j.. 2024. 1. 5.

[백준/Python] 1920번 - 수 찾기 HTML 삽입 미리보기할 수 없는 소스 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. HTML 삽입 미리보기할 수 없는 소스 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. HTML 삽입 미리보기할 수 없는 .. 2024. 1. 4.

[백준/C++] 2110번 - 공유기 설치 HTML 삽입 미리보기할 수 없는 소스 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사.. 2024. 1. 4.

[백준/Python] 1654번 - 랜선 자르기 HTML 삽입 미리보기할 수 없는 소스 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 .. 2024. 1. 4.

[백준/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.

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

티스토리툴바