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