조합

1. 표준 라이브러리 사용 (추천)

• 실무나 일반적인 코딩 테스트에서는 파이썬 내장 모듈인 itertools의 combinations 함수를 사용하는 것이 가장 효율적이고 빠릅니다.

from itertools import combinations

data = [1, 2, 3, 4]

# data에서 2개를 뽑는 모든 조합 구하기
result = list(combinations(data, 2))

print(result)
# 출력: [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

• 특징: 반환값은 튜플 형태의 이터레이터(Iterator)이므로, 눈으로 확인하려면 list()로 감싸주어야 합니다.

• 중복 허용 조합: 만약 중복 조합(H)이 필요하다면 combinations_with_replacement를 사용합니다.

2. 직접 구현 (알고리즘 공부용)

• 라이브러리를 사용할 수 없는 상황이나 조합의 원리를 이해해야 할 때는 백트래킹(Backtracking) 기법을 이용한 재귀 함수로 구현합니다.

• 이 코드는 start 인덱스를 이용해 이전에 선택한 요소 다음부터 탐색하도록 강제함으로써 순서를 무시하고 중복을 방지합니다.

def get_combinations(arr, n):
    result = []

    if n == 0:
        return [[]]

    for i in range(len(arr)):
        elem = arr[i]
        # 현재 원소(elem) 이후의 리스트(rest_arr)에서 n-1개를 뽑는 재귀 호출
        rest_arr = arr[i + 1:]
        
        for C in get_combinations(rest_arr, n - 1):
            result.append([elem] + C)

    return result

data = [1, 2, 3, 4]
print(get_combinations(data, 2))
# 출력: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

3. 경우의 수만 계산할 때

• 조합의 목록이 아니라, 단순히 "몇 가지 경우의 수가 나오는지" 숫자만 필요하다면 math.comb를 사용합니다. 직접 공식을 구현하는 것보다 훨씬 빠르고 정확합니다.

import math

n = 5
k = 2

# 5개 중 2개를 뽑는 경우의 수 (5C2)
count = math.comb(n, k)

print(count)
# 출력: 10

요약

---

약수 갯수 구하기

1. 단순 반복문 (숫자가 작을 때)

1부터 N까지 모든 수로 나누어 떨어지는지 확인합니다. 이해하기 쉽지만 숫자가 크면 느립니다.

def count_divisors(n):
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
    return count

print(count_divisors(15))  # 4

2. 제곱근(Root) 활용 (효율적인 방법) ⭐추천

약수는 항상 짝꿍이 있다는 점을 이용합니다(예: $3 \times 5 = 15$). 따라서 제곱근($\sqrt{N}$)까지만 검사하면 시간을 대폭 줄일 수 있습니다.

def count_divisors_fast(n):
    count = 0
    # 1부터 √n 까지만 반복
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            count += 1        # i는 약수
            if i != n // i:   # 짝꿍 약수도 카운트 (예: 3이면 5도 카운트)
                count += 1
    return count

print(count_divisors_fast(15))  # 4

• 예: 15의 경우 1부터 3($\sqrt{15} \approx 3.8$)까지만 검사합니다.
  • $i=1$: 15 나누어 떨어짐 (약수 1, 짝꿍 15) $\rightarrow$ count +2
  • $i=2$: 안 됨
  • $i=3$: 15 나누어 떨어짐 (약수 3, 짝꿍 5) $\rightarrow$ count +2
  • 종료 (총 4개)

3. 약수 리스트까지 반환하기

약수 자체를 구하고 싶다면 count 대신 리스트에 담으면 됩니다.

def get_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)  # 보기 좋게 정렬

print(get_divisors(15))  # [1, 3, 5, 15]

---

Prefix(누적합)

prefix는 앞에서부터 누적해서 더한 합을 저장한 배열이라서, 나중에 구간합을 아주 빠르게 구할 때 쓰는 도구입니다.

핵심은 prefix[r] - prefix[l]을 하면 원본 배열의 l부터 r-1까지의 합이 나온다는 점입니다.

prefix가 뭔지

예를 들어 elements = [7, 9, 1, 1, 4]라면, prefix는 보통 맨 앞에 0을 하나 두고 시작해서 [0, 7, 16, 17, 18, 22]처럼 만듭니다.

이 뜻은 prefix[1] = 7, prefix[2] = 7+9, prefix[3] = 7+9+1처럼 0번부터 그 직전까지의 합을 저장해 둔 것이라고 보면 됩니다.

왜 빼기만 하면 되나

예를 들어 원본 배열에서 인덱스 1부터 3까지의 합, 즉 9 + 1 + 1 = 11을 구하고 싶다면 prefix[4] - prefix[1]을 하면 됩니다.

실제로 prefix[4]는 7+9+1+1=18이고, prefix[1]은 7이므로 18 - 7 = 11이 되어 앞부분이 깔끔하게 빠집니다.

---

소수 판별

🔥 1️⃣ 가장 중요한 결론

👉 2부터 √n까지만 나눠본다

✅ 2️⃣ 최종 코드 (이거 외우면 끝 ⭐)

def is_prime(n):
    if n < 2:
        return False
    
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    
    return True

🔍 3️⃣ 왜 √n까지만?

약수는 항상 쌍으로 존재:

n = a × b

예:

36 = 6 × 6
36 = 4 × 9

👉 작은 쪽만 보면 큰 쪽은 자동으로 결정됨
👉 그래서 √n까지만 확인하면 충분

❗ 4️⃣ 꼭 기억할 예외

n < 2 → 소수 아님

값	결과
0	❌
1	❌
2	✅

⚡ 5️⃣ 시간복잡도

방법	복잡도
2 ~ n	O(n) ❌
2 ~ √n	O(√n) ✅

👉 무조건 √n 버전 사용

🚀 6️⃣ 여러 개 판별할 때

👉 개별 판별 말고 체(에라토스테네스) 사용

def sieve(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    
    for i in range(2, int(n**0.5)+1):
        if prime[i]:
            for j in range(i*i, n+1, i):
                prime[j] = False
    
    return prime

🎯 핵심 요약

• ❗ n < 2 처리
• 🔥 √n까지만 검사
• 🚀 여러 개면 체 사용

💡 한 줄 정리

👉 “나눠떨어지는 순간 탈락, √n까지만 보면 된다”

---