🗂️ 2024.07.16 TIL

Python

소수 판별하기 (자주 나오니 꼭 기억하자!)

소수 확인하는 방법:

• 어떤 수에 대해 2부터 자기 자신-1 까지의 모든 수들을 확인하며 만약 그 수로 나눠떨어지면 소수 X, 나눠 떨어지지 않으면 소수이다.

파이썬으로 16이 소수인지 판별하는 코드를 구현하면 다음과 같다:

prime = True
for i in range(2, 16):  # 2 부터 15까지 소수인지 확인하기
    if 16 % i == 0:  # 약수로 자기자신이 나눠지면 소수가 아니다.
        prime = False

print(prime)

• 결과: False

위의 코드는 판벌하고자 하는 수에 비례하기 때문에 $O(n)$ 이다.

하지만 약수의 성질(특정 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다)을 활용해서 시간복잡도를 줄일 수 있다.

• ex) 16의 약수는 1, 2, 4, 8, 16

  • 제곱근 4 를 기준으로 16을 만드는 수가 대칭되기 때문에 4 까지만 확인하면 됨.

    prime = True
    for i in range(2, int(n**0.5) + 1):  # 2부터 n의 제곱근까지 소수인지 확인하기
        if n % i == 0:  # 약수로 자기자신이 나눠지면 소수가 아니다.
            prime = False
    
    print(prime)

SQL

오늘 프로그래머스 문제를 풀면서 처음으로 세 개의 테이블을 join 하는 게 나왔다. 세 개를 join 한다고 해서 어려울 건 없었다.

• 조회시 기준이 되는 테이블을 중심으로 하나 하나씩 join 하면 혼동하지 않을 수 있다.
• 예를 들어 PATIENT 테이블, APPOINTMENT 테이블, DOCTOR 테이블을 join 할 때 다음과 같이 할 수 있다.

  FROM PATIENT p
      JOIN APPOINTMENT a ON p.PT_NO = a.PT_NO
      JOIN DOCTOR d ON a.MDDR_ID = d.DR_ID