본문 바로가기

Algorithm296

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

[백준/Python] 12865번 - 평범한 배낭 HTML 삽입 미리보기할 수 없는 소스 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. HTML 삽입 미리보기할 수 없는 소스 첫 줄에 물품의 수 N(1 ≤ N ≤ 100.. 2024. 1. 3.

[백준/Python] 2565번 - 전깃줄 HTML 삽입 미리보기할 수 없는 소스 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위.. 2024. 1. 3.

[백준/Python] 11054번 - 가장 긴 바이토닉 부분 수열 HTML 삽입 미리보기할 수 없는 소스 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 .. 2024. 1. 3.

[백준/Python] 11053번 - 가장 긴 증가하는 부분 수열 HTML 삽입 미리보기할 수 없는 소스 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. HTML 삽입 미리보기할 수 없는 소스 처음에는 변수에 현재까지 가장 길었을 때의 길이와, 그때의.. 2024. 1. 3.

[백준/Python] 2156번 - 포도주 시식 HTML 삽입 미리보기할 수 없는 소스 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 .. 2024. 1. 3.

[백준/Python] 10844번 - 쉬운 계단 수 HTML 삽입 미리보기할 수 없는 소스 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. HTML 삽입 미리보기할 수 없는 소스 계단수의 특성을 생각하면 쉬운 문제다. 계단수는 연속적이여야 하므로 N번째 자리에 1이라는 수가 오기 위해서는 N-1번째 자리에는 0또는 2가 와야만 한다. 그러므로 N번째 자리가 1.. 2024. 1. 3.

[백준/Python] 1463 - 1로 만들기 HTML 삽입 미리보기할 수 없는 소스 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. HTML 삽입 미리보기할 수 없는 소스 1부터 N까지 리스트를 전부 채워서 최소 횟수를 저장해서 풀었다. 좀 더 시간을 줄이기 위해서는 N에서 1까지 역순으로 수를 구하거.. 2024. 1. 3.

[백준/Python] 2580번 - 스도쿠 HTML 삽입 미리보기할 수 없는 소스 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽.. 2024. 1. 3.

[백준/Python] 9663번 - N-Queen HTML 삽입 미리보기할 수 없는 소스 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오 HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N이 주어진다. (1 ≤ N < 15) HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. HTML 삽입 미리보기할 수 없는 소스 시간 초과로 인해 pypy로 풀었다. 체스판의 크기 N이 주어지면 길이가 N인 리스트를 만든다. 리스트의 인덱스 i(0~N-1)를 체스판의 행이라 생각하고 i번째 행에 몇번째 칸에 퀸이 들어갈 수 있는지를 비교해 리스트에 저장해가며 탐색했다. 퀸이 놓인 칸으로.. 2024. 1. 3.

[백준/Python] 2304번 - 창고 다각형 HTML 삽입 미리보기할 수 없는 소스 N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 지붕의 가장자리는 땅에 닿아야 한다. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다. 그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 .. 2024. 1. 3.

[백준/Python] 2116번 - 주사위 쌓기 HTML 삽입 미리보기할 수 없는 소스 천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다. 주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아.. 2024. 1. 3.

[백준/Python] 6087번 - 레이저 통신 HTML 삽입 미리보기할 수 없는 소스 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다. HTML 삽입 미리보기할 수 없는 소스 첫째.. 2024. 1. 3.

[프로그래머스/C++] 야근 지수 HTML 삽입 미리보기할 수 없는 소스 야근을 하면 피로도가 쌓이는데 이때 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱해서 더한 값과 같다.N시간 동안 야근 피로도를 최소화 하도록 일을 한다. 1시간 동안 작업량을 1만큼 처리할 수 있다고 할 때, 퇴근까지 남은 N시간과 각 일에 대한 작업량 works가 주어지면 야근 피로도를 최소화한 값을 return하면 된다. HTML 삽입 미리보기할 수 없는 소스 works n result [4, 3, 3] 4 12 [2, 1, 2] 1 6 [1,1] 3 0 HTML 삽입 미리보기할 수 없는 소스 works는 길이 1 이상, 20,000 이하인 배열입니다. works의 원소는 50000 이하인 자연수입니다. n은 1,000,000 이하인 자연수입니.. 2024. 1. 3.

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

티스토리툴바