[코테]백준 3주차

기본수학1

1. 손익분기점

• 수학으로 계산할 수 있는지 여부부터 살펴보고 코드 짜기

2. 벌집 - 중앙의 1을 중심으로 층을 나누어 품

• (이 문제는 재귀로 풀면 안되는 문제) 재귀로 풀 수 있는지 없는지 여부 살펴보기

n=int(input())
n=n-1
i=1
count=0
while i!=0:
  n=n-6*count #벌집의 형태가 1+6+6*2+ ...--> 등비수열 푸는 법 정리
  if n>0:
    count+=1
    print(count, n)
  else:
    i=0
print(count+1) 

3. 분수찾기 - 1+2+3의 패턴을 보임 (짝수/홀수의 규칙이 반대임)

• 내 코드는 시간복잡도가 O(3n) - while문 1개 , for문 2개 -> 매우 큼
  좋은 코드는 O(n) - 저런 코드를 짤려면 정말 문제를 많이 풀어봐야 할 것같다...

x=int(input())
i=1
count=1
#해당 번째 분수가 속한 집단을 찾기 위함
while i!=0: #while문 break하기 위한 i(의미 없음)
    if x>0:
        x-=count 
        count+=1
    else:
        i=0
number=count-1 #집단
location=x+number #while문 마지막 전의 x, 즉 해당 집단에서 몇번째에 있는지를 알려줌
li=[] #해당 집단의 모든 분수를 계산해 리스트로 생성 --> 리스트를 생성하지 않고 하는 방법 아래
if number%2==0: #짝수인 경우 
  for a in range(1,number+1): 
    son=a #정방
    mom=count-a #역방
    li.append(str(son)+'/'+str(mom))
else: #홀수인 경우
  for a in range(1,number+1):
      son=count-a #역방
      mom=a #정방
      li.append(str(son)+'/'+str(mom))
print(li[location-1])

#다른사람 코드
def get_fraction(n):
    i = 1
    up = False
    total = 0
    while total < n:
        total += i 
        up = not up #짝수와 홀수 집단을 나눠줌
        i += 1 #1+2+3+...
    i -= 1 #주어진 수의 집단의 넘버를 반환
    if up: #홀수
        numerator = 1 + total - n
        denominator = i - total + n
    else: #짝수
        numerator = i - total + n #(정방)식이 이해가 안가네...
        denominator = 1 + total - n
    return (numerator, denominator)
n = int(input())
fraction = get_fraction(n)
print(str(fraction[0])+'/'+str(fraction[1]))
#정말 잘 만든 코드
line=1
while X>line:
    X-=line
    line+=1    
if line%2==0:
    a=X
    b=line-X+1
else:
    a=line-X+1
    b=X   
print(a, '/', b, sep='')

7. 설탕배달 - 시간 오래 걸렸지만 결국 못품

#정답 코드
n=int(input())
bag=0
while True:
  if n%5==0: #만약 5로 나누어 떨어진다면 5로 나눈 몫을 반환 
    bag+=n//5
    print(bag)
    break
  n-=3 # 5로 나누어 떨어지지 않는다면 3을 빼고 다시 5로 나눔 #3의 배수도 5로 나누어 떨어질 수 있음
  bag+=1
  if n<0: #3을 계속 빼고도 5로 나누어 떨어지지 않는다면 -1 반환
    print(-1)
    break

9. Fly me to the Alpha Centauri #시간초과 #실패

• 노가다로 다 나열해서 패턴 찾는 문제...
  

import math
T=int(input())
for _ in range(T):
  x,y=map(int, input().split())
  distance=y-x
  if distance>3:
    i=int(math.sqrt(distance))
    if i**2==distance: #제곱(i**2)인 수는 2*i-1개
      print(2*i-1)
    elif i**2<distance<=i**2+i: #제곱(i**2)인 수 다음부터 (i**2+i)까지 2*i개
      print(2*i)
    else: # 그 외의 수는 2*i+1개
      print(2*i+1)
  else:
    print(distance)

기본수학2

소수 정리

• 에라토스테네스의 체
  : 주어진 범위에서 소수가 아닌 모든 수를 제외하는 방법
  1단계 : 1을 제뢰
  2단계 : 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
  3단계 : 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다 (2에서 지운 2와 3의 배수를 넘긴다.)
  4단계 : 위의 과정을 범위 끝까지 반복하여 소수만 남긴다.

<에라토스테네스의 체 기본 코드 1>
#에라토스테네스의 체 - 소수를 판별하는 알고리즘(대량으로 정확하게 구하는 방법)
#합성수를 지우는 방식으로 소수를 찾는 방법

n=1000
a = [False,False] + [True]*(n-1) #False 2개와 n-1개의 True로 구성된 리스트
#False 를 두개 만드는 이유는 2부터 소수여부를 판별하기 때문에 0과 1은 False로 지정하여 2부터 True일 수 있게 한것임
primes=[]

for i in range(2,n+1):
  if a[i]: #제일 처음 2를 소수로 잡고 2의 배수를 삭제 #그 다음 제일 작음 소수를 선택하여 그 배수 삭제
    primes.append(i)
    for j in range(2*i, n+1, i): #(자기자신은 빼기 위해서 *2, n까지, i배수만 빼라)
        a[j] = False
print(primes)

• n의 최대 약수가 sqrt(n)이하이기 때문에 주어진 범위 제곱근까지 검사

<에라토스테네스의 체 기본 코드 2>
def prime_list(n):
  li=[True]*(n+1)
  #n의 최대 약수가 sqrt(n)이하이기 때문에 주어진 범위 제곱근까지 검사
  #예시) 만약 범위가 120까지라면 11의 배수는 생각하지 않아도 됨 - 11**2=121
  m=int((n+1)**0.5)
  for i in range(2, m+1):#i*2해주는 이유는 2의 배수를 없앨때 2는 없애지 않기 위해 
    if li[i]:
      for j in range(i*2, n+1, i):
        li[j]=False
  return [i for i in range(2,n+1) if li[i]]

1. 소수 찾기
   1) 에라토스테네스의 체 사용 안하고 전부 찾는 코드

  N=int(input())
li=map(int, input().split())
num=0
for i in li:
  count=0
  for a in range(2,i+1): # 주어진 수 이하의 모든 수로 나누었을 때
    if i%a==0:
      count+=1
  if count==1: #나누어떨어지는 수의 갯수가 1개(자기자신)밖에 없으면 소수
    num+=1
print(num)

2) 에라토스테네스의 체 사용

N=int(input())
li=map(int, input().split())
n=max(li) #주어진 리스트에서 제일 큰 값까지 범위를 잡음
limit=[False,False]+[True]*(n-1) #index 0,1은 먼저 소수가 아님을 설정
for i in range(2,n+1):
  if limit[i]:
    for j in range(i*2, n+1, i):
      limit[j]=False
count=0
for a in li: 
  if limit[a]:
    count+=1

2. 소수

<에라토스테네스의 체로 품>
M=int(input())
N=int(input())
li=[False, False]+[True]*(N-1) #최댓값인 N까지의 모든 소수 구함
for i in range(2,N+1):
  if li[i]:
    for j in range(i*2, N+1, i):
      li[j]=False
total=[]
compare=list(range(M, N+1)) #M부터 N까지의 모든 수에서 위의 소수 리스트에 해당되는 것 total에 저장
for a in compare:
  if li[a]:
    total.append(a)
if len(total)>0:
	print(sum(total), total[0])
else:
	print(-1)

3. 소인수분해

<내가 짠 코드> - while 1개, for 1개
N=int(input())
for i in range(2,N+1):
  check=1
  while check!=0:
    if i==N:
      print(N)
      break
    elif N%i==0:
      N=N//i
      print(i)
    else:
      check=0

<다른 사람이 짠 코드> - while 문 하나
N=int(input())
i=2 #2부터 1개씩 증가하여 나눠야 하는 경우 for문 안쓰고 이렇게 할 수 있음
while N!=1:
 if N%i==0:
   N=N/i
   print(i)
 else:
   i+=1

6. 골드바흐의 추측
   
   (지우 고마웡)

#에라토스테네스의 체
L=[False,False]+[True]*(10000-1)
m=int(10000**0.5)
for i in range(2,m+1):
  if L[i]:
    for j in range(2*i, 10000+1, i):
      L[j]=False
T=int(input())
for _ in range(T):
  n=int(input())
  a=n//2 
  b=a
  while True:
    if L[a] and L[b]: #둘다 True(소수)인 경우
      print(a,b)
      break
    a-=1
    b+=1

• 느낀점

1. 그날 스터디 정리는 그날 자기 전에 끝내자! 그날 안끝내면 기억도 안나고 코드를 처음부터 다시 자야하는 일이 발생한다.
2. 백준 기본수학 1,2는 다시 풀어보자! 다른 분들의 코드와 비교해보았을때 나의 코드의 효율성이 많이 떨어진다. 좋은 코드는 내것으로 체화시키자!