본문 바로가기
728x90
반응형

백준205

[백준] 4948번 : 베르트랑 공준 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 지정한 범위에서 소수의 개수를 찾는 문제이다. 매번 소수의 개수를 새로 구할 경우 많은 시간이 소모되어 시간초과가 발생하게 된다. 하여 소수를 구할 최댓값이 정해져 있으므로 최댓값까지 소수를 모두 판단하여 저장한 결과를 활용한다. 시간을 조금 더 단축시키기 위해 소수를 판단할 때는 해당 값의 제곱근까지만 확인한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import s.. 2023. 9. 22.
[백준] 1026번 : 보물 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 각 배열의 원소를 순서대로 곱하고 더했을 때 그 값이 최소가 되는 값을 구하는 문제이다. 어떤 값을 곱하고 더한 결과가 최소가 되려면 한 배열은 최솟값부터, 다른 배열은 최댓값부터 시작하여 각 배열의 최솟값과 최댓값을 곱하고 더해야 한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys 각 배열의 원소 개수를 입력받는다. N = int(sys.stdin.re.. 2023. 9. 20.
[백준] 11866번 : 요세푸스 문제 0 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 원형으로 앉은 사람을 차례대로 제거하는 문제이다. 원형으로 앉아 있으므로 해당 순서가 되기 전까지는 제일 앞사람을 제일 뒤로 옮기고, 해당 순서가 되면 해당 사람을 제거한다. 이런 방식으로 마지막까지 사람을 제거한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque 사람 수와 제거할 순서를 입력받는다. N, K = map(int, sy.. 2023. 9. 18.
[백준] 1934번 : 최소공배수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 두 수의 최소공배수를 구하는 문제인데 최소공배수를 한 번에 구하려고 하다 보니 시간초과가 발생하였다. 하여 유클리드 호제법을 활용하여 두 수의 최대공약수를 구하고 최대공약수와 두 수를 최대공약수로 나눈 값을 곱하여 최소공배수를 구하도록 구현하였다. 유클리드 호제법은 두 수의 최대공약수를 쉽게 구할 때 활용하는데 두 수 중 큰 수를 작은 수로 나누고 생긴 나머지를 이용하여 나누는 수를 나머지로 나누며 .. 2023. 9. 16.
[백준] 10844번 : 쉬운 계단 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 원하는 자릿수의 계단 수의 개수를 구하는 문제이다. 마지막 숫자의 값에 따라 다음으로 올 수 있는 수가 결정된다. 처음에는 자릿수를 늘려가며 계단 수를 모두 구하는 방식으로 풀이하였다. 하지만 메모리 초과가 계속적으로 발생하였다. 하여 고정된 메모리를 사용하고 최소한의 메모리를 사용할 방법을 고안해 보았다. 0과 9는 1가지, 나머지 숫자는 2가지씩 다음 숫자가 올 수 있다. 해당 숫자가 마지막 숫자로 올 수 있는 경우의 수는 이전 결과에서 해당 숫자가 마지막으로 올 수 있는 경우의 수를 더하면 된다. 예를 들어 다음 결과에서 마지막 .. 2023. 9. 14.
[백준] 11050번 : 이항 계수 1 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 이항 계수 즉, 조합의 경우를 구하는 문제이다. 이항 계수의 값은 N! / K!(N - K)! 의 결과와 동일하므로 팩토리얼을 활용해 값을 구한다. 이때 결과를 정수형으로 반환하기 위해 나눗셈의 몫을 출력하도록 구현한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys N과 K를 입력받는다. N, K = map(int, sys.stdin.readline().split()) 팩토리얼을 구해줄 함수를 선언한다. def factorial(n) 만약.. 2023. 9. 12.
[백준] 3009번 : 네 번째 점 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 세 점을 입력받고 직사각형의 나머지 한 점을 찾는 문제이다. 직사각형의 모든 점을 보면 x좌표의 값이 2개, y좌표의 값이 2개로 정해지는데, 세 개의 점을 입력받아 1개의 값만 입력받아진 값이 나머지 한 점의 각 좌표 값이 되어야 한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys x좌표를 저장할 리스트를 생성한다. xList = list() y좌표를 저장할 리스트를 생성한다. yList = list() 3번 반복하며 for _ in ran.. 2023. 9. 4.
[백준] 1966번 : 프린터 큐 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 인쇄 차례를 구할 문서를 잘 쫓아가는 것이 핵심이다. 중요도가 동일한 문서가 존재할 수 있기 때문에 인쇄 차례를 구할 문서가 현재 어디에 위치하는지를 아는 것이 중요하다. 하여 처음 입력받는 인쇄 차례를 구할 문서의 위치를 계속 변경하며 해당 문서의 위치를 파악하도록 했다. 만약 제일 큰 중요도를 가진 문서를 출력할 때 그 문서가 찾고자 하는 문서라면 인쇄 순서를 출력하도록 구현했다. sys.stdin.readline() .. 2023. 9. 2.
[백준] 11729번 : 하노이 탑 이동 순서 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 우선 하노이 탑의 원판 이동 순서를 알아야 한다. 원판이 1개일 경우에는 그냥 목표 장대로 옮기면 되지만 2개 이상일 때는 마지막 원판을 차례대로 목표 장대에 옮겨야 한다. 이때 마지막 원판을 제외하고 나머지 원판들은 시작 장대와 목표 장대를 제외한 나머지 한 장대에 옮겨놔야 한다. 이러한 하노이 탑의 원판 이동 순서를 파악하고 나서 문제를 해결하면 된다. sys.stdin.readline() 함수를 사용하기.. 2023. 8. 31.
[백준] 2805번 : 나무 자르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 절단기의 높이를 조절하며 잘리는 나무의 길이를 구하여 정답을 도출하는 문제이다. 절단기의 높이는 0부터 자를 나무의 최대 높이 중 하나이다.최대한 빠르게 정답을 도출하기 위해 이진 탐색을 활용하여 절단기 높이를 구하였다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys 나무의 수와 가져갈 나무의 길이를 입력받는다. N, M =.. 2023. 8. 29.
728x90
반응형

티스토리툴바