지난 학습 요약
지난 세션(4/24)에서는 이진 탐색을 처음 학습하며 빈칸/디버깅/함수 작성 4문제 전부 1차 정답으로 끝냈다. 코드 추적 습관이 강화돼 print(f"left=... mid=...")로 실행을 시뮬레이션하며 풀이하는 흐름이 자리잡았다. bisect 라이브러리는 완성형에서만 쓰고 빈칸은 직접 구현이 정석이라는 실전 전략도 같이 정리.
오늘 수업 계획
시험 출제 범위 중 자주 등장하는 수학 파트를 한 번에 정리한다. 소수 판별의 √n 최적화부터 시작해서, 같은 원리로 풀리는 약수 구하기, 그리고 외우면 끝나는 공식 두 개(유클리드 호제법, LCM 공식)까지. 마지막은 GCD를 이용해 N개 수의 LCM을 구하는 함수 작성 문제로 마무리.
학습 내용 정리
1. 소수 판별 — √n 최적화
소수는 1과 자기 자신만으로 나누어떨어지는 자연수(1 제외). 가장 단순한 풀이는 2부터 n-1까지 다 나눠보는 것이다.
def is_prime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True문제는 n이 1,000,000 같은 큰 수면 백만 번 다 돌아야 한다는 점. 그래서 √n까지만 보면 충분하다는 최적화가 핵심이다.
왜 √n까지면 충분한가? (시각적 설명)
36의 약수 쌍을 적어보면 √36 = 6을 기준으로 거울처럼 대칭이다.
1 × 36 = 36
2 × 18 = 36
3 × 12 = 36
4 × 9 = 36
6 × 6 = 36 ← √36 (중간점)
9 × 4 = 36 ← 위와 대칭
12 × 3 = 36
...즉 √n 이하에서 약수를 못 찾으면 √n 초과에서도 못 찾는다(대칭이니까). 그래서 검사 범위를 √n까지로 줄이면 시간복잡도가 O(n) → O(√n)으로 떨어진다.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n: # i*i <= n 은 i <= √n 과 같음
if n % i == 0:
return False
i += 1
return True⚠️ 포인트:
i * i <= n은 제곱근 함수(math.sqrt)를 쓰지 않고도 같은 효과를 낸다. 실수 오차도 없고 정수 연산이라 빠르다. 이 패턴은 시험에 그대로 등장한다.
Java vs Python — 정수 연산 비교
| 연산 | Java | Python |
|---|---|---|
| 정수 나눗셈 | 5 / 2 = 2 (자동) | 5 / 2 = 2.5 (실수), 5 // 2 = 2 |
| 나머지 | % | % |
| 거듭제곱 | Math.pow(a, b) (실수 반환) | a ** b (정수 반환) |
Java에서 int / int = int 로 자동 정수화되는 게, Python에서는 명시적으로 //로 적어줘야 한다. 22차 이진 탐색에서도 이 함정이 디버깅 문제로 나왔는데, 오늘 LCM 공식에서도 같은 패턴이 또 등장. 정수 결과가 필요한 곳에선 무조건 // — 외우자.
2. 약수 구하기 — 짝꿍 패턴
약수 구하기도 √n 트릭을 그대로 쓴다. 다만 핵심 아이디어가 하나 더 추가된다.
i가 약수면
n // i도 자동으로 약수다. 두 개를 동시에 수집하면 √n까지만 돌면 된다.
def get_divisors(n):
small = []
large = []
i = 1
while i * i <= n:
if n % i == 0:
small.append(i)
if i != n // i: # 제곱수 함정 처리
large.append(n // i)
i += 1
return small + large[::-1]⚠️ 제곱수 함정
36의 경우 i=6일 때 짝꿍 n//i = 6 — 같은 수다. 이 체크를 빼먹으면 6이 두 번 들어가 [1,2,3,4,6,6,9,...]이 된다. 이게 시험 디버깅 문제의 단골 함정.
디버깅 문제
def count_divisors(n):
count = 0
i = 1
while i * i <= n:
if n % i == 0:
count += 2 # 버그: 제곱수에서 2번 셈
i += 1
return count
# count_divisors(36) → 기대 9, 실제 10 (i=6에서 2번 셈)
# count_divisors(49) → 기대 3, 실제 4한 줄 수정:
count += 1 if i == n // i else 2수업 중 질문: i == n // i 이 조건 i * i == n 이렇게 써도 되지 않나? 저렇게 쓴 이유가 있나해서
좋은 질문이다. 둘 다 정답이고 우리 맥락에선 결과가 같다. 다만 미묘한 차이가 있다.
| 표현 | 의미 | 안전성 |
|---|---|---|
i == n // i | "i와 짝꿍이 같은 값?" (약수 쌍 관점) | n % i == 0 조건 안에서만 안전 |
i * i == n | "i가 정확히 √n?" (제곱근 관점) | 항상 안전 — 정수 곱셈, 오차 없음 |
왜 차이가 생기나? 만약 if n % i == 0: 조건이 없는 곳에서 비교한다고 하면:
n = 10, i = 3
i * i == n → 9 == 10 → False ✅ (정확)
i == n // i → 3 == 10 // 3 → 3 == 3 → True ❌ (잘못된 판정!)정수 나눗셈 //은 나머지를 버려버리니까 i가 약수가 아닌데도 결과가 맞아떨어진 것처럼 보일 수 있다. 우리 코드는 if n % i == 0: 안에서 쓰니까 둘 다 안전하지만, 습관적으로는 i * i == n이 robust한 디폴트. 의도 표현 면에서는 짝꿍 변수와 같이 쓸 때 i == n // i가 가독성이 좋다 — 상황에 맞게 쓰면 된다.
3. 최대공약수 (GCD, Greatest Common Divisor) — 유클리드 호제법
두 수의 공통 약수 중 가장 큰 수. 외우면 끝나는 공식 1개:
gcd(a, b) = gcd(b, a % b)를 반복. b가 0이 되면 a가 답.
추적해보기
gcd(48, 18)
= gcd(18, 48 % 18) = gcd(18, 12)
= gcd(12, 18 % 12) = gcd(12, 6)
= gcd(6, 12 % 6) = gcd(6, 0)
↑ b=0 → a=6이 정답코드 (반복문 — 시험에 더 흔함)
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a🐍 Python 튜플 언패킹:
a, b = b, a % b는 오른쪽 전체를 먼저 계산한 다음 왼쪽에 동시 대입한다. Java라면 임시변수가 필요한 패턴인데 Python은 한 줄에 끝.// Java int temp = a; a = b; b = temp % b;# Python a, b = b, a % b
수업 중 질문: a, b 파라미터 조건 있어? 둘 중에 작은 수를 기준값으로 해야할 것 같은데 그런 설명이 없더라고
핵심 질문이다. a < b여도 자동으로 작동한다. 추적해보면 보인다:
gcd(5, 12) — 작은 수를 a에 넣어봤다.
| 반복 | a | b | a % b | 다음 (a, b) |
|---|---|---|---|---|
| 시작 | 5 | 12 | 5 % 12 = 5 | (12, 5) ← 자동 swap! |
| 1 | 12 | 5 | 2 | (5, 2) |
| 2 | 5 | 2 | 1 | (2, 1) |
| 3 | 2 | 1 | 0 | (1, 0) |
| 4 | 1 | 0 | 종료 | return 1 |
왜 자동 swap이 되냐면, a < b이면 a % b = a가 항상 성립한다(5를 12로 나눈 나머지는 5 그대로). 그래서 첫 줄 a, b = b, a % b가 → a, b = b, a로 변신. 한 번 헛돌고 큰 수가 자연스럽게 앞으로 온다.
→ 매개변수 조건 따로 없다. 어느 쪽이 크든 알아서 됨. 그래서 시험에서 빈칸/디버깅 문제에 if a < b: a, b = b, a 같은 줄이 있다면 그건 있어도 없어도 결과 같은 줄(함정 후보).
4. 최소공배수 (LCM, Least Common Multiple) — 황금 공식
두 수의 공통 배수 중 가장 작은 수. 공식 한 줄.
lcm = (a * b) // gcd(a, b)
# 또는 (오버플로우 안전 버전)
lcm = a // gcd(a, b) * b왜 성립? 직관적으로:
a × b는 공통 배수 중 하나(최소는 아닐 수 있음)- 거기서 공통으로 겹치는 부분(GCD)만큼 한 번 빼주면 최소가 됨
확인:
lcm(4, 6) = (4 * 6) // gcd(4, 6) = 24 // 2 = 12 ✅
lcm(12, 18) = (12 * 18) // gcd(12, 18) = 216 // 6 = 36 ✅⚠️
/vs//함정 재등장: 22차 이진 탐색에서도 나왔던 함정. 정수 결과 필요한 곳에선 무조건//.(4*6) / gcd(4,6)은12.0(실수)가 나와서 시험 답으로 오답 처리 가능.
5. N개 수의 LCM — 누적 패턴 함수 작성
세 수 이상의 LCM은 어떻게? lcm(a, b, c) = lcm(lcm(a, b), c) — 둘씩 누적해서 합쳐가면 된다.
수업 중 질문: 빈 리스트가 들어올 수도 있어?
엣지케이스 사고력 좋은 질문. 이번 문제는 len(numbers) >= 1 가정. COS Pro는 보통 입력 제약이 명시되고, 빈 리스트가 들어오는 경우는 드물다. 다만 실전 코딩테스트에서 입력 제약을 먼저 확인하는 습관은 함정 회피에 직접적으로 도움이 된다 — 계속 유지할 것.
직접 작성한 풀이
def lcm_all(numbers):
if len(numbers) == 1:
return numbers[0]
a = numbers[0]
lcm = numbers[0]
for i in range(1, len(numbers)):
b = numbers[i]
lcm = a // gcd(a, b) * b
a = lcm
return lcm테스트 5개 전부 통과. 1차 정답.
피드백: 코드 슬림화 체크리스트
잘 동작하지만 a와 lcm 두 변수가 항상 같은 값이다. 추적해보면:
i=1 직후: a = lcm = 12
i=2 직후: a = lcm = 24또 if len == 1 분기도 불필요하다 — 리스트가 1개면 for 루프가 한 번도 안 돌고 lcm = numbers[0] 그대로 반환된다.
슬림화된 형태:
def lcm_all(numbers):
lcm = numbers[0]
for n in numbers[1:]: # 첫 번째 빼고 값 순회
lcm = lcm // gcd(lcm, n) * n
return lcm💡 코드 슬림화 체크리스트 (앞으로 함수 작성 후 한 번씩 자기 점검)
1. 같은 값을 가진 변수 2개가 있나? → 하나로 합치기
2. 불필요한 엣지 분기가 있나? → 메인 로직이 자연스럽게 처리하면 제거
3. 인덱스가 꼭 필요한가? → 값 자체로 충분하면for x in arr
for n in numbers[1:]는 첫 번째 원소 빼고 값으로 순회하는 Python 패턴이다. 인덱스 안 쓰고 값 자체로 도는 게 더 깔끔. 누적 패턴에선 슬라이싱 + 값 순회가 더 흔하다.
오늘의 결과
오늘 푼 문제는 4문제(빈칸 2 + 디버깅 1 + 함수 작성 1), 1차 정답률 4/4 (100%). 함수 작성 자력 정답이 21차→22차→23차로 3세션 연속 이어지며 과거 약점이 강점으로 전환되는 추세. 다음 학습은 4/29(수)부터 BFS/DFS 시작.
