수학 공식

코딩 테스트 문제를 풀 때 머릿속에 바로 떠올려야 할 '수학 공식 템플릿'

이 식들만 외워도 웬만한 Lv.1~2 수학 문제는 해결됩니다.

---

1. 경우의 수 (조합)

'의상' 문제처럼 여러 항목 중 하나씩 골라 조합할 때 씁니다.

• 공식: (a+1)×(b+1)×(c+1)⋯−1
• 의미:
  • a,b,c: 각 카테고리의 요소 개수
  • +1: 해당 카테고리를 '선택하지 않는' 경우의 수 추가
  • -1: 모든 카테고리를 '선택하지 않은' 경우(공집합) 제외

---

2. 최대공약수(GCD)와 최소공배수(LCM)

• 핵심: 두 주기가 서로 맞물리는 시점을 찾을 때 씁니다.
• 용도: "A 작업은 3일마다, B 작업은 4일마다 실행될 때 같이 실행되는 날은?" 같은 문제.

두 수의 관계를 풀 때 필수입니다. 유클리드 호제법이라는 공식 하나면 끝납니다.

• **최대공약수(GCD) 구하기 (재귀):**Java
• int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
• 최소공배수(LCM) 구하기:
  • 공식: (a×b)/GCD
  • 의미: 두 수를 곱한 값을 최대공약수로 나누면 최소공배수가 됩니다.

---

3. 등차수열의 합

'x만큼 간격이 있는 n개의 숫자'나 '1부터 N까지의 합'을 구할 때 씁니다. 루프를 돌리지 않아도 되어 성능이 압도적입니다.

• 공식: **(**n×(first+last))/2
• 의미:
  • n: 숫자의 개수
  • first: 첫 번째 숫자
  • last: 마지막 숫자
• 응용: 1부터 100까지의 합 = 100×(1+100)/2=5050

---

4. 소수(Prime Number) 판별

주어진 숫자가 소수인지 확인할 때 가장 효율적인 범위입니다.

• 공식: 2부터 **루트 N(Math.sqrt(N))*까지만 나누어 떨어지는지 확인
• 이유: 약수는 대칭을 이루기 때문에 제곱근까지만 확인하면 그 이후는 확인할 필요가 없습니다. 시간 복잡도를 $O(N)$에서 $O(\sqrt{N})$으로 줄여줍니다.

---

5. 나머지 연산 (Modular)

• 핵심: num % n을 하면 결과는 무조건 0부터 n-1 사이에서만 돕니다.
• 용도: 배열의 인덱스를 뱅글뱅글 돌려야 할 때(원형 큐), 혹은 대량의 숫자를 특정 범위로 압축할 때(해시 함수).

---

💡 암기 팁

지금 당장 이 식들을 다 외우기보다, 포스트잇에 딱 요렇게만 적어서 모니터 옆에 붙여두세요.

1. 조합: (n+1) 곱하고 -1
2. 공배수: (a*b) / 최대공약수
3. 합계: n(첫+끝) / 2
4. 소수: 루트까지만 나누기