본문 바로가기

Algorithm290

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

[백준/Python] 2981번 - 검문 HTML 삽입 미리보기할 수 없는 소스 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 .. 2024. 1. 2.

[Algorithm/기본지식] 유클리드 호제법 HTML 삽입 미리보기할 수 없는 소스 https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324 두 정수 a, b의 최대 공약수를 G(a,b)라고 표현한다. 이때 정수 a, b, q, r (b는 0이 아니다)에 대하여 a = bq + r 이면 G(a, b) = G(b, r)이 성립한다. HTML 삽입 미리보기할 수 없는 소스 G(a, b) = g일 때, 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다. (최대공약수가 g이기 때문에 a′, b′는 서로소 이다.) a = bq + r 로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다. G(b, r) = g임을 보.. 2024. 1. 2.

[백준/Python] 17070번 - 파이프 옮기기1 HTML 삽입 미리보기할 수 없는 소스 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다... 2024. 1. 2.

[백준/Python] 17136번 - 색종이 붙이기 HTML 삽입 미리보기할 수 없는 소스 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다. 종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자. HTML 삽입 미리보기할 수 없는 소스 총 10.. 2024. 1. 2.

[백준/Python] 2566번 - 최대값 HTML 삽입 미리보기할 수 없는 소스 9×9 격자판에 쓰여진 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 수가 주어진다. 주어지는 수는 100보다 작은 자연수 또는 0이다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. HTML 삽입 미리보기할 수 없는 소스 입력을 받아 이를 2차원 리스트의 형태로 저장하고 for.. 2024. 1. 2.

[백준/Python] 18870번 - 좌표 압축 HTML 삽입 미리보기할 수 없는 소스 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. HTML 삽입 미리보기할 수 없는 소스 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 10.. 2024. 1. 2.

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

티스토리툴바