메뉴 닫기

[EDX]Introduction to Computer Science and Programming Using Python-Week5(2)

week5 – lecture 10

Search 알고리즘에 관한 강의이다

먼저 Simple한 방법이 소개되는데 search를 위해서 주어진 L(L은 list라고 가정한다)의 길이만큼 for문을 돌면서 일치하는 것이 존재하는지 찾는 방법이다. 심플 검색의 복잡도는 O(len(L)) 이된다.  선형 의 복잡도는 엄청 나쁘지는 않지만 더 나은 방법을 고려해본다.

“I need to know, can I do better?”

*이하 len(L)은 N으로 표현한다

이분검색(Binary Search)를 이용한다면 검색 알고리즘은 O(log(N))로 향상 될 수 있다.  하지만 Binary Search의 경우는 정렬(sorting)이 되어야 가능하다는 문제가 잇다. 그렇다면? sorting 을 위한 cost는 어떤가? 그래서 sorting 알고리즘을 알아본다.

sorting 알고리즘에는 다양한 방법이 있지만(아마 정보처리기사 공부하면서 봤던 기억이….) 이번 강의에서는 선택정렬(selection sort)와 합병정렬(merge sort)가 등장한다.

먼전 선택정렬이다. 이제 Big O 표기법을 배운이상 존재하는 알고리즘에 대해서는 복잡도를 계산해서 Big O 표기법으로 표시한다. 그래서 어떤 알고리즘이 효율적인지 비교하는데 선택정렬은 복잡도가 O(N^2) 이다. 이런…

그럼 sorting 하고 검색하면 O(N^2) + O(log(N)) … 그냥 심플한 방법으로 O(N)이 낫다.

그럼 여기서 끝인가?

개발 경력 2년밖에 안되지만 좋은 개발자가 되기 위해서는 항상 물어봐야한다고 생각한다.

“I need to know, can I do better?”

합병정렬(merge sort)의 복잡도는 얼마인가? 합병정렬은 L을 쪼개서 각각 sorting한다음에 합치는 방법인데 결론만 이야기하면 O(N*log(N))이다.

그렇다면???

합병정렬로 sorting 하고 검색하면?   O(n*log(n)) + O(k*log(n))  – k는 검색 횟수

그렇다. 심플 검색 O(N)보다 합병정렬이후 이분검색이 더 효율적인 알고리즘이다.

특히 검색을 여러번 실행해야 할 경우 sorting 을 위한 cost는 amortize cost(상환비용)이다. 

그럼 위의 방법보다 더 나은 방법은 없는가?

Hash 가 나온다.

Hash 란 key 를 가지는 데이터 구조인데 key를 int로 변환해서 index로 사용한다. 따라서 Hash 로 저장된 데이터의 경우 검색 복잡도는 O(1)이다.

이런

앞선 방법 보다 비교할 수 없을 만큼 효율적이다.

어떤 검색 알고리즘을 사용해야할 지는 알아서 판단하자.

“I need to know, can I do better?”

 

진행중인 프로젝트에서 DB에서 where 절로 검색 쿼리를 완성하는 것이 아닌 데이터를 전부 불러온 뒤 javascript 에서 indexOf로 검색하는 코드를 만들어두었다.

이 강의를 바탕으로 비효율적인 알고리즘을 개선해야겠다.