C# List BinarySearch 함수

C#에서 List의 이진 탐색을 자체적으로 제공하고 있습니다!!

백준 8980번 문제에서 이를 써먹었고 정리해 보려 합니다.

 

https://programming-mr.tistory.com/102

백준# 8980 택배

써먹은 문제는 제 블로그에 있습니다.

 

 

1. 바이너리 서치(이진 탐색) 이란 무엇인가.

 

우선 써먹으려면 리스트가 정렬되어 있어야 합니다.

정렬이 안돼 있어도 이 함수는 어찌어찌 찾긴 하는데

근본은 무조건 정렬되어 있어야 합니다.

 

ex) 3 7 8 10 14 19

이렇게 있을 때 제가 14를 찾고 싶습니다. 그럼 인덱스의 0번부터 만날 때 까지 찾으면

운이 없는 경우에 리스트의 모든 요소를 한번 씩 검사해 봐야 합니다.

3의 경우 한 번에 찾겠지만 결과적으로 시간복잡도는 같은 O(n)으로 칩니다.

 

이진 탐색은 리스트의 가운데를 찍어봅니다!

리스트의 경우는 인덱스가 list.Count / 2가 되겠습니다.

그럼 10을 확인하고 14는 이것보다 큽니다.

다음 10보다 작거나 같은 모든 요소는 더이상 검사하지 않습니다.

 

다음 14와 19의 중간을 확인합니다.

14를 확인하고 14가 있음을 확인합니다.

 

정렬이 되어있어야 하는 이유가 이겁니다.

가운데를 찍어보고 찾는 것이 가운데 값보다 크냐 작냐에 따라

다음 탐색을 진행하기 때문입니다.

 

 

대표적인 예시로 EggDrop 문제가 있습니다.

아주 단단한 계란을 개발? 했고 이게 건물 몇층에서 떨어트렸을 때까지

깨지지 않고 버텨주나 확인해 보는 것 입니다.

 

10층짜리 건물에서 시험한다면 1층부터 10층까지 차례대로 올라가며

계란을 떨어트려 볼 수도 있겠으나 효율적이진 않습니다!

 

1. 처음 5층에서 떨어트려 봅니다.

 

2 - 1. 깨졌다면 높이가 낮은 곳으로 가야합니다. 1 ~ 4의 중간인 2층에서 진행합니다.

2 - 2. 계란이 버텨줬다면 높은 곳으로 갑니다. 6 ~ 10층의 중간인 8층에서 진행합니다.

 

이것을 반복하면 어디서 버텨주는지 최소한의 계란으로 테스트 가능합니다.

 

 

 

2. list.BinarySearch함수 사용.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            //0 부터 9 까지 리스트에 추가.
            List<int> intList = new List<int>();
            for (int i = 0; i < 10; i++)
                intList.Add(i * 2);
 
            //인덱스 찍어보기.
 
            //중간의 어떤 값.
            var middleIndex = intList.BinarySearch(4);
            Console.WriteLine("중간의 어떤 값 : " + middleIndex);
            //결과 : 2
 
            //가장 처음의 값.
            var firstIndex = intList.BinarySearch(0);
            Console.WriteLine("가장 처음의 값 : " + firstIndex);
            //결과 : 0
 
            //중간이지만 리스트에 없는 값.
            var missedIndex = intList.BinarySearch(5);
            Console.WriteLine("중간이지만 리스트에 없는 값 : " + missedIndex);
            //결과 : -4
 
            //가장 마지막의 값
            var lastIndex = intList.BinarySearch(18);
            Console.WriteLine("가장 마지막의 값 : " + lastIndex);
            //결과 : 9
 
            //처음보다 더 작은 값.
            var minIndex = intList.BinarySearch(-2);
            Console.WriteLine("처음보다 더 작은 값 : " + minIndex);
            //결과 : -1
 
            //마지막 값보다 더 큰 값.
            var maxIndex = intList.BinarySearch(13);
            Console.WriteLine("마지막 값보다 더 큰 값 : " + maxIndex);
            //결과 : -8
 
 
        }
    }
}

int 리스트 하나로 테스트 했습니다.

0 부터 18까지 2의 배수로 넣었습니다.

 

결과를 보면 공통점이 있는데 리스트에 있는 값은 양수로, 리스트에 없는 값은 음수로 표현됩니다.

만약 정렬을 어떤 기준으로 유지하면서 값을 넣고 싶다면 양수와 음수를 구분하기 귀찮겠죠?

~오퍼레이터 사용하면 되겠습니다.

 

list.Insert(~index, 값);

사용하면 됩니다. 그럼 정렬을 유지하며 해당 값이 들어갑니다.

1의 보수로 바꿔주는 연산자인데.... 설명은 생략합니다.

 

또는 Math.Abs(index); 사용하면 되겠습니다.

절댓값 뽑아주는 함수 입니다.

 

 

2. list.BinarySearch의 응용.

 

이진 탐색을 사용하려면 정렬이 되어있어야 한다고 설명 했습니다.

그 정렬의 기준이 제가 설정한 기준이고 그 기준으로 이진 탐색을 하고 싶을 수

있을 겁니다. 그 경우 어떻게 해야 하는지 설명하겠습니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace BinarySearch
{
    public class Student : IComparer<Student>
    {
        public int grade;
        public int mathScore;
        public int engScore;
 
        public Student(int grade, int mathScore, int engScore)
        {
            this.grade = grade;
            this.mathScore = mathScore;
            this.engScore = engScore;
        }
 
        public int Compare(Student st1, Student st2)
        {
            // 학년에 대해 정렬 후 수학 점수에 대해 정렬.
            return (st1.grade == st2.grade) ?
                st1.mathScore.CompareTo(st2.mathScore) : st1.grade.CompareTo(st2.grade);
        }
 
        public void PrintStudent()
        {
            Console.WriteLine("grade : " + this.grade + " mathScore : "
                + this.mathScore + " engScore : " + this.engScore);
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            //리스트 정의.
            var studentList = new List<Student>();
            studentList.Add(new Student(1, 4, 6));
            studentList.Add(new Student(2, 5, 3));
            studentList.Add(new Student(2, 6, 2));
            studentList.Add(new Student(3, 5, 4));
            studentList.Add(new Student(1, 6, 1));
            studentList.Add(new Student(2, 7, 5));
            studentList.Add(new Student(3, 1, 3));
 
            //위의 Compare을 기준으로 정렬.
            studentList.Sort(studentList.First());
 
            //학생 전체 출력.
            Console.WriteLine("학생 추가 전 출력.");
            studentList.ForEach(x => x.PrintStudent());
 
            //학생 추가.
            var student = new Student(2, 2, 2);
 
            //바이너리 서치의 첫 매개변수는 찾고자 하는 학생
            //두번째 매개변수는 Compare함수가 구현된 객체.
            var index = studentList.BinarySearch(student, student);
            studentList.Insert(~index, student);
 
 
            //전체 학생 다시 출력.
            Console.WriteLine("학생 추가 후 다시 출력.");
            studentList.ForEach(x => x.PrintStudent());
        }
    }
}
 

제 블로그에서 정렬 방법에 대해 설명 드린적 있습니다.

1. OrderBy()사용

2. IComparable 상속 후 int CompareTo(Object other)구현.

3. IComparer<T> 상속 후 int Compare(T t1, T t2) 구현.

 

이 중 3번 IComparer을 구현해야 합니다.

 

BinarySearch(넣을 아이템, IComparer가 구현된 객체)

이렇게 넣어주면 아까 intList와 같은 결과를 보여줍니다.

 

정보가 2 2 2 인 학생을 BinarySearch로 찾고 Insert 함수로 집어넣었습니다.

그 결과를 다시 출력한 모습입니다.

 

 

이진 탐색 함수를 써먹는 방법을 설명하는 글이지만

이진 탐색은 직접 구현 해보시길 추천합니다. 꼭!!