21-03-05 알고리즘 강의 노트정리

이진검색

정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
전화번호부 반으로 찢어 찾기 (from CS50)
True/False 결과로 최적해를 탐색하는 방법

탐색 배열의 가운데 인덱스를 구함
만약 가운데 값이 해당 값과 같다면 찾은 것
주어지는 배열은 정렬되어 있으므로 가운데 값이 해당 값보다 작다면 우측 반을 검색범위로 지정 (mid+1, high)
반대의 경우라면 (low, mid+1)로 검색범위를 지정
위 과정을 반복하여 값을 찾음 (단, low > high가 된다면 해당 값이 배열에 없는 경우)

while문을 사용한 이진검색

const binarySearch = (
    arr = arr.sort((a,b) => a - b), low = 0, high = arr.length, target
    ) => {
        while(low <= high) {
            // 가운데 인덱스 구하기
            let mid = Math.floor((low + high)/2);

            // 가운데 값이 해당값과 같다면 찾은 것
            if (arr[mid] === target) return mid;

            // 해당 값보다 작다면
            if (arr[mid] < target) low = mid + 1

            // 해당 값보다 크다면
            if (arr[mid] > target) high = mid - 1
        }
    // 반복하는 동안 low > high가 된다면 해당 값이 배열에 없으므로 -1을 리턴
    return -1
}

재귀를 사용한 이진검색

const binarySearchRecursive = (
    arr = arr.sort((a,b) => a - b), low = 0, high = arr.length, target
) => {
    // 찾지 못한 경우
    if (low > high) return -1

    // mid값 구하기
    let mid = Math.floor((low + high)/2);

    // 가운데 값이 해당 값이라면 return
    if (arr[mid] === target) return mid 
    
    // 해당 값 보다 작거나 크다면 함수를 재귀 호출
    if (arr[mid] < target) return binarySearchRecursive(arr, mid+1, high, target)
    return binarySearchRecursive(arr, low, mid-1, target)
}

True/False 결과로 최적해를 탐색하는 방법

구슬의 개수 N과 그룹의 수 M이 주어질 때 임의의 그룹 내 요소들의 최대값이 최소가 되게 하는 문제

const check = mid => {
    let group = 1, sum = 0;
    for (let i = 0; i < N; ++i) {
        // 첫번째 구슬부터 더하여 mid값보다 커지면 그룹화하고 새 그룹으로 넘어감
        if (sum + arr[i] > mid) {
            // mid가 10이라 가정하고 1, 2번째 값의 합이 8이 되고 
            // arr[2]값이 4라면 sum + arr[2] = 12가 되어 8보다 커지므로
            // sum값을 arr[2]값으로 초기화하고 그룹 수를 늘린다
            sum = arr[i];
            group++;
        } else {
            // 만약 합이 최대값을 넘기지 않는다면 더해주어도 괜찮음
            sum += arr[i]
        }
    }
    return group <= M
}

let low = 0, high = 0;
let N = 8, M = 3
let arr = [5, 4, 2, 6, 9, 3, 8, 7]
const input = () => {
    console.log(`${N}개의 구슬을 ${M}개의 그룹으로 나누어야 합니다`)
    for (let i = 0; i < N; ++i){
        // console.log(arr[i])
        // 각 구슬 중에 최소값을 구함
        if (low < arr[i]) low = arr[i];
        // 구슬의 총합을 최대값으로 구함
        high += arr[i]; 
    }
}

const output = () => {
    console.log(answer);
    let count = 0, sum = 0, limit = M; // limit: 그룹 수 제한
    for (let i = 0; i <= N; ++i) {
        // 구한 해답이 arr[i]번째까지의 합보다 크거나 
        // 한 그룹당 하나 이상의 구슬이 있어야 하므로 N - M < i 보다 작아야 한다
        if (sum + arr[i] > answer || N - i < limit) {
            console.log(`그룹${i+1}:${count}`) // 그룹 수를 출력
            count = sum = 0; // 초기화
            limit--; // 남은 그룹 수 줄이기 
        } 
        sum += arr[i];
        count++;
    }
}

const process = () => {
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (check(mid)) {
            answer = mid;
            high = mid - 1;
        } 
        // group <= M 가 false를 리턴 할 때 (그룹 수가 M을 넘어갈 때)
        else low = mid + 1
    }
}

const solution = () => {
    input();
    process();
    output();
}

solution();

배우면서 이해가기 어려웠던 점
- mid값은 index값이 아닌가? 왜 mid를 최대값으로 설정하여 check를 할까?
  → mid값은 최소값 + 최대값의 중간값
  → check 함수는 group <= M의 boolean 값을 리턴하므로 이 함수가 True값을 리턴할 때만 구슬의 합을 계산하면 된다

책 복사하기

주어진 대본들의 페이지(m[])를 k명의 서기공이 한 파트 이상 복사할 때 가장 많은 페이지를 맡은 서기공의 페이지를 구하는 문제
답이 두 개 이상 있다면 첫 번째 서기공이 할 일이 가장 작아야 하며 두 번째 서기공이 할 일이 작아야 한다

입력값이 100,000으로 커서 순차 탐색보다 이진 탐색을 사용해야 한다

let arr = [100, 200, 300, 400, 500, 600, 700, 800, 900];
let M = arr.length, K = 3;
let low = 0, high = 0;

const input = () => {
    console.log(`${M}개로 나누어진 대본을 ${K}명의 서기공이 나누어 일을 해야 합니다`); 
    for (let i = 0; i < M; ++i) {
        // 숫자 구슬과 유사함
        if (low < arr[i]) low = arr[i];
        high += arr[i]; 
    }
}

const check = mid => {
    let group = 1, sum = 0;
    for (let i = 0; i < M; ++i) {
        if (sum + arr[i] > mid) {
            sum = arr[i];
            group++;
        } else sum += arr[i];
    }
    return group <= K
}

const process = () => {
    while (low <= high) {
        let mid = Math.floor((low + high)/2);
        if (check(mid)) {
            answer = mid;
            high = mid - 1
        } else low = mid + 1
    }
}

const output = (index, sum, people) => {
    if (index < 0) return;
    if (sum + arr[index] > low || index < people) {
        output(index - 1, arr[index], people - 1);
        console.log(`${arr[index]} / `)
    } else {
        output(index -1, sum + arr[index], people);
        console.log(`${arr[index]} `)
    }
}

const solution = () => {
    input();
    process();
    output(M - 1, 0, K - 1);
    // 배열의 마지막 번째(M-1)값부터 탐색해 들어가면 재귀를 통해 첫번째 index부터 실행된다
    // 사람이 K명일때는 "/"가 K-1개 들어가야 하므로 K-1번만 수행한다
}

solution();

숫자 구슬 문제를 이해하고 나면 생각보다 이해하기 쉬웠음
재귀적으로 호출될 때 마지막부터 탐색한다면 LIFO 콜스택에 의해 가장 먼저 출력되는 것은 0번째 index일 것이다 (탈출구문은 0보다 작을 때로 작성)

21-03-05 알고리즘 강의 노트정리

이진검색

True/False 결과로 최적해를 탐색하는 방법

책 복사하기

Harry Kim