본문 바로가기

백준16

[백준 1929번] 소수 구하기 - 에라토스테네스의 체 - 제출 코드 import math import sys m, n = map(int, sys.stdin.readline().split()) def is_prime(x): if x==1: return False for i in range(2,int(math.sqrt(x)+1)): if x%i == 0: return False return True while m 뒤에 있는 해당 수의 배수들을 지워준다 check_list = [False]+[False] + [True] * (n-1) for i in range(2,n+1): if check_list[i]==True: # 살아있으면 소수 -> 배수들을 지워주겠다 for j in range(i*2, n+1, i): check_list[j] = False return.. 2022. 1. 2.
[백준 2609번] 최대공약수/최소공배수 - 유클리드 호제법 - 짠 코드 def gcd(x, y): min1 = min([x, y]) max1 = max([x, y]) while min1 != 0: max1, min1 = min1, max1 % min1 return max1 # 최소공배수 def lcm(x, y): return x * y // gcd(x, y) a, b = map(int, input().split()) print(gcd(a,b)) print(lcm(a,b)) # 재귀과정으로 만들면 저절로 큰값이 x, 작은값이 y로 가도록 만들 수 있다. - 최대공약수 : 두가지 수가 주어졌을 때 더이상 공약수가 없을 때까지 공약수로 나눠가며 지금까지 나눈 공약수들을 곱해주면 최대공약수가 된다. 유클리드 호제법 : 두 양의 정수 a,b (a > b)에 대하여 a =.. 2022. 1. 1.
[백준 1874번] 스택 알고리즘 - 먼저 혼자짜본 코드 import sys n = int(sys.stdin.readline()) suyeol = [int(sys.stdin.readline()) for _ in range(n)] answer = [] if sorted(suyeol[suyeol.index(max(suyeol)):],reverse=True)==\ suyeol[suyeol.index(max(suyeol)):]: for i in range(1, n + 1): answer.append(i) print('+') while answer[-1] == suyeol[0]: print('-') answer.pop() suyeol.pop(0) if len(answer)==0: break else: print(.. 2022. 1. 1.
[백준 1654번] 이분탐색 ( Binary Search) - 처음 짠 코드 import sys k, n = map(int,sys.stdin.readline().split()) lansun = [] for i in range(k): lansun.append(int(sys.stdin.readline())) count = max(lansun) while True: a = 0 for i in range(k): a += lansun[i] // count if a>=n: break else: count -= 1 print(count) 처음에는 lansun리스트에서 min을 골라 1씩 빼가며 내려가면 원하는 값을 찾을 수 있을거라 생각했다. -> 시간초과 -> input을 sys.stdin.readline()으로 바꾸고 list comprehension으로 만들어 보기도 .. 2021. 12. 31.

티스토리툴바