수치해석

수치해석(Numeric Analysis)은 직접 풀기 힘든 수학문제를 근사적으로 푸는 알고리즘입니다.

프로그래밍 대회에서 자주 나오는 기법은 이분법으로

그래프 상에서 x축 윗부분에 위치한 점 하나와 아랫부분에 위치한 점 하나를 찾은 뒤

이 범위에서 0이되는 지점을 수치적으로 빠르게 찾아내는 기법입니다.

또한 삼분 검색이라는 기법은 최대점, 최소점이 있는 그래프에서 이러한 점을 찾아내는 기법입니다.

주어진 문제를 다음과 같은 기법으로 풀 수 있는 문제로 변형하여 답을 찾아내야하는 경우가 많습니다.

이분법의 경우 범위가 N일 때 O(lgN)번만에 0이 되는 지점을 찾을 수 있기에

수의 범위가 큰 문제에 대하여 이 기법을 생각해 볼 수 있습니다.

기본 문제

2805번: 나무 자르기

1300번: K번째 수

15732번: 도토리 숨기기

8986번: 전봇대