본문 바로가기

Algorithm296

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

[백준/Python] 2292번 - 벌집 HTML 삽입 미리보기할 수 없는 소스 육각형으로 이루어진 벌집이 있고, 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호가 주어진다. 이때 1에서 N번 방 까지 갈때 몇개의 방을 지나는지 구하는 문제 HTML 삽입 미리보기할 수 없는 소스 1을 기준으로 주변에 방은 6, 12, 18 ...개씩 6의 구구단 형식으로 늘어나는 것을 볼 수 있다. 이를 활용하면 정수 N이 주어졌을 때 1로부터 몇 칸 떨어져 있는지 구할 수 있다. 1 => 1 2~7 => 1+(1~6) *1로 부터 같은거리 만큼 떨어져 있는 수는 6개 8~19 => 1+6+(1~12) *1로 부터 같은거리 만큼 떨어져 있는 수는 12개 20~37=> 1+6+12+(1~18) *1로 부터 같은거리 만큼 떨어져 있는 수는 .. 2024. 1. 2.

[Algorithm/기본지식] 소수 판별하기 HTML 삽입 미리보기할 수 없는 소스 정수 N이 주어졌을 때, 소수인지 아닌지 판별하는 방법은 2~N의 제곱근 사이의 수들로 정수 N이 나뉘어지는지 확인하면 된다. $$a=\sqrt{N}$$ $$N=b_1\times b_2\times ...b_n\ \left(N의\ 소인수\ 분해\right)$$ 임의의 정수 N의 제곱근을 a라고 한다. 정수 N이 소인수 분해된다고 가정 했을 때, 가장 큰 소인수가 a보다 크거나 같다면 정수 N의 남은 소인수는 무조건 a보다 같거나 작을 수 밖에 없다. a가 N의 제곱근이라서 정수 N은 (a보다 큰 소인수 * a보다 작은 소인수)로 나타나기 때문이다. 이를 활용하면 1. N이 소수가 아닐 때, a보다 큰 소인수가 없는 경우 2. N이 소수가 아닐 때, a보다 크.. 2024. 1. 2.

[백준/Python] 11653번 - 소인수분해 HTML 삽입 미리보기할 수 없는 소스 정수 N이 주어졌을 때, 소인수 분해를 해야한다. (단, 1 입력 시 출력X) HTML 삽입 미리보기할 수 없는 소스 정수 N을 소인수분해 하기 위해서, 정수 N이 소수인지 아닌지 판별하는 방법을 활용했다. HTML 삽입 미리보기할 수 없는 소스 정수 N의 제곱근을 a라고 했을 때, 정수 N의 소인수 중 a보다 크거나 같은 소인수가 존재 하면, 나머지 소인수는 전부 a보다 작거나 같을 수 밖에 없다. 그러므로 for 문을 이용해 2부터 N의 제곱근 사이의 수로 정수 N이 나눠지는지 확인하고, 나눠지고 남은 수를 출력하면 소인수 분해가 끝난다. N의 소인수들이 전부 a보다 작거나 같을 경우 정수 N의 소인수를 전부 구할 수 있다. N의 소인수 중 a보다 큰 소인수.. 2024. 1. 2.

[프로그래머스/Python] 하노이의 탑 HTML 삽입 미리보기할 수 없는 소스 하노이 탑은 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하면, 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 한다. 이 때, 1번 기둥에 있는 원판의 개수 n이 매개변수로 주어지면 n개의 원판을 3번 원판으로 최소로 옮기는 방법을.. 2024. 1. 2.

[Algorithm/기본지식] 소수 판별하기 정수 N이 소수인지 아닌지 판별하는 방법 정수 N이 주어졌을 때, 소수인지 아닌지 판별하는 방법은 2~N의 제곱근 사이의 수들로 정수 N이 나뉘어지는지 확인하면 된다.$$a=\sqrt{N}$$$$N=b_{1}\times b_{2}\times b_{3}\times\cdots\times b_{n} $$ (N의 소인수분해)임의의 정수 N의 제곱근을 a라고 한다. 정수 N이 소인수 분해된다고 가정 했을 때, 가장 큰 소인수가 a보다 크거나 같다면 정수 N의 남은 소인수는 무조건 a보다 같거나 작을 수 밖에 없다.a가 N의 제곱근이라서 정수 N은 (a보다 큰 소인수 * a보다 작은 소인수)로 나타나기 때문이다.이를 활용하면1. N이 소수가 아닐 때, a보다 큰 소인수가 없는 경우2. N이 소수가 아닐 때.. 2023. 2. 10.

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

티스토리툴바