[Algorithm]이진탐색(Binary Search)

Wintering·2022년 5월 20일
0

Algorithm

목록 보기
2/16

🔻 백준 1654 랜선자르기

'랜선자르기'라는 문제를 풀었다. 예제를 입력하고 출력이 제대로 되는 걸 확인했는데도 제출을 하면 틀렸습니다가 계속 떴다. 예제를 예로 들면 802, 743, 457, 539를 문제의 조건에 맞춰 같은 크기로 나눌 수 있는 최대 크기를 구해야하는데, 일단 조건은 차치하고 '숫자들 중 최소값인 457보다 무조건 작다'라는 것에 초점을 맞추고, 정수형이니까 457에서부터 -1씩 줄여나가면서 조건에 맞는 최댓값을 구하는 알고리즘을 짰었다.

❓왜 틀렸을까


예제문제에 대해서는 원하는 최대값이 잘 구해졌다. 하지만 틀릴 수 밖에 없는 문제점이 있었는데

  • 문제의 조건에 주어진 랜선의 길이는 231-1보다 작거나 같은 수 이다. 231이라는 수 자체가 이미 Int형의 범위 (-231 ~ (231 - 1))의 끝자락에 걸쳐있는데, countSum이라는 변수에서 덧셈을 하게 될 때, 저 근사값이 들어갔을 경우 아주 가뿐하게 int의 범위를 벗어나기 때문에 오류가 발생한다.

  • 이 오류가 아니더라도, countSum 변수를 돌리면서 N번, 가진 랜선의 수만큼 돌아가기 위한 K번 총 N*K번의 반복문이 돌아가게 되는데, 만약 N과 K가 끝범위인 1,000,000 과 10,000이었다면 곱해서 10,000,000,000번을 돌아가하므로 시간이 과하게 걸린다. (아마 시간초과가 떴을 것!)


이런 문제점을 해결하기 위해서 나온 방식이 '이진 탐색(BinarySearch)' 인 것 같다.

이진 탐색이란?

이진 탐색이란 데이터가 정렬되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당값을 찾을때까지 이 과정을 반복한다.

백준 코드 수정

0개의 댓글