🧮 알고리즘 풀이 노트

알고리즘 개념들을 정리한 노트입니다.

sys.stdin.readline

📝 핵심 개념

• sys.stdin.readline()은 Python의 기본 input() 함수보다 빠른 입력 방식입니다.
• 대량의 데이터를 처리하는 알고리즘 문제에서 시간 초과를 방지하는 핵심 기법입니다.
• 코딩 테스트에서 입력이 많은 문제는 반드시 이 방식을 사용해야 합니다.

⚡ 빠른 이유

1. 버퍼링 방식의 차이:

   • sys.stdin.readline()은 OS 레벨의 버퍼에서 직접 데이터를 가져옵니다.
   • input()은 내부적으로 readline()을 호출한 후 추가 처리 과정을 거칩니다.

2. 최소한의 처리:

   • input()은 프롬프트 출력, 개행 문자 제거 등 추가 작업을 수행합니다.
   • sys.stdin.readline()은 이러한 추가 처리 없이 한 줄을 그대로 가져옵니다.

3. 저수준 최적화:

   • sys.stdin.readline()은 더 저수준(low-level)의 함수로 오버헤드가 적습니다.
   • 대용량 입력 처리에서 성능 차이가 두드러집니다.

🔍 사용 방법

import sys

# 한 줄 입력받기
n = int(sys.stdin.readline())

# 공백으로 구분된 정수 입력받기
a, b = map(int, sys.stdin.readline().split())

# 여러 줄 입력받기
data = [int(sys.stdin.readline()) for _ in range(n)]

# 주의: 개행문자(\n)가 포함되므로 필요시 제거
s = sys.stdin.readline().rstrip()

📊 약수 (Divisors)

약수

📝 핵심 개념

• N의 배수는 항상 N의 약수를 가진다.
• N 이하의 자연수에서 K를 약수로 가지는 개수는 N/K이다.

📈 예시: 1~10까지의 약수 분석

숫자	약수가 되는 수	개수
1	1, 2, 3, 4, 5, 6, 7, 8, 9, 10	10개
2	2, 4, 6, 8, 10	5개
3	3, 6, 9	3개
4	4, 8	2개
5	5, 10	2개
6	6	1개
7	7	1개
8	8	1개
9	9	1개
10	10	1개

🧮 계산 방법

f(1) + f(2) + ... + f(N)을 계산할 때:

• 1은 총 N/1번 등장
• 2는 총 N/2번 등장
• 3은 총 N/3번 등장
• ...

🔢 공식

N은 초기값, K는 N 이하의 숫자(1~N)일 때:

• 약수의 합: (N // K) * K이다.

🔍 10 이하의 수 경우

1은 1, 2, 3, 4, 5, 6, 7, 8, 9, 10의 약수입니다. (10개)
2는 2, 4, 6, 8, 10의 약수입니다. (5개)
3은 3, 6, 9의 약수입니다. (3개)
4는 4, 8의 약수입니다. (2개)
5는 5, 10의 약수입니다. (2개)
6은 6의 약수입니다. (1개)
7은 7의 약수입니다. (1개)
8은 8의 약수입니다. (1개)
9는 9의 약수입니다. (1개)
10은 10의 약수입니다. (1개)

f(1) + f(2) + ... + f(10)을 계산할 때, 1은 총 10번, 2는 총 5번, 3은 총 3번, ... 이런 식으로 더해집니다. 즉, k가 N 이하의 수들의 약수로 몇 번 등장하는지를 세면 됩니다.

N은 초기값, K는 N이하의 숫자 (1~N)

• (N // K) * K

---

🔢 소수 (Prime Numbers)

에라토스테네스의 체

📝 소수(Prime Number)

소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다.

🧩 에라토스테네스의 체 (Sieve of Eratosthenes)

에라토스테네스의 체는 특정 범위 내의 모든 소수를 찾는 효율적인 알고리즘입니다.

원리

1. 2부터 n까지의 모든 수를 나열합니다.
2. 아직 지워지지 않은 수 중 가장 작은 수(처음에는 2)를 소수로 채택합니다.
3. 해당 소수의 배수를 모두 지웁니다.
4. 2~3 과정을 반복합니다.

구현 방법

def eratos(n=1000):
    # 0, 1은 소수가 아니므로 False로 처리
    num = [False, False] + [True] * (n - 1)

    prime = []
    for i in range(2, n + 1): # 2부터 n까지
        if num[i]: # 소수인 경우
            prime.append(i) # 소수 리스트에 추가
            for j in range(2 * i, n + 1, i): # 소수의 배수는 소수가 아니므로 False로 처리
                num[j] = False
    return prime

시간 복잡도

• ⏱️ O(N log log N): 일반적인 구현 시간 복잡도
• ⏱️ 특정 수가 소수인지만 판별할 때는 O(√N)의 방법이 더 효율적입니다.

최적화 포인트

1. 최적화된 구현에서는 i의 제곱부터 시작해 배수를 지울 수 있습니다. (for j in range(i*i, n+1, i))
2. n의 제곱근까지만 반복해도 됩니다. (for i in range(2, int(n**0.5)+1))

활용

• 특정 범위 내의 모든 소수를 찾는 문제
• 소인수분해
• 소수 관련 계산이 필요한 다양한 문제

💡 소수 판별만 필요한 경우, 해당 수의 제곱근까지만 나누어보는 간단한 방법으로 O(√N) 시간에 구현할 수 있습니다.

---

🔀 최대공약수와 최소공배수 (GCD & LCM)

유클리드 호제법

📝 핵심 개념

• 최대공약수(GCD, Greatest Common Divisor): 두 수의 공통된 약수 중 가장 큰 수
• 최소공배수(LCM, Least Common Multiple): 두 수의 공통된 배수 중 가장 작은 수
• 유클리드 호제법: 두 수의 최대공약수를 효율적으로 구하는 알고리즘

🧮 유클리드 호제법 원리

두 자연수 a, b에 대해 (a > b):

1. a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
2. 이 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 최대공약수이다.

📈 구현 방법

# 재귀를 이용한 방법
def gcd(a, b):
    return gcd(b, a % b) if a % b else b

# 반복문을 이용한 방법
def gcd_loop(a, b):
    while b:
        a, b = b, a % b
    return a

🔢 최소공배수 구하기

최소공배수는 두 수의 곱을 최대공약수로 나눈 값입니다.

def lcm(a, b):
    return a * b // gcd(a, b)

🔍 예시

GCD(24, 16) 계산:
24 % 16 = 8
16 % 8 = 0
∴ GCD(24, 16) = 8

LCM(24, 16) 계산:
LCM = 24 * 16 / 8 = 48

📊 활용

• 분수의 약분
• 여러 수의 최대공약수/최소공배수 구하기
• 확장 유클리드 알고리즘 (ax + by = gcd(a,b) 형태의 해 구하기)
• 모듈러 역원 계산

💡 여러 수의 최대공약수와 최소공배수

• 여러 수의 최대공약수: 각 쌍의 최대공약수를 구하는 과정을 반복
• 여러 수의 최소공배수: 각 쌍의 최소공배수를 구하는 과정을 반복