하드러너 블레이크 (Hard-Learner Blake)

제로베이스 데이터 취업 스쿨 과정 학습 내용을 정리한 포스팅입니다.

📍 이진탐색

정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

nums.sort()

searchData = 17

result_idx = -1

start_idx = 0
end_idx = len(nums) - 1
mid_idx = (start_idx + end_idx) // 2
mid_value = nums[mid_idx]

while True:
	if searchData == nums[len(nums) -1]:
        result_idx = len(nums) - 1
        break
    
    if searchData > mid_value:
        start_idx = mid_idx
        mid_idx = (start_idx + end_idx) // 2
        mid_value = nums[mid_idx]
        
    elif searchData < mid_value:
        end_idx = mid_idx
        mid_idx = (start_idx + end_idx) // 2
        mid_value = nums[mid_idx]
    
    if searchData == mid_value:
        result_idx = mid_idx
        break

- 검색(찾으려는 값과 일치하는 지 확인)할 때 중간값(mid_value)와 비교한 후, 반절을 고려 대상에서 제외해나가는 과정을 반복하기 때문에 빠르게 탐색할 수 있다.

📍 버블정렬

처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘

nums = [10, 2, 7, 21, 0]

length = len(nums) - 1
for i in range(length):
    for j in range(length - i):
        if nums[j] > nums[j+1]:
            nums[j], nums[j+1] = nums[j+1], nums[j]
            
print(nums) # [0, 2, 7, 10, 21]

- 첫번째 for문의 첫 회에서 제일 큰 값이 맨 끝으로 가게 된다.

- 두번째는 그 다음으로 큰 값을 3번째에, 세번째는 그 다음으로 큰 값을 2번째에 두는 과정이 반복되는 것

📍 삽입정렬

왼쪽에 정렬되어 있는 자료배열과 비교하여 오른쪽 값의 정렬 위치를 찾아 삽입한다.

nums = [5, 10, 2, 1, 0]

for i1 in range(1, len(nums)):
    i2 = i1 - 1
    cNum = nums[i1]
    
    while nums[i2] > cNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1
        
    nums[i2 + 1] = cNum

- for 문에서 현재 기준이 되는 오른쪽의 값을 설정.

- while 문에서 왼쪽에 있는 값들이 기준 값보다 크면 값을 바꿔주는 과정 진행.

📍 선택정렬

주어진 리스트 중에 최소값을 찾아 그 값을 맨 앞에 위치한 값과 교체하는 방식

nums = [4, 2, 5, 1, 3]

for i in range(len(nums) -1):
    min_idx = i
    
    for j in range(i+1, len(nums)):
        if nums[min_idx] > nums[j]:
            min_idx = j
            
    nums[i], nums[min_idx] = nums[min_idx], nums[i]