바닥부터 시작하는 개발 공부

알고리즘 유형: 수학 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 풀이 import sys N = int(sys.stdin.readline().strip()) i = 2 while N!=1: if N%i==0: N=N//i print(i) i=2 else: i+=1

알고리즘 유형: 수학 문제 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) 출력 첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다. 풀이 최소 공배수는 두 수의 곱을 최대 공약수로 나눠준것과 같다 이를 이용하여 쉽게..

알고리즘 유형: 수학 문제 하루에 한 시간 단위로 일을 하거나 일을 쉬어도 된다. 하루에 한 시간 일하면 피로도는 $A$ 만큼 쌓이고 일은 $B$ 만큼 처리할 수 있다. 만약에 한 시간을 쉰다면 피로도는 $C$ 만큼 줄어든다. 단, 피로도가 음수로 내려가면 0으로 바뀐다. 당연히 일을 하지 않고 쉬었기 때문에 처리한 일은 없다. 피로도를 최대한 $M$ 을 넘지 않게 일을 하려고 한다. $M$ 를 넘기면 일하는데 번아웃이 와서 이미 했던 일들도 다 던져버리고 일을 그만두게 된다. 번아웃이 되지 않도록 일을 할때 하루에 최대 얼마나 일을 할 수 있는지 구해보자. 하루는 24시간이다. 입력 첫 번째 줄에 네 정수 $A,$B$,$C$,$M$이 공백으로 구분되어 주어진다. 맨 처음 피로도는 0이다. 출력 하..

알고리즘 유형: 수학 문제 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다. 출력 첫째 줄에 B진법 수 N을 10진법으로 출력한다. 풀이 10을 넘어가는 숫자는 10진법 내에서 표기가 안되므로 알파벳을 사용해서 입력을 받습니다 각 숫자 혹은 알파벳이 10진법에서 어떤 숫자를 의미하는지 저장해둘 딕셔너리를 하나 만들어두겠습니다. 알파벳을 하나하나 타이..

알고리즘 유형: 수학, 브루트 포스 문제 자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다. 출력 입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다. 풀이 일단 최대 공약수를 계산해주겠습니다 두 수 a,b의 최대 공약수는 작은 수 min(a,b)를 넘어 가지 않으며 a와 b를 나누었을때 나누어떨어지는 수입니다 range를 통해 min(a,b)부터 1까지 스캔해주면서 나누어지면 반복문을 탈출하고 이때의 숫자를 return 합니다 숫자의 갯수는 최소 2 최대 3입니다. 조건문을 통해 각각의 경우를 나누어줍..

알고리즘 유형: 수학(기하학) 문제 시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다. 1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 ..

알고리즘 유형: 다이나믹 프로그래밍 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 풀이..

알고리즘 유형: 다이나믹 프로그래밍 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 출력 좀 까다로웠던 문제였습니다. 처음에는 탐욕법을 먼저 생각했었는데요 아이디어는 다음과 같았습니다 연산1. 3으로 나누기 연산2. 2로 나누기 연산3. 1 빼기의 세가지 연산 중에서 가장 숫자를 크게 감소 시키는 순이 1, 2,3 순이..