목록2023/03/08 (1)

코딩관계론

[프로그래머스] 수 찾기

아이디어 도출 방법 주어진 문제는 search배열(n)에서 특정 숫자(m)를 찾는 문제였다. 하지만 배열의 길이가 크고, 찾고자 하는 특정 숫자가 많아지면 이중반복문으로는 해결하기 어렵다. 따라서 이중 반복문을 제거하고, 주어진 배열에서 더 빠르게 탐색할 수 있는 알고리즘이 필요한데 이것이 이분 탐색이다. 이분 탐색은 기존의 O(n)의 시간 복잡도를 O(logn)으로 줄여준다. 이런 방법을 사용한다면 기존의 O(n*n)의 시간 복잡도에서 O(nlogn) + O(mlogn)으로 개선할 수 있다. 또한 이분 탐색을 하기 전 필수적으로 수행되어야 할 것은 '특정 배열'(주어진 숫자를 찾고자 하는 배열)이 정렬되어 있어야 한다. 최종 결과 n = int(input()) search = list(map(int, ..
개발/알고리즘 2023. 3. 8. 23:30
이전 Prev 1 Next 다음