C++ Week 6

팀프로젝트 7일차.

Study

팀프로젝트

---

Today I Learned

---

이진탐색

Overview

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <iostream>

long long solution(long long n) {
    long long answer = 0;
    long long low = 1;
    long long high = n;
    long long mid = 0;
    
    
    while (low <= high)
    {
        mid = (low + high) / 2;
        
        if (mid == 0) { low = 1; continue; }
        
        if (mid == n / mid && n % mid == 0)
        {
            return (mid + 1) * (mid + 1);
        }
        else if (mid < n / mid)
        {
            low = mid + 1;
        }
        else if (mid < n / mid)
        {
            high = mid - 1;
        }
    }
    return -1;
}

이진탐색(Binary Serach)는 단순히 값을 찾는 것이 아니라 '정답이 될 수 없는 절반의 범위를 매번가차 없이 버리는 것' 이다.

전제 조건 = 탐색 범위가 반드시 정렬되어 있어야 한다.

작동 원리
1. 탐색 범위의 중간값(mid)을 정한다.
2. mid가 정답보다 큰지 작은지 판단한다.
3. 정답이 아닌 쪽의 범위를 통쨰로 날리고, 남은 절반에서 다시 시작한다.

기대 효과 = 50,000,000,000,000(50조)일 때, 단 46번의 비교만으로 정답을 찾아낼 수 있다. O(logn)

이 알고리즘 문제는 사실 알고리즘 하나로만 풀 수도 있지만 이진탐색이 궁금했다.

Trouble Shooting

1. Overflow

   • Problem : long long을 썻지만, 중간값 mid를 제곱하는 과정 if(mid * mid) 에서 long long의 최대범위를 초과할 수 있다는 걸 확인

   • Solution : mid * mid < n 대신 `mid < n / mid을 사용하여 곱셉 없이 크기 비교, 수학적으로는 같지만, 컴퓨터 연산에서 안전성 면에서는 다름

2. int자료형 정수 나눗셈

   • Problem : if에서 mid == n / mid인지만 확인하면 n=10, mid=3일떄 3 == 10 / 3이 참이 되는 오류 발생 ( 정수 나눗셈은 소수점을 버리기 때문 )

   • Solution : 반드시 나머지연산(n % mid == 0)을 &&하여 정확히 나누어떨어지는 "완전제곱수" 인지 검증 해야한다.

3. high

   • Problem : high의 값이 항상 n의값의 -1 이 되는데 어떻게 반으로 갈라서 검색한다는거지? 라고생각했음

   • Solutiono : high의 값은 담고 변하지않는 변수가 아니라, min > n / min 일때 min - 1한 값을 high에 넣는다는걸 생각해야함.