본문 바로가기

분류 전체보기

 (63)
BOJ 1165 : 소인수 분해 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 풀이 소인수 분해는 가장 작은 나눠지는 인수들로 분해하는 것인데, 나는 컴퓨터 속도를 믿고,, 시간복잡도가 O^2 인 계산을 때려버렸다. 그 이유는 중간에 break 문이 있기 때문에 간헐적으로 큰 값이 아니면 충분히 커버가 가능할 것이라 생각했기 때문 그래서 해답은 2부터 주어진 수인 10000000까지 차례로 나누다가 나누어 떨어지는 수가 있으면 추가하고 break를 건다, 그리고 해당 값으로 N을 나눴을 때 1이하로 떨어지면 처음의 while을 멈춘다. import sys if __name__ == '__main__': n = int(sys.stdin.readline()) soinsu_list = [] while n > 1: for..
BOJ 2581 : 소수 문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 풀이 이전 문제와 동일하지만, 범위를 주고 풀어라는게 추가되었다. 이전 문제와 달리 범위가 있으므로 시간복잡도가 증가하게 되면 시간초과가 의심되었다. 그래서 처음부터 전체 소수의 범위를 줬기 때문에 이를 활용해서 prime_list를 구하고 거기서 범위내에 있는 소수들만 추렸다. from re import X import sys if __name__ == '__..
BOJ 1978 : 소수 찾기 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 풀이 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 즉 1이면 소수가 아니고, 2이상의 수부터 N까지 나눴을 때, 나누어 떨어지는 수는 제외하면 된다. import sys if __name__ == '__main__': n = int(input()) a = list(map(int, input().split())) count = n for i in a: if i == 1: count -= 1 continue for j in range(2, i): if i % j == 0: count -= 1 break print(count) 이 문제도 갑자기 소수의 정의가 생각이 안나서 다시 찾아보고 풀었다. 근..
BOJ 2839 : 설탕배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 풀이 import sys # 그리디 알고리즘 if __name__ == '__main__': N = int(sys.stdi..
BOJ 2775 : 부녀회장이 될테야 문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 풀이 import sys def data_sum(data_list, n): floor_d_list = [] ..
BOJ 10250 : ACM 호텔 그림 1. H = 6 이고 W = 12 인 H × W 호텔을 간략하게 나타낸 그림 위와 같이 생긴 호텔에서 방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다. 즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다. 여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다. import sys if __name__ == '__main__': num = int(..
BOJ 2869 : 달팽이는 올라가고 싶다. 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. import sys import math if __name__ == '__main__': A, B, V = map(int, sys.stdin.readline().split()) day = (V - B) / (A - B) print(math.ceil(day)) 대충 계산을 해보면, V 만큼에서 자는 동안 마지막 날 내려오는 B 만큼을 뺀 것을, 하루에 올라가는 양(A-B)를 나누어서 올림 연산하면 된다. 2..
BOJ 1193 : 분수찾기 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. if __name__ == '__main__': x = int(input()) sum_n = 0 n = 0 while not (n-1*(n)/2 < x

티스토리툴바