[TIL] 99클럽 코테 스터디 1일차 TIL + 이분 탐색

 

문제 풀이 (백준 1072 게임)

 

문제 탐색하기

위 문제를 풀기 위해서는 고려해야할 점이 3가지가 존재합니다.

첫번째 부동소수점 오차를 고려해야합니다.

두번째 X가 최대 1000,000,000까지 주어질 수 있으므로 시간 복잡도를 고려하여 이분탐색 알고리즘을 활용해야합니다.

세번째 승률이 절대 변하지 않는 경우를 생각합니다.

 

* 부동소수점 오차

부동소수점 오차는 컴퓨터가 실수를 정확히 표현하지 못해 발생하는 작은 오차입니다. 컴퓨터는 실수를 이진수로 표현하는데, 10진수의 일부 소수점 숫자는 2진수로 완전히 변환되지 않는 경우가 많기에 근사값으로 저장하는 경우가 있습니다. 

따라서 이 경우 예상한 결과가 나오지 않을 수 있기때문에 최대한 정수범위 내에서 연산을 하거나 BigDecimal을 사용해야합니다.

// 승률을 구하는 로직

// 1. 기존 구현 방법
Z = (long)((double)Y/X)*100;

// 2. 부동소수점 오차 고려 방법
Z = Y*100/X;

 

* 이분탐색 알고리즘 활용

최소 몇번의 게임을 해야 승률이 변하는지 구해야하기에 게임을 추가로 하는 횟수는 1이상 X이하일 것입니다. (현재 게임횟수의 2배를 하게되면 승률의 변동이 무조건 있을 것이기 때문)

추가게임횟수를 선형탐색을 통해 풀게되면 시간초과가 발생하기 때문에 이분탐색을 통해서 구할 수 있습니다.

이분탐색(이진탐색 - Binary Search)란?

: 정렬된 배열에서 특정 값을 찾는 알고리즘
이분탐색은 탐색 범위를 절반씩 줄여나가기 때문에 순차탐색에 비해 빠른 속도를 보장합니다. 하지만 배열이 정렬되어 있어야하는 조건이 필요하기에 정렬작업이 필요한 경우도 있습니다.

• 순차탐색 : 최악의 경우 배열 끝까지 탐색 O(N)
• 이분탐색 : 범위가 정해질 때 마다 탐색 범위가 반으로 줄어듬 O(logN)

* 이분탐색 알고리즘으로 설계하기

1. 게임을 추가로 하는 횟수의 범위를 설정합니다. 1 <= (추가횟수) <= X 즉, (left와 right를 세팅해주는 과정)
2. 범위의 중간을 변수로 선언합니다. (mid)
3. X+mid, Y+mid를 통해서 승률을 구해줍니다. 
4. 승률이 기존의 승률보다 높으면 right = mid - 1 로 세팅하고 기존의 승률보다 낮거나 같으면 left = mid + 1로 세팅합니다. 
5. left가 right보다 커질때까지 반복합니다. left가 right보다 커질때의 left값이 최소 게임 추가 횟수 입니다.

* 승률이 절대 변하지 않는 경우

X와 Y가 같아서 승률이 100이거나

기존 승률이 99인 경우에는 더이상 승률이 오를 수 없기에 절대 변하지 않는 경우에 속합니다. 

따라서 위 2경우를 제외하고 이분탐색을 진행하면 됩니다.

 

문제 풀이

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        long X = sc.nextLong();
        long Y = sc.nextLong();

        long Z = getRatio(X, Y);

        if(Z >= 99){
            System.out.println(-1);
        }else{
            // 이분 탐색
            long start = 1;
            long end = X;
            long mid, ratio = 0;

            while(start <= end){
                mid = (end + start)/2;
                ratio = getRatio(X+mid, Y+mid);
                if(ratio > Z){
                    end = mid-1;
                }else{
                    start = mid+1;
                }
            }

            System.out.println(start);
        }
    }

    private static long getRatio(long X, long Y){
        return Y*100/X;
    }
}

 

 

오늘의 회고

부동소수점 오차, 이분탐색의 개념에 대해 얻어갈 수 있는 좋은 시간이었습니다.

승률을 구하는 부분에서 부동소수점 오차를 고려하지 않고 로직을 작성해서 계속 답이 틀렸었는데 소숫점에 대해서 근사값으로 저장하기에 발생하는 오차때문이라는 것에 대해 새롭게 알게되었습니다.

또한 이분탐색 역시 개념으로는 알고있었지만 이렇게 문제를 풀어가며 적용해보는 과정을 통해서 좀 더 이해할 수 있었습니다.