5주차

5주차

퀵정렬 - 교차되면 멈추고, 피벗과 H 값 스왑, 정렬된 배열의 경우에는 최악

퀵정렬과 셀정렬은 시험에 나올지도?

 

6주차 탐색

 

이진 탐색 - 재귀

def binarySearch(arr, key, lt, rt):
    if lt <= rt:
        mid = (lt+rt) // 2
        if key == arr[mid]:
            return mid
        elif key < arr[mid]:
            return binarySearch(arr, key, lt, mid-1)
        else:
            return binarySearch(arr, key, mid+1, rt)

이진 탐색 - 반복

def binarySearch(arr, key, lt, rt):
    while(lt <= rt):
        mid = (lt + rt)//2
        if key == arr[mid]:
            return mid
        elif key > arr[mid]:
            lt = mid+1
        else:
            rt = mid -1

실습 문제1번

◦ 출력
- x ≤ k 를 만족하는 사전의 키 x 중 가장 큰 값의 위치(즉, 인덱스) 출력
(위치는 0부터 시작한다고 가정하고, 위 조건을 만족하는 x가 없는 경우 –1 출력) - 즉, 키 k가 존재하는 경우에는 k의 위치를 출력하면 되고, 그렇지 않은 경우 k보다 작으면서 가장 큰 수의 위치를 출력하면 된다. 입력 예시 1 출력 예시 1
-7 ↦ k = –7
-92 -31 -7 4 14 20 29 44
□2 ↦ 사전에서 -7의 위치는 2
입력 예시 2 출력 예시 2
33 ↦ k = 33
-92 -31 -7 4 14 20 29 44
□6 ↦ 문제 조건을 만족하는 사전의 키는 29이고, 사전에서 29의 위치는 6
입력 예시 3 출력 예시 3
-93 ↦ k = -93
-92 -31 -7 4 14 20 29 44
□-1 ↦ -93보다 작은 사전의 키는 없음

실습 문제1번 풀이 

처음에는 값을 못찾고 리턴 하는 조건을 

키값보다 작은 값이 없을 때와, 키값보다는 작은 값 중에 제일 큰값을 리턴하는 경우 두가지인줄 알앗는데

rt를 출력하는거 하나만으로 출력이 가능하다

def binarySearch(arr, key, lt, rt):
    if lt <= rt:
        mid = (lt+rt) // 2
        if key == arr[mid]:
            return mid
        elif key < arr[mid]:
            return binarySearch(arr, key, lt, mid-1)
        else:
            return binarySearch(arr, key, mid+1, rt)
    return rt

    #키값보다 작은 값이 없음
    if arr[0] > key : return -1;
    #정렬된거 돌면서 만나는 키값보다 작은 것 중에 제일 큰 값 리턴
    for i in range(len(arr)-1,0,-1):
        if arr[i] < key : return arr[i]
        
    #1번 풀이 굳이 반복문으로 비교하지 않고 rt 하나만으로도 비교 가능하다
    #값을 못찾으면 rt가 교차되서 맨 앞까지 밀려난다
    return rt


key = int(input())
a = list(map(int,input().split(' ')))
length = len(a)

lt = 0
rt = length-1

print(binarySearch(a,key,lt,rt));

실습문제 2번

출력 (문제 1과 약간 다름에 주의) - x ≥ k 를 만족하는 사전의 키 x 중 가장 작은 값의 위치(즉, 인덱스) 출력
(위치는 0부터 시작한다고 가정하고, 위 조건을 만족하는 x가 없는 경우 사전의 키 갯수
출력)
입력 예시 1 출력 예시 1
-100 ↦ k = -100
-92 -31 -7 4 14 20 29 44
□0 ↦ 문제 조건을 만족하는 사전의 키는 -92이고, 사전에서 -92의 위치는 0
입력 예시 2 출력 예시 2
55 ↦ k = 55
-92 -31 -7 4 14 20 29 44
□8 ↦ 55보다 큰 사전의 키는 없음(키의 수)

실습문제 2번 풀이

1번과 거의 유사하다, 배열 내에 키값이 없으면 lt가 인덱스를 넘어가고 리턴이 되는데 그게 배열 전체 원소 갯수와 같고

def binarySearch(arr, key, lt, rt):
    while(lt <= rt):
        mid = (lt + rt)//2
        if key == arr[mid]:
            return mid
        elif key > arr[mid]:
            lt = mid+1
        else:
            rt = mid -1
    return lt


key = int(input())
a = list(map(int,input().split(' ')))
length = len(a)

lt = 0
rt = length-1

print(binarySearch(a,key,lt,rt))

이진 탐색 트리 - 중위순회를 하면 정렬되어서 출력된다