📌이진탐색
💡이진탐색 : 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색
Q. 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자.
- 검색 모듈은 이진 검색 알고리즘을 이용하자.
- 리스트는 [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]를 이용하자.
- 검색 과정을 로그로 출력하자.
- 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없다면 –1을 출력하자
- binary_search.py
def binarySearch(nums, search_num):
staIdx = 0
endIdx = len(nums) - 1
minIdx = (staIdx + endIdx) // 2
midVal = nums[minIdx]
search_idx = -1
print(f'staIdx: {staIdx}, endIdx: {endIdx}')
print(f'minIdx: {minIdx}, midVal: {midVal}')
while search_num <= nums[len(nums) - 1] and search_num >= nums[0]:
if staIdx + 1 == endIdx:
if nums[staIdx] != search_num and nums[endIdx] != search_num:
break
if midVal == search_num:
search_idx = minIdx
break
elif midVal > search_num:
endIdx = minIdx
minIdx = (staIdx + endIdx) // 2
midVal = nums[minIdx]
print(f'-staIdx: {staIdx}, endIdx: {endIdx}')
print(f'-minIdx: {minIdx}, midVal: {midVal}')
else:
staIdx = minIdx
minIdx = (staIdx + endIdx) // 2
midVal = nums[minIdx]
print(f'+staIdx: {staIdx}, endIdx: {endIdx}')
print(f'+minIdx: {minIdx}, midVal: {midVal}')
return search_idx- binaryEx.py
import binary_search as bs
if __name__ == '__main__':
nums = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
search_num = int(input('input search number: '))
search_idx = bs.binarySearch(nums, search_num)
print('>>> Search Result <<<')
print(f'search result index: {search_idx}')
print(f'search result number: {search_num}')- 출력결과
📌순위
💡순위 : 수의 크고 작음을 이용해서 수의 순서를 정하는 것(rank)
Q.알파벳 문자들과 정수들에 대한 순위를 정하는 프로그램을 순위 알고리즘을 이용해서 만들어 보자. 단, 알파벳은 아스키코드 값을 이용한다.
[32, ‘a’, ‘z’, 45, ‘G’, 39, 50, ‘T’, ‘t’, 22, 31, 55, ‘s’, 63, 59, ‘E’]
datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
print(f'datas: {datas}')
ascII_datas = []
for data in datas:
if str(data).isalpha():
ascII_datas.append(ord(data)) # ord: 문자 -> 아스키
continue
ascII_datas.append(data)
print(f'ascII datas: {ascII_datas}')
ranks = [0 for i in range(len(ascII_datas))]
print(f'ranks before: {ranks}')
for idx, data1 in enumerate(ascII_datas):
for data2 in ascII_datas:
if data1 < data2:
ranks[idx] += 1
print(f'ranks after: {ranks}')
for i, d in enumerate(datas):
print(f'data: {d:>2} \t rank: {ranks[i] + 1}')- 출력결과
📌버블정렬
💡버블정렬: 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
Q. 숫자로 이루어진 리스트를 버블정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자.(단 정렬하는 과정도 출력하도록 한다.)
- bubble_sort.py
def bubble_sort(ns, asc=True):
length = len(ns) - 1
for i in range(length):
for j in range(length-i):
if asc == True and ns[j] > ns[j+1]:
ns[j], ns[j+1] = ns[j+1], ns[j]
if asc == False and ns[j] < ns[j+1]:
ns[j], ns[j+1] = ns[j+1], ns[j]
print(ns)
print()
return ns- bubbleEx.py
import bubble_sort as bs
import copy # 깊은 복사하기 위함
if __name__ == '__main__':
nums = [10, 4, 1, 13, 11, 16, 19, 14, 6, 5]
print(f'not sorted nums: {nums}')
print(f'sorted nums by ASC: {bs.bubble_sort(copy.deepcopy(nums))}')
print()
print(f'sorted nums by DESC: {bs.bubble_sort(copy.deepcopy(nums), False)}')- 출력결과
📌삽입정렬
💡삽입정렬: 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는 알고리즘.
Q. 숫자로 이루어진 리스트를 삽입정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자.(단 정렬하는 과정도 출력하도록 한다.)
- insert_sort.py
def insert_sort(ns, asc=True):
print(f'not sorted nums: \n{ns}')
for i1 in range(1, len(ns)):
i2 = i1 - 1
c_num = ns[i1]
if asc:
while ns[i2] > c_num and i2 >= 0:
ns[i2 + 1] = ns[i2]
i2 -= 1
else:
while ns[i2] < c_num and i2 >= 0:
ns[i2 + 1] = ns[i2]
i2 -= 1
ns[i2 + 1] = c_num
print(f'ns: {ns}')
return ns- insertEx.py
import random
import copy
import insert_sort as iss
if __name__ == '__main__':
nums = random.sample(range(1, 20), 10)
result = iss.insert_sort(copy.deepcopy(nums))
print(f'sorted nums by ASC: \n{result}')
print()
result = iss.insert_sort(copy.deepcopy(nums), False)
print(f'sorted nums by DESC: \n{result}')- 출력결과
📌선택정렬
💡 선택정렬: 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘.
Q. 숫자로 이루어진 리스트를 선택정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자.(단 정렬하는 과정도 출력하도록 한다.)
- select_sort.py
def select_sort(ns, asc=True):
print(f'not sorted nums: \n{ns}')
for i in range(len(ns) - 1):
check_idx = i
for j in range(i + 1, len(ns)):
if asc:
if ns[check_idx] > ns[j]:
check_idx = j
else:
if ns[check_idx] < ns[j]:
check_idx = j
ns[i], ns[check_idx] = ns[check_idx], ns[i]
print(f'nums: {ns}')
return ns- selectEx.py
import random
import copy
import select_sort as ssort
if __name__ == '__main__':
nums = random.sample(range(1, 21), 10)
result = ssort.select_sort(copy.deepcopy(nums))
print(f'sorted nums by ASC: \n{result}')
print()
result = ssort.select_sort(copy.deepcopy(nums), False)
print(f'sorted nums by DESC: \n{result}')- 출력결과
📌병합정렬
💡 벙합정렬: 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬하는 알고리즘.
Q. 숫자로 이루어진 리스트를 병합정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자.(단 정렬하는 과정도 출력하도록 한다.)
- merge_sort.py
def merge_sort(ns, asc=True):
if len(ns) < 2: # 더이상 분할할 수 없는 경우
return ns
mid_idx = len(ns) // 2
left_nums = merge_sort(ns[:mid_idx], asc=asc) # asc=asc 꼭 해야함
right_nums = merge_sort(ns[mid_idx:], asc=asc)
merged_nums = []
left_idx, right_idx = 0, 0
while left_idx < len(left_nums) and right_idx < len(right_nums):
if asc:
if left_nums[left_idx] < right_nums[right_idx]:
merged_nums.append(left_nums[left_idx])
left_idx += 1
else:
merged_nums.append(right_nums[right_idx])
right_idx += 1
else:
if left_nums[left_idx] > right_nums[right_idx]:
merged_nums.append(left_nums[left_idx])
left_idx += 1
else:
merged_nums.append(right_nums[right_idx])
right_idx += 1
merged_nums += left_nums[left_idx:]
merged_nums += right_nums[right_idx:]
print(f'merged_nums: {ns}')
return merged_nums- mergeEx.py
import random
import copy
import merge_sort as ms
if __name__ == '__main__':
nums = random.sample(range(1, 101), 20)
print(f'not sorted nums: \n{nums}')
result = ms.merge_sort(copy.deepcopy(nums))
print(f'sorted nums by ASC: \n{result}')
print()
print(f'not sorted nums: \n{nums}')
result = ms.merge_sort(copy.deepcopy(nums), False)
print(f'sorted nums by DESC: \n{result}')- 출력결과
"이 글은 제로베이스 데이터 취업 스쿨 강의 자료 일부를 발췌한 내용이 포함되어 있습니다."
