[TIL] 이분탐색 알고리즘, 테스트코드, DNS

이분탐색 알고리즘 문제

가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [n, test] = input
const array = test.split(' ').map((x) => +x)

const sequence = []

for (let i = 0; i < +n; i++) {
    let low = 0
    let high = sequence.length
    let mid

    while (low < high) {
        mid = Math.floor((low + high) / 2)
        
        if (sequence[mid] >= array[i]) {
            high = mid
        } else {
            low = mid + 1
        }
    }

    sequence[low] = array[i]
}

console.log(sequence.length)

나무 자르기

https://www.acmicpc.net/problem/2805

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [num, test] = input
const [n, m] = num.split(' ').map((x) => +x)
const trees = test.split(' ').map((x) => +x)

let low = 0
let high = 1000000000
let mid

while (low + 1 !== high) {
	mid = Math.floor((low + high) / 2)

	const sum = trees.reduce((total, height) => {
		if (height > mid) {
			total += height - mid
		}
        return total
	}, 0)

	if (sum >= m) {
		low = mid
	} else {
		high = mid
	}
}

console.log(low)

테스트 코드 작성

DNS 관련 공부