선형으로 나열되어있는 데이터를 순차적으로 스캔하면서 원하는 값이 있는지 없는지 판단
마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화
내가 찾으려는 값을 선형 검색으로 찾다가 마지막에 찾으면 검색실패, 중간에 찾으면 검색 성공하는 판단법
data = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4] ##맨 끝에서 찾으려는 값을 찾았다면 찾은게 아님= 검색 실패/ 마지막 이전에 찾으려는 값을 찾으면= 검색 성공
print(f'data: {data}')
print(f'data length: {len(data)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
data.append(searchData)
n = 0
while True:
if data[n] == searchData:
if n != len(data) -1:
searchResultIdx = n
break
n += 1
print(f'data: {data}')
print(f'data length: {len(data)}')
print(f'SearchResultIdx: [{searchResultIdx}]')
⇊
#검색 성공
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
data length: 10
찾으려는 숫자 입력: 0
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 0]
data length: 11
SearchResultIdx: [6]
#검색실패
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
data length: 10
찾으려는 숫자 입력: 11
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 11]
data length: 11
SearchResultIdx: [-1]
정렬되어있는 자료구조에서 중앙값과의 크고 작음을 이용하여 데이터 검색
자료가 정렬되어있지 않다면 자료를 먼저 정렬해야함
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums.sort()
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
staIdx = 0
endIdx = len(nums) - 1
mididx = (staIdx + endIdx) // 2
midVal = nums[mididx]
while searchData <= nums[len(nums) -1] and searchData >= nums[0]:
if searchData == nums[len(nums) - 1]:
searchResultIdx = len(nums) -1
break
if searchData > midVal:
staIdx = mididx
mididx = (staIdx + endIdx) //2
midVal = nums[mididx]
elif searchData < midVal:
endIdx = mididx
mididx = (staIdx + endIdx) //2
midVal = nums[mididx]
elif searchData == midVal:
searchResultIdx = mididx
break
print(f'searchResultIdx: {searchResultIdx}')
⇊
찾으려는 숫자 입력: 7
searchResultIdx: 3
수의 크고 작음을 이용하여 수의 순서를 정하는 것
##모듈
class RankDeviation:
def __init__(self, mss, ess):
self.midStuScores = mss
self.endStuScores = ess
self.midRank = [0 for i in range(len(mss))]
self.endRank = [0 for i in range(len(mss))]
self.rankDevi = [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.midStuScores, self.midRank)
def setEndRank(self):
self.setRank(self.endStuScores, self.endRank)
def getMidRank(self):
return self.midRank
def setEndRank(self):
self.setRank(self.endStuScores, self.endRank)
def getEndRank(self):
return self.endRank
def printRankDeviation(self):
for idx, mRank in enumerate(self.midRank):
deviation = mRank - self.endRank[idx]
if deviation > 0:
deviation = '↑' + str(abs(deviation)) #abs()=절대값 함수
elif deviation < 0:
deviation = '↓' + str(abs(deviation))
else:
deviation = '=' + str(abs(deviation))
print(f'mid rank: {mRank} \t end rank: {self.endRank[idx]} \t deviation: {deviation}')
##실행
import rankkk as rk
import random
midStuScores = random.sample(range(50, 101), 20)
endStuScores = random.sample(range(50, 101), 20)
rd = rk.RankDeviation(midStuScores, endStuScores)
rd.setMidRank()
print(f'midStuScores: {midStuScores}')
print(f'mid rank: {rd.getMidRank()}')
rd.setEndRank()
print(f'endStuScores: {endStuScores}')
print(f'end rank: {rd.getEndRank()}')
rd.printRankDeviation()
⇊
midStuScores: [94, 99, 57, 62, 67, 61, 89, 93, 63, 92, 78, 55, 64, 73, 100, 79, 88, 71, 75, 95]
mid rank: [3, 1, 18, 16, 13, 17, 6, 4, 15, 5, 9, 19, 14, 11, 0, 8, 7, 12, 10, 2]
endStuScores: [59, 88, 83, 63, 60, 58, 86, 70, 73, 53, 80, 56, 79, 69, 50, 64, 75, 87, 90, 97]
end rank: [15, 2, 5, 13, 14, 16, 4, 10, 9, 18, 6, 17, 7, 11, 19, 12, 8, 3, 1, 0]
mid rank: 3 end rank: 15 deviation: ↓12
mid rank: 1 end rank: 2 deviation: ↓1
mid rank: 18 end rank: 5 deviation: ↑13
mid rank: 16 end rank: 13 deviation: ↑3
mid rank: 13 end rank: 14 deviation: ↓1
mid rank: 17 end rank: 16 deviation: ↑1
mid rank: 6 end rank: 4 deviation: ↑2
mid rank: 4 end rank: 10 deviation: ↓6
mid rank: 15 end rank: 9 deviation: ↑6
mid rank: 5 end rank: 18 deviation: ↓13
mid rank: 9 end rank: 6 deviation: ↑3
mid rank: 19 end rank: 17 deviation: ↑2
mid rank: 14 end rank: 7 deviation: ↑7
mid rank: 11 end rank: 11 deviation: =0
mid rank: 0 end rank: 19 deviation: ↓19
mid rank: 8 end rank: 12 deviation: ↓4
mid rank: 7 end rank: 8 deviation: ↓1
mid rank: 12 end rank: 3 deviation: ↑9
mid rank: 10 end rank: 1 deviation: ↑9
mid rank: 2 end rank: 0 deviation: ↑2
처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
##모듈
import copy
def bubbleSort(ns, deepCopy = True):
if deepCopy:
cns = copy.copy(ns) ##students를 몽땅 카피에서 새로운 students를 생성
else:
cns = ns ##얕은 복사
length = len(cns) - 1
for i in range(length):
for j in range(length - i):
if cns[j] > cns[j +1]:
cns[j], cns[j+1] = cns[j+1], cns[j]
return cns
import bubble as bb
import random as rd
students = []
for i in range(20):
students.append(rd.randint(170, 185))
print(f'students: {students}')
sortedStudents = bb.bubbleSort(students, deepCopy=True)
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')
⇊
students: [175, 171, 179, 185, 174, 183, 178, 172, 179, 176, 170, 178, 181, 174, 180, 178, 182, 170, 179, 178]
students: [175, 171, 179, 185, 174, 183, 178, 172, 179, 176, 170, 178, 181, 174, 180, 178, 182, 170, 179, 178]
sortedStudents: [170, 170, 171, 172, 174, 174, 175, 176, 178, 178, 178, 178, 179, 179, 179, 180, 181, 182, 183, 185]
정렬되어 있는 자료배열과 비교해서, 정렬위치를 찾음
##모듈
class InsertArr:
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):
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 insertarrange as ir
nums = random.sample(range(1, 1000), 100)
print(f'not sorted numbers: {nums}')
#객체 생성
sn = ir.InsertArr(nums)
# 오름차순(ascending)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by asc: {sortedNumbers}')
##내림차순(descending)
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by dsc: {sortedNumbers}')
#min & max
print(f'min: {sn.getMinNumber()}')
print(f'max: {sn.getMaxNumber()}')
⇊
not sorted numbers: [86, 687, 675, 735, 106, 859, 886, 891, 459, 558, 108, 927, 66, 666, 271, 937, 802, 566, 299, 996, 681, 847, 887, 105, 340, 779, 225, 637, 239, 457, 852, 966, 726, 28, 657, 123, 591, 441, 416, 532, 773, 957, 152, 391, 308, 529, 323, 458, 550, 117, 444, 827, 34, 863, 29, 432, 84, 396, 505, 200, 866, 740, 329, 236, 318, 183, 96, 216, 330, 809, 800, 613, 544, 175, 745, 161, 195, 536, 991, 974, 860, 636, 286, 651, 765, 737, 379, 851, 921, 250, 132, 51, 332, 569, 158, 571, 724, 512, 547, 764]
sortedNumbers by asc: [28, 29, 34, 51, 66, 84, 86, 96, 105, 106, 108, 117, 123, 132, 152, 158, 161, 175, 183, 195, 200, 216, 225, 236, 239, 250, 271, 286, 299, 308, 318, 323, 329, 330, 332, 340, 379, 391, 396, 416, 432, 441, 444, 457, 458, 459, 505, 512, 529, 532, 536, 544, 547, 550, 558, 566, 569, 571, 591, 613, 636, 637, 651, 657, 666, 675, 681, 687, 724, 726, 735, 737, 740, 745, 764, 765, 773, 779, 800, 802, 809, 827, 847, 851, 852, 859, 860, 863, 866, 886, 887, 891, 921, 927, 937, 957, 966, 974, 991, 996]
sortedNumbers by dsc: [996, 991, 974, 966, 957, 937, 927, 921, 891, 887, 886, 866, 863, 860, 859, 852, 851, 847, 827, 809, 802, 800, 779, 773, 765, 764, 745, 740, 737, 735, 726, 724, 687, 681, 675, 666, 657, 651, 637, 636, 613, 591, 571, 569, 566, 558, 550, 547, 544, 536, 532, 529, 512, 505, 459, 458, 457, 444, 441, 432, 416, 396, 391, 379, 340, 332, 330, 329, 323, 318, 308, 299, 286, 271, 250, 239, 236, 225, 216, 200, 195, 183, 175, 161, 158, 152, 132, 123, 117, 108, 106, 105, 96, 86, 84, 66, 51, 34, 29, 28]
min: 28
max: 996
주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘
최소값을 찾는게 가장 중요
nums = [4, 2, 5, 1, 3]
for i in range(len(nums)-1):
minIdx = i
for j in range(i+1, len(nums)):
if nums[minIdx] > nums[j]:
minIdx = j
#자리바꿈하는 코드
# tempNum = nums[i]
# nums[i] = nums[minIdx]
# nums[minIdx] = tempNum
nums[i], nums[minIdx]= nums[minIdx], nums[i]
print(f'nums: {nums}')
print(f'nums: {nums}')
⇊
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 3, 4, 5]
nums: [1, 2, 3, 4, 5]
nums: [1, 2, 3, 4, 5]
#모듈
def sortNumber(ns, asc=True):
if asc:
for i in range(len(ns)- 1):
minIdx = i
for j in range(i + 1, len(ns)):
if ns[minIdx] > ns[j]:
minIdx = j
ns[i], ns[minIdx] = ns[minIdx], ns[i]
else:
for i in range(len(ns) - 1):
minIdx = i
for j in range(i + 1, len(ns)):
if ns[minIdx] < ns[j]:
minIdx = j
ns[i], ns[minIdx] = ns[minIdx], ns[i]
return ns
##실행
import random
import selectArr as sa
scores = random.sample(range(50, 101), 20)
print(f'Scores: {scores}')
print(f'scores length: {len(scores)}')
result = sa.sortNumber(scores)
print(f'result: {result}')
result = sa.sortNumber(scores, asc=False)
print(f'result: {result}')
⇊
Scores: [96, 84, 88, 51, 83, 95, 59, 62, 66, 72, 58, 99, 98, 80, 81, 71, 73, 55, 77, 78]
scores length: 20
result: [51, 55, 58, 59, 62, 66, 71, 72, 73, 77, 78, 80, 81, 83, 84, 88, 95, 96, 98, 99]
result: [99, 98, 96, 95, 88, 84, 83, 81, 80, 78, 77, 73, 72, 71, 66, 62, 59, 58, 55, 51]
자료구조에서 가장 큰 값
class MaxAlgorithm:
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
def getMaxNum(self):
self.maxNum = self.nums[0]
for n in self.nums:
if self.maxNum < n:
self.maxNum = n
return self.maxNum
ma = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
maxNum = ma.getMaxNum()
print(f'Max Num: {maxNum}')
⇊
Max Num: 20