알고리즘-0927(K번째 수)

Об этом предложении

1. 선택 정렬 저번주차에서 했던 내용에서 이어서 설명하자면 선택 정렬은 정렬되지 않은 부분에서 가장 작은 값을 찾아 맨 앞으로 가져오는 방식 이다. 예시 코드를 들어보자. def selection_sort(data): n = len(data) for i in range(n - 1): min_index = i for j in range(i + 1, n): if data[j] < data[min_index]: min_index = j data[i], data[min_index] = data[min_index], data[i] return data 라는 코드가 있다. 이 코드는 최솟값을 찾아서 현재 위치와 교환한다. 즉, 일단 현재 숫자를 가장 작은 숫자라 가정하고 더 작은 숫자를 발견하면 그 위치를 기억한다. 그리고 끝까지 찾아본 후 교환하면서 정렬을 실행한다. 이 정렬을 시각적으로 표현하면 이렇게 된다. 2. 삽입 정렬 삽입 정렬은 선택 정렬과 생각하는 방식이 다르다. 삽입 정렬은 삽입 정렬은 이미 정렬된 영역과 아직 정렬되지 않은 영역으로 나뉜다. 두 번째 요소부터 시작하여 자신의 왼쪽 요소와 한 칸씩 비교하며 왼쪽으로 이동한다. 자신보다 큰 요소들은 오른쪽으로 이동시키고, 자신보다 작거나 같은 요소를 만나면 그 바로 뒤에 삽입한다. 이 과정을 반복하면서 정렬된 영역을 확장한다. 삽입정렬은 key 를 활용하냐 안하냐에 따라 두가지 방식으로 나뉘는데, key를 사용하거나, 사용하지 않는 swap 방식이 있다. Key 활용 예시 코드를 들어보자. def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr 여기에서 key = arr[i] 가 끼워 넣을 숫자이다. 그리고 j= i-1 로 바로 왼쪽부터 검사한다. while j >= 0 and arr[j] > key: 을 통해 만약 key 보다 큰 숫자가 있다면 arr[j + 1] = arr[j] 을 통해 오른쪽으로 보내고 그 자리에 arr[j + 1] = key 을 통해 key 를 삽입한다. key 를 통한 삽입 정렬을 이해하기 쉽게 시각화하면 이렇게 된다. SWAP Swap 방식은 key 를 사용하지 않고 삽입 정렬을 실행한다. 예시 코드를 들면 array = [6, 3, 5, 2, 4] for i in range(1, len(array)): for j in range(i, 0, -1): if array[j] < array[j - 1]: array[j], array[j - 1] = array[j - 1], array[j] else: break print(array) 라는 코드가 있다. 우선 첫 번째 요소 6은 혼자이므로 이미 정렬되었다고 간주한다. 먼저 두 번째 요소인 3부터 시작하여 왼쪽에 있는 6과 비교한다. 이때 6이 3보다 더 크므로 swap 한다 [6, 3, 5, 2, 4] ↕ [3, 6 | 5, 2, 4] 이러한 상황이 완성되게 된다. 이제 다음으로 세 번째 요소인 5를 바로 왼쪽의 6과 비교한다. 이때 6이 더 크므로 swap 한다. 여기서 끝이 아니라 한 칸 이동한 후 바로 왼쪽의 3과 또 값을 비교한다. 이때는 5가 3보다 더 크니까 swap 할 필요가 없어진다. [3, 5, 6 | 2, 4] 이러한 방식을 2와 4에 계속해서 적용하면 결국 [2, 3, 4, 5, 6] 이 나오게 된다. 이 과정또한 시각적으로 표현하면 이러한 모습이 된다. 3. K번째 수 문제 및 제한사항 입출력 예 선택 정렬 def solution(array, commands): answer = [] for command in commands: i = command[0] j = command[1] k = command[2] new_array = array[i-1:j] for a in range(len(new_array) - 1): min_index = a for b in range(a + 1, len(new_array)): if new_array[b] < new_array[min_index]: min_index = b new_array[a], new_array[min_index] = new_array[min_index], new_array[a] answer.append(new_array[k-1]) return answer 삽입 정렬 ```python

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.38

Уверенность

49%