MONG 기술블로그

이진 탐색 ( Binary Search )이란 정렬된 배열에서 타겟을 빠르게 찾는 검색 알고리즘이다. 제약 조건 : 정렬된 상태의 배열에서 사용가능 장점 : 시간복잡도가 O(logN) 으로 매우 빠른 성능 보유 시간복잡도를 수치로 변경하여 설명해보면 다음과 같다. 크기 1억개인 배열에서 특정 값을 찾는 경우. ( 정렬된 경우 ) 순차 탐색 : 최악의 경우 1억번 탐색 필요 이진 탐색 : log100000000 번 탐색 필요. 대략 26번만의 탐색으로 특정 값을 찾을 수 있음 이를 Python 코드로 직접 구현하여 탐색 횟수를 비교해보자. import random # 1 - 천만 nums = [i for i in range(1, 10000001)] # 유니크한 백만개의 수를 1-천만 범위에서 리스트로 추출..

인프라 엔지니어로써 실무적으로 프로그래밍을 사용하는 빈도가 매우 적지만 IT 업무에 종사하는 사람으로써 언제든지 꺼내들 수 있는 프로그래밍 언어 하나쯤은 가지고 있어야 한다고 생각한다. 또한 단순히 프로그래밍 언어를 작성한다기보다 내가 원하는 로직을 구현할 줄 알아야 한다고 생각하기에 알고리즘 공부도 꾸준히 해야한다 우선 정복할 대상은 프로그래머스 고득점 Kit 이다. 간단하게 구현한 내용을 정리하여 나중에 필요한 로직이 있을 때 꺼내 쓸 수 있도록 블로깅해놓자. 사용언어 : Python3 첫 도전과제 : 프로그래머스 코딩테스트 고득점 Kit 코딩테스트 고득점 Kit 문제 풀이 현황 - 해시 ( 4/4 ) - 스택/큐 ( 4/4 ) - 힙(Heap) ( 3/3 ) - 정렬 ( 3/3 ) - 완전탐색 ( ..