[파이썬 알고리즘] 제곱근 구하기: 완전 열거 vs 이분 검색

 안녕하세요! 오늘은 파이썬을 활용해 양수의 **제곱근(Square Root)**을 구하는 두 가지 알고리즘을 비교해 보겠습니다. 특히 무한소수로 떨어지는 근사값을 컴퓨터가 어떻게 효율적으로 찾아내는지 그 원리를 파헤쳐 봅니다.

---

1. 완전 열거 알고리즘 (Brute Force)

가장 단순한 방법은 0부터 시작해 아주 작은 수(Step)만큼 계속 더해가며 정답에 가까운지 확인하는 것입니다.

• 근사값의 정의: 제곱한 값과 목표값 x의 차이가 아주 작은 상수 입실론(ε) 범위 안에 있다면, 그 값을 근사값(제곱근)으로 인정합니다.

• 작동 원리: ans를 0부터 시작해 step만큼씩 늘려가며 ans**2가 x와 충분히 가까워질 때까지 반복합니다.

⚠️ 완전 열거의 한계점

1. 성능 문제: 25의 제곱근을 찾을 때 약 5만 번의 이동이 필요할 만큼 연산량이 많습니다.

2. 소수점 문제: 만약 찾으려는 수 x가 1보다 작으면(예: 0.25), 제곱근이 x보다 커지기 때문에 탐색 범위를 잘못 설정하면 영원히 답을 찾지 못하는 오류가 발생할 수 있습니다.

3. 효율성 저하: 정확도를 높이려 step을 더 줄이면 실행 시간이 너무 오래 걸립니다.

---

2. 더 스마트한 방법: 이분 검색 (Bisection Search)

완전 열거의 비효율을 해결하기 위해 등장한 것이 바로 이분 검색입니다. 탐색 범위를 절반씩 뚝뚝 잘라가며 정답을 찾아냅니다.

• 작동 원리

  1. 탐색 범위의 중간값(mid)을 정답이라고 가정합니다.

  2. 중간값을 제곱해 봅니다(mid**2).

  3. 제곱값이 정답보다 크다면? 정답은 왼쪽 절반 안에 있습니다. (범위를 왼쪽으로 축소)

  4. 제곱값이 정답보다 작다면? 정답은 오른쪽 절반 안에 있습니다. (범위를 오른쪽으로 축소)

  5. 오차 범위 안으로 들어올 때까지 이 과정을 반복합니다.

• 이분 검색 vs 이진 검색: * 이분 검색: 연속적인 실수값(연속 데이터) 사이에서 근사값을 찾을 때 주로 사용합니다.

  • 이진 검색(Binary Search): 리스트나 튜플처럼 이미 정렬된 이산 데이터(Discrete Data) 세트에서 값을 찾을 때 사용합니다.

---

3. 왜 이분 검색을 써야 할까요?

완전 열거 방식이 한 걸음씩 정직하게 걷는다면, 이분 검색은 거리를 절반씩 순간이동하며 좁혀가는 것과 같습니다. 데이터가 커질수록 이분 검색의 속도는 압도적으로 빨라집니다.

---

💡 학습 요약 가이드

1. 완전 열거: 구현은 쉽지만 성능이 낮고 범위 설정에 주의가 필요함.

2. 이분 검색: 범위를 절반씩 줄여나가는 알고리즘으로 매우 효율적임.

3. 근사값: 컴퓨터는 무한소수를 다룰 때 입실론이라는 오차 범위를 설정해 계산함.