▷ 오늘 학습 계획: 알고리즘 강의(문풀 1~3)
검색 알고리즘
- 선형 검색: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
- 이진 검색: 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
선형 검색
def searchNumberByLine(ns, sn):
searchResultIdx = -1
print(f'Numbers: {ns}')
print(f'Search Number: {sn}')
n = 0
while True:
if n == len(ns):
print('Search fail')
break
if ns[n] == sn:
searchResultIdx = n
print('Search success')
print(f'search result index: {searchResultIdx}')
break
n += 1
return searchResultIdx이진 검색
def searchNumberByBinary(ns, sn):
searchResultIdx = -1
staIdx = 0
endIdx = len(ns)-1
midIdx = (staIdx + endIdx) // 2
midVal = ns[midIdx]
print(f'staIdx: {staIdx}, endIdx: {endIdx}')
print(f'midIdx: {midIdx}, midVal: {midVal}')
while sn >= ns[0] and sn <= ns[len(ns)-1]:
if sn == ns[len(ns)-1]:
searchResultIdx = len(ns)-1
break
if staIdx + 1 == endIdx:
if ns[staIdx] != sn and ns[endIdx] != sn:
break
if sn > midVal:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = ns[midIdx]
print(f'+staIdx: {staIdx}, endIdx: {endIdx}')
print(f'+midIdx: {midIdx}, midVal: {midVal}')
elif sn < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = ns[midIdx]
print(f'-staIdx: {staIdx}, endIdx: {endIdx}')
print(f'-midIdx: {midIdx}, midVal: {midVal}')
elif sn == midVal:
searchResultIdx = midIdx
break
return searchResultIdx순위 알고리즘
- 수의 크고 작음을 이용해서 수의 순서를 정하는 것
순위
datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T',
't', 22, 31, 55, 's', 63, 59, 'E']
print(f'datas: {datas}')
ascIIDatas = []
for data in datas:
if str(data).isalpha():
ascIIDatas.append(ord(data))
continue
ascIIDatas.append(data)
print(f'ascIIDatas: {ascIIDatas}')
ranks = [0 for i in range(len(ascIIDatas))]
for idx, data1 in enumerate(ascIIDatas):
for data2 in ascIIDatas:
if data1 < data2:
ranks[idx] += 1
print(f'{ranks}')
for i,d in enumerate(datas):
print(f'data: {d:>2} \t rank: {ranks[i]+1}')정렬 알고리즘
- 버블 정렬: 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
- 삽입 정렬: 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
- 선택 정렬: 주어진 리스트 중에 최소값을 찾아서 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬
- 병합 정렬: 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
- 퀵 정렬: 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
버블 정렬
- 숫자로 이루어진 리스트를 오름차순과 내림차순으로 정렬하는 모듈
import copy
def sortByBubble(ns, asc = True): #기본값: 오름차순
c_ns = copy.copy(ns) #깊은 복사로 원본 데이터 유지
length = len(c_ns)-1
for i in range(length):
for j in range(length-i):
if asc:
if c_ns[j] > c_ns[j+1]:
c_ns[j], c_ns[j+1] = c_ns[j+1], c_ns[j]
else:
if c_ns[j] < c_ns[j+1]:
c_ns[j], c_ns[j+1] = c_ns[j+1], c_ns[j]
print(f'ns: {c_ns}')
print()
return c_ns선택 정렬
- 숫자로 이루어진 리스트를 오름차순과 내림차순으로 정렬하는 모듈
import copy
def sortBySelect(ns, asc = True):
c_ns = copy.copy(ns)
for i in range(len(c_ns)-1):
minIdx = i
for j in range(i+1, len(c_ns)):
if asc:
if c_ns[minIdx] > c_ns[j]:
minIdx = j
else:
if c_ns[minIdx] < c_ns[j]:
minIdx = j
c_ns[i], c_ns[minIdx] = c_ns[minIdx], c_ns[i]
print(f'nums: {c_ns}')
return c_ns삽입 정렬
- 1부터 20까지 10개의 숫자로 이루어진 리스트를 삽입정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
import copy
def sortByInsert(ns, asc = True):
c_ns = copy.copy(ns) #원본 데이터 유지하도록 깊은 복사
for i1 in range(1, len(c_ns)):
i2 = i1 -1
currentN = c_ns[i1]
if asc: #오름차순
while c_ns[i2] > currentN and i2 >= 0:
c_ns[i2 + 1] = c_ns[i2]
i2 -= 1
else: #내림차순
while c_ns[i2] < currentN and i2 >= 0:
c_ns[i2 + 1] = c_ns[i2]
i2 -= 1
c_ns[i2 + 1] = currentN
print(f'c_ns: {c_ns}')
return c_ns병합 정렬
- 1부터 20까지 10개의 숫자로 이루어진 리스트를 병합정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
def mSort(ns, asc = True):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx], asc=asc)
rightNums = mSort(ns[midIdx:len(ns)], asc=asc)
mergeNums = []
leftIdx = 0; rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
if asc:
if leftNums[leftIdx] < rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
else:
if leftNums[leftIdx] > rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
mergeNums += leftNums[leftIdx:]
mergeNums += rightNums[rightIdx:]
print(f'mergeNums: {mergeNums}')
return mergeNums▷ 내일 학습 계획: 알고리즘 강의(문풀 4~5)
