[알고리즘] 탐색(1) - 이진 탐색, 이진 탐색 트리 with Python
탐색 알고리즘? - 컴퓨터에 저장된 자료를 신속하고 정확하게 찾아주는 알고리즘 이진 탐색(binary search) 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘으로 탐색 시간 복잡도는 O(logN) 탐색 방법: 분할-정복 방법 사용 ex) 정렬된 배열 [12,15,23,48,62,98,111,130] 에서 23을 찾는다면?? 1. 가운데 값 선택 -> 48 2. 우리가 찾고자하는 23은 48 좌측에 위치함으로 탐색범위가 12~23으로 줄어듬, 줄어든 탐색범위에서 중간 값 선택 -> 15 3. 23은 15 우측에 위치, 값은 하나만 남게 되고 이 값은 23과 일치 소스코드(파이썬) def binary_search(a:list, search_key): left, right = 0, len(a) wh..
[자료구조] 리스트 (연결 리스트 부터 이중 연결 리스트까지)
오늘 알아볼 자료구조는 리스트입니다 :) 리스트란? 순서를 가지고 일렬로 나열한 원소들의 모임으로 데이터 목록을 다루는 자료구조로 기본 연산으로는 삽입, 삭제, 탐색이 있습니다. 리스트 구현 방법 1. 배열 이용 (순차적인 메모리 공간 할당) 2. 연결 리스트 이용 (노드에 분산 저장) 리스트의 연산 init(list) - 리스트 초기화 is_empty(list) - 리스트 공백 유무 검사 is_full(list) - 리스트 포화상태 유무 검사 insert(list, pos, item) - pos 위치에 item 추가 insert_last(list, item) - 리스트 맨 끝에 item 추가 delete(list, pos) - pos 위치의 요소 제거 get_entry(list, pos) - pos 위..
시간복잡도 O(NlogN)정렬 알고리즘 알아보기 with Python
이전에 시간 복잡도 O(N^2)인 정렬 알고리즘들에 대해 포스팅했었는데요. 오늘은 시간 복잡도가 O(NlogN)인 정렬 알고리즘에 대해 알아보려 합니다! 시간복잡도가 O(NlogN)인 대표적인 정렬에는 퀵 정렬, 합병 정렬, 힙 정렬이 있습니다. 1. 퀵 정렬 분할 정복(divide and conquer)기법을 사용한 정렬로, 평균적으로 아주 빠른 성능을 갖는 알고리즘입니다. 정렬 방법 1. 주어진 리스트에서 하나의 원소를 고른다. (피벗) 2. 피벗을 기준으로 두 개의 파티션으로 분할한다. 파티션 1: 피벗보다 작은 원소, 파티션 2: 피벗보다 큰 원소 3. 분할된 파티션에 대해서도 리스트의 크기가 0 혹은 1이 될 때까지 1,2 과정을 반복한다. 소스코드(파이썬) def quick_sort(a: li..