선형 검색
:선형으로 나열되어 있는 데이터를 순차적으로 스캔해서 원하는 값을 찾는다.
- 리스트에서 가장 앞에 있는 숫자 7을 검색하고 위치를 출력한다.
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
searchData = int(input('input search number: '))
searchResultIdx = -1
nums.append(searchData)
n = 0
while True:
if nums[n] == searchData:
if n != len(nums) - 1:
searchResultIdx = n
break
n += 1
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdx: {searchResultIdx}')
if searchResultIdx < 0:
print('not search index')
else:
print(f'search index: {searchResultIdx}')
[Output]
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
nums length: 11
input search number: 7
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
nums length: 12
searchResultIdx: 1
search index: 1- 리스트에서 숫자 ‘7’을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자.
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
searchData = int(input('input search number: '))
searchResultIdxs = [] #위 식과 달라진 부분!
nums.append(searchData)
n = 0
while True:
if nums[n] == searchData:
if n != len(nums) - 1:
searchResultIdxs.append(n)
else:
break
n += 1
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdxs: {searchResultIdxs}')
print(f'searchResultCnts: {len(searchResultIdxs)}')이진 검색 : 정렬되어 있는 자료구조에서 중앙값과 크고 작음을 이용해서 데이터를 검색한다.
- 리스트를 오름차순으로 정렬한 후 ‘7’을 검색하고 위치(인덱스)를 출력하자
datas = [ 4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
datas.sort()
print('datas:{}'.format(datas))
searchNum = int(input('찾으려는 값을 입력하세요:'))
searchResultIdx = -1
startIdx = 0
endIdx = len(datas) - 1
midIdx = (startIdx+endIdx) // 2
midVal = datas[midIdx]
while searchNum <= datas[len(datas)-1] and searchNum >= datas[0]:
if searchNum == datas[len(datas) - 1]:
searchResultIdx = len(datas) -1
break
elif searchNum > midVal:
startIdx = midIdx
midIdx = (startIdx+endIdx) // 2
midVal = datas[midIdx]
elif searchNum < midVal:
endIdx = midIdx
midIdx = (startIdx + endIdx) // 2
midVal = datas[midIdx]
elif searchNum == midVal:
searchResultIdx = midIdx
break
print('searchResultIdx:{}'.format(searchResultIdx))
[Output]
datas:[0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
>> 찾으려는 값을 입력하세요:9
searchResultIdx:4순위 : 수의 크고 작음을 이용해 수의 순서를 정하는 것
- 학급 학생 20명의 중간고사 기말고사 성적을 이용해 각각 순위를 구하고, 중간고사 대비 기말고사 순위변화(편차)를 출력, 시험성적은 난수 발생
모듈
class RankDeviation:
def __init__(self,mss,ess):
self.midStuSco = mss
self.endStuSco = ess
self.midRanks = [0 for i in range(len(mss))]
self.endRanks = [0 for i in range(len(mss))]
self.rankDeviation = [0 for i in range(len(mss))]
def setRank(self,ss,rs):
for idx, sco1 in enumerate(ss):
for sco2 in ss:
if sco1 < sco2:
rs[idx] +=1
def setMidRank(self):
self.setRank(self.midStuSco, self.midRanks)
def getMidRank(self):
return self.midRanks
def setEndRank(self):
self.setRank(self.endStuSco, self.endRanks)
def getEndRank(self):
return self.endRanks
def printRankDeviation(self):
for idx, mRank in enumerate(self.midRanks):
deviation = mRank - self.endRanks[idx]
if deviation >0:
deviation = '↑' +str(abs(deviation))
elif deviation <0:
deviation = '↓' + str(abs(deviation))
else:
deviation = '=' + str(abs(deviation))
print(f'midRank : {mRank} \t endRank : {self.endRanks[idx]} \t deviation : {deviation}')실행
import book as rk
import random
midStuSco = random.sample(range(50,101),20)
endStuSco = random.sample(range(50,101),20)
rd = rk.RankDeviation(midStuSco,endStuSco)
rd.setMidRank()
print(f'midStuScors : {midStuSco}')
print(f'midRank : {rd.getMidRank()}')
rd.setEndRank()
print(f'EndStuScors : {endStuSco}')
print(f'endRank : {rd.getEndRank()}')
rd.printRankDeviation()버블 정렬 : 처음부터 끝까지 인접하는 인덱스 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
- 학생들의 키를 random 모듈을 이용하여 170 ~ 185 사이로 생성한다.
모듈
# 얕은 복사
def bubbleSort(ns):
length = len(ns) - 1
for i in range(length):
for j in range(length - i):
if ns[j] > ns[j + 1]:
ns[j], ns[j + 1] = ns[j + 1], ns[j]
return ns
# 깊은 복사
import copy
def bubbleSort(ns, deepCopy=True):
if deepCopy:
cns = copy.copy(ns)
else:
ens = ns
length = len(ns) - 1
for i in range(length):
for j in range(length - i):
if ns[j] > ns[j + 1]:
ns[j], ns[j + 1] = ns[j + 1], ns[j]
return ns실행
import random as rd
import sortMod as sm
students = []
for i in range(20):
students.append(rd.randint(170,185))
sortedStudents = print(f'students : {students}')
sm.bubbleSort(students, deepCopy = False)
print(f'sortedStudents : {sortedStudents}')삽입 정렬 : 정렬되어 있는 자료 배열과 비교해서 정렬 위치를 찾는다.
- 1부터 1000까지의 난수 100개를 생성하고 1) 생성한 난수를 오름차순, 내림차순으로 구현하는 알고리즘 2) 생성된 난수 중 최솟값, 최댓값을 반환하는 함수를 구현하는 모듈을 만들어라
모듈
class SortNumbers:
def __init__(self, ns, asc = True):
self.nums = ns
self.isAsc = asc
def isAscending (self, flag):
self.isAsc = flag
def setSort(self):
for i1 in range(1, len(self.nums)):
i2 = i1 - 1
cNum = self.nums[i1]
if self.isAsc: #오름차순인 경우
while self.nums[i2] > cNum and i2 >=0:
self.nums[i2 + 1] = self.nums[i2]
i2 -= 1
else: #내림차순인 경우
while self.nums[i2] < cNum and i2 >=0:
self.nums[i2 + 1] = self.nums[i2]
i2 -= 1
self.nums[i2 +1] = cNum
def getSortedNumbers(self): #외부에서 sorted배열을 가져갈 수 있도록 하는 함수
return self.nums
def getMinNumber(self):
if self.isAsc: #오름차순일 경우
return self.nums[0]
else:
return self.nums[len(self.nums) -1]
def getMaxNumber(self):
if self.isAsc:
return self.nums[len(self.nums) - 1]
else:
return self.nums[0]
실행
import random
import sortMod as sm
nums = random.sample(range(1,1000),100)
print(f'not sorted numbers : {nums}')
# 객체 생성
sn = sm.SortNumbers(nums)
# 오름차순
sn.setSort() # 정렬
sortedNumbers = sn.getSortedNumbers() #출력
print(f'sortedNumbers : {sortedNumbers}')
#내림차순
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by DESC : {sortedNumbers}')
# min & max
print(f'min : {sn.getMinNumber()}')
print(f'max : {sn.getMaxNumber()}')선택정렬 : 주어진 리스트 중에 1) 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 2) 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
- 20명의 시험점수를 오름차순, 내림차순으로 정렬하는 모듈
모듈
def sortNumbers(nums,asc=True):
if asc: #오름차순이 True일 때
for i in range(len(nums)-1):
minIdx = i
for j in range(i+1,len(nums)):
if nums[minIdx] > nums[j]:
minIdx = j
nums[i], nums[minIdx] = nums[minIdx], nums[i]
else:
for i in range(len(nums)-1):
minIdx = i
for j in range(i+1,len(nums)):
if nums[minIdx] < nums[j]:
minIdx = j
nums[i], nums[minIdx] = nums[minIdx], nums[i]
return nums실행
import random
import module as md
scores = random.sample(range(50,101),20)
print(scores)
print(len(scores))
result = md.sortNumbers(scores)
print(result)위처럼 얕은 복사일 경우 원 데이터도 함께 정렬된다. 이를 원하지 않는 경우 copy함수를 이용해 복제한 데이터(깊은 복사)를 활용한다.
최댓값
- 리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 만들어보자
class MaxAlgorithm:
def __init__(self,cs):
self.chars = cs
self.maxChar = 0
def getMaxChar(self):
self.maxChar = self.chars[0]
for a in self.chars:
if ord(self.maxChar) < ord(a):
self.maxChar = a
return self.maxChar
chars = ['c','x','Q','A','e','P','p']
ma = MaxAlgorithm(chars)
result = ma.getMaxChar()
print('아스키 코드 값이 가장 큰 값은:{}'.format(result))
최솟값
- 리스트에서 아스키코드가 가장 작은값을 찾는 알고리즘을 만들어보자
class MinAlgorithm:
#초기화 하는 역할
def __init__(self, cs):
self.chars = cs
self.minChar = 0
def getMinChar(self):
self.minChar = self.chars[0]
for c in self.chars:
if ord(self.minChar) > ord(c):
self.minChar = c
return self.minChar
chars = ['c', 'x', 'Q', 'A']
mi = MinAlgorithm(chars)
minChar = mi.getMinChar()
print(f'minChar : {minChar}')최빈값
class MaxAlgorithm:
def __init__(self,ns):
self.nums = ns
self.maxNum = 0
self.maxNumIdx = 0
def setMaxNumAndIdx(self):
self.maxNum = self.nums[0]
self.maxNumIdx = 0
for i, n in enumerate(self.nums):
if self.maxNum < n:
self.maxNum = n
self.maxNumIdx = i
def getMaxNum(self):
return self.maxNum
def getMaxIdx(self):
return self.maxNumIdx
nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlo = MaxAlgorithm(nums)
maxAlo.setMaxNumAndIdx()
maxNum = maxAlo.getMaxNum()
print(f'maxNum:{maxNum}')
indexes = [0 for i in range(maxNum+1)]
print(indexes)
for n in nums:
indexes[n] = indexes[n] + 1
print(indexes)
maxAlo = MaxAlgorithm(indexes)
maxAlo.setMaxNumAndIdx()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxIdx()
print(f'{maxNumIdx}의 숫자가 {maxNum}의 빈도수로 가장 높다')
데이터로 경로를 탐색합니다.
0개의 댓글
