[코테 준비 : day12]

백 투 더 비기닝..

계속 코테 준비를 하면서 이제는 기초적인 구현이나 알고리즘은 작성할 수 있다고 생각했다.
하지만 내 오만이였다. 어제는 KT 에이블스쿨 코딩 테스트를 봤는데 3문제 중 1솔인듯?아닌듯한 느낌으로 풀었다.
난 정말 최선을 다했지만 풀지못했다. 그래서 내린 결론은 처음으로 다시 돌아가는 것이다.
아무리 기초 문제라도 그 알고리즘을 확실히 정리하고 알아가서 어려운 문제도 풀 수 있도록 해야한다. 속도가 문제가 아니다!

사실 KT 에이블스쿨에 들어가고싶은 마음이 아~주 컸지만 아직 내 실력이 따라가지 못하나보다. 아직 결과는 나오지 않았지만! 다음에 좋은 기회가 왔을 때 내 실력으로 놓치지 않도록 하고싶다. 다시 가보자..!

1. 소수 구하기
   https://www.acmicpc.net/problem/1929
   
   고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 내가 알고리즘 문제를 풀 때 소수가 필요한 부분에서 자주 사용했다.

m,n=map(int,input().split())

for i in range(m,n+1):
    if i==1:#1은 소수가 아니므로 제외
        continue
    for j in range(2,int(i**0.5)+1):
        if i%j==0: #약수가 존재하므로 소수가 아님
            break   #더이상 검사할 필요가 없으므로 멈춤
    else:
        print(i)

2. 베르트랑 공준
   https://www.acmicpc.net/problem/4948
   
   소수를 구하고 리스트에 담는다. 그리고 n보다 크고 2n보다 작다면 카운트!

import sys, math

def d(N): # 소수를 찾는 함수
    if N == 1:
        return False
    for i in range(2, int(math.sqrt(N))+1):
        if N % i == 0:
            return False
    return True
    
sosu = [] # 소수를 담을 리스트 선언
for i in range(2, 2*123456):  # 조건 범위안에 소수를 찾고 리스트에 추가
    if d(i):
        sosu.append(i)
        
while True:
    N = int(sys.stdin.readline()) # 입력이 여러개 일땐 sys 사용
    cnt = 0 # 갯수세기
    
    if N == 0: # 0이 입력되면 출력X
        break
        
    for i in sosu: # 소수 리스트안에 숫자를 하나씩 꺼내서 확인
        if N < i <= 2*N: # N보다 크고 2N보다 작거나 같으면 갯수 카운트 +1
            cnt += 1

    print(cnt)

3. 최대공약수 최소공배수
   https://www.acmicpc.net/problem/2609
   
   아주 간단하게 math 라이브러리에서 꺼내면 되는 것인데 잊고있었다. 기억하기 위해 기록!
   gcd: 최대공약수
   lcm: 최소공배수

import math

a, b = map(int, input().split())

print(math.gcd(a, b))
print(math.lcm(a, b))

4.골드바흐의 추측
https://www.acmicpc.net/problem/9020

import math

def d(N): # 소수 판별 함수
    if N == 1:
        return False
    for i in range(2, int(math.sqrt(N))+1):
        if N % i == 0:
            return False
    return True
    
N = int(input()) # 테스트 케이스 수 입력

for _ in range(N):
    num = int(input()) # 짝수 입력
    
    A = num // 2 # 두 수 중 줄어드는 변수
    B = num // 2 # 두 수 중 늘어나는 변수
    
    for _ in range(num // 2):
        if d(A) and d(B): # 두 수가 소수이면 출력
            print(A, B)
            break
        else: # 소수가 아니면 두 수를 줄이고 늘리기
            A -= 1
            B += 1

5. 모든수열, 조합
   https://www.acmicpc.net/problem/10974
   https://www.acmicpc.net/problem/2407
   
   
   이 문제들도 라이브러리를 잘 알고 있다면 쉽게 풀 수 있다. 기억하자!

from itertools import permutations
n=int(input())
num=[]
for i in permutations(range(1,n+1),n):
    print(*i)
    

from math import comb
n, m = map(int, input().split())
print(comb(n, m))