binary search 썸네일형 리스트형 Arrays.binarySearch() 사용 지금까지 매번 구현해서 사용했는데 Arrays API에 이분탐색 함수가 있었다. 좀 찾아볼걸. 하지만 일반적으로 자주 구현하던 방식이랑 차이가 있어서 주의해야하는 부분이 있다. 일단 나는 이분 탐색은 무조건 양수를 반환하게 구현한데 반해서 Arrays 라이브러리에 포함된 binarySearch() 함수는 음수값을 반환하는 경우가 있다. 이게 우리가 원하는 타겟이 딱 맞게 존재하는 경우에는 양수가 반환되는데 정확히 같은 값이 아니면 배열에서 자기 위치를 찾아 음수로 반환한다는 특징이 있다. 예를 들어 2, 4, 7, 9 이라는 숫자 배열이 있다고 하자. 배열이 0부터 시작하는 경우, 정상적으로 이분 탐색이 이뤄진다면 2를 찾을 때 0을 반환하고, 9를 찾는다면 3을 반환할 것이다. 이것은 일반적인 탐색 결.. 1654번: 랜선 자르기 - Baekjoon Online Judge 1654번: 랜선 자르기 - Baekjoon Online Judgehttps://www.acmicpc.net/problem/1654 랜선 자르기 문제는 이분 탐색을 이용하여 범위 내에서 원하는 개수의 랜선을 만들되 그 길이는 최대값이 되도록 하는 문제이다. 원하는 값을 찾기에는 너무 많은 값을 하나씩 대입해야 하기 때문에 이분 탐색을 이용하여 가능한 후보군을 줄임으로써 시간내에 원하는 값을 찾을 수 있다. 이분 탐색 문제를 푼다고 했을 때 구현에서 차이가 나는 부분은 어떤 기준으로 중앙값을 옮겨줄 것인가이다. 이 문제의 경우 주어진 랜선을 적절하게 잘라서 원하는 개수를 맞춰주는 것이기 때문에 랜선의 길이가 중앙값 이동의 기준이 된다. 처음 중앙값은 0에서 int의 max값 사이에 있다는 것을 가정하고 그.. 13. 이분 탐색 (Binary Search) 이진 탐색이라고도 부르는 이분 탐색은 간단하면서도 강력한 알고리즘입니다. 기본적인 알고리즘의 아이디어는 이미 정렬이 되어 있는 자료구조에서 특정 값을 찾을 때에 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것입니다. 절반씩 나눠가면서 탐색하는 것에서 이분 탐색이라는 이름이 나왔다는 것을 알 수 있습니다. 이진 탐색 - 나무위키https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89 예를 들어 설명해보도록 하겠습니다.아래와 같이 배열이 하나 주어졌다고 해봅시다. 0 1 2 3 4 5 6 7 8 9 2 5 6 10 12 13 15 17 19 23 여기서 우리가 알고 있는 것은 이 배열이 작은 수부터 큰 수까지 오름차순으로 정렬이 되어 있다는 것 뿐이고,.. 이전 1 다음