선형검색
선형검색이란?
선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
n = 0
while True:
if n == len(datas):
searchResultIdx = -1
break
elif datas[n] == searchData:
searchResultIdx = n
break
n += 1
print(f'searchResultIdx: {searchResultIdx}')#결괏값:
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
datas length: 10
찾으려는 숫자 입력: 9
searchResultIdx: 4
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
datas length: 10
찾으려는 숫자 입력: 0
searchResultIdx: 6보초법
마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
datas.append(searchData)
n = 0
while True:
if datas[n] == searchData:
if n != len(datas) - 1:
searchResultIdx = n
break
n += 1
print(f'datas: {datas}')
print(f'len(datas): {len(datas)}')
print(f'searchResultIdx: [{searchResultIdx}]')# 결괏값:
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
datas length: 10
찾으려는 숫자 입력: 0
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 0]
len(datas): 11
searchResultIdx: [6]
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
datas length: 10
찾으려는 숫자 입력: 11
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 11]
len(datas): 11
searchResultIdx: [-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: '))
searchResultIdx = -1 # 몇 번째에 있는지
nums.append(searchData) #보초법 사용하기 위해
n = 0
while True:
if nums[n] == searchData: # 0에서부터 시작
if n != len(nums) - 1: # 입력한 값이 맨 끝에 있는 숫자가 아니면
searchResultIdx = n # 그 수의 자리는 n
break
n += 1
print(f'nums: {nums}')
print(f'len(nums): {len(nums)}')
print(f'searchResultIdx: {searchResultIdx}')
if searchResultIdx < 0: # 못찾았을 때
print('not search index')
else:
print(f'search index: {searchResultIdx}')# 결괏값:
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]
len(nums): 12
searchResultIdx: 1
search index: 1
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
nums length: 11
input search number: 50
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 50]
len(nums): 12
searchResultIdx: -1
not search index리스트에서숫자 '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 = [] # 인덱스 여러 개를 한 번에 다 찾는 것이기 때문에 리스트형 선언
nums.append(searchData) # 보초법 사용을 위해 append 사용
n = 0
while True:
if nums[n] == searchData:
if n != len(nums) - 1: # 입력한 값이 맨 끝에 있는 숫자가 아니면
searchResultIdx.append(n) # 보초법에 의해서 내가 임의로 추가시킨 것(searchResultInx에 추가)
else:
break
n += 1 # 무한 반복에 빠지게 하지 않게 위해
print(f'nums: {nums}')
print(f'len(nums): {len(nums)}')
print(f'searchResultIdx: {searchResultIdx}')
print(f'searchResultCnts: {searchResultIdx}')# 결괏값:
# 입력값이 7일 때,
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] # 마지막 7은 보초법에 의해서 내가 임의로 추가시킨 것
len(nums): 12
searchResultIdx: [1, 5, 8]
# 입력값이 0일 때,
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
nums length: 11
input search number: 0
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 0]
len(nums): 12
searchResultIdx: [6]
# 입력값이 50일 때,
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
nums length: 11
input search number: 50
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 50]
len(nums): 12
searchResultIdx: []
searchResultCnts: []이진검색
이진검색이란?
정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midval = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midval: {midval}')
while searchData <= datas[len(datas)-1] and searchData >= datas[0]:
if searchData == datas[len(datas)-1]:
searchResultIdx = len(datas)-1
break
if searchData > midval:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midval = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midval: {midval}')
elif searchData < midval:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midval = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midval: {midval}')
elif searchData == midval:
searchResultIdx = midIdx
break
print(f'searchResultIdx: {searchResultIdx}')# 결괏값:
# 입력값이 2일 때,
datas: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length: 11
찾으려는 숫자 입력: 2
midIdx: 5
midval: 6
midIdx: 2
midval: 3
midIdx: 1
midval: 2
searchResultIdx: 1
# 입력값이 15일 때,
datas: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length: 11
찾으려는 숫자 입력: 15
midIdx: 5
midval: 6
searchResultIdx: -1
# 입력값이 10일 때,
datas: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length: 11
찾으려는 숫자 입력: 10
midIdx: 5
midval: 6
midIdx: 7
midval: 8
midIdx: 8
midval: 9
midIdx: 9
midval: 10
searchResultIdx: 9이진검색(실습)
실습
리스트를 오름차순으로 정렬한 후 '7'을 검색하고 위치(인덱스)를 추렭하자.
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print(f'nums: {nums}')
nums.sort()
print(f'nums: {nums}')
searchData = int(input('search number: '))
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}')# 결괏값:
# 입력값이 10일 때,
nums: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
search number: 10
searchResultIdx: 5
# 입력값이 61일 때,
nums: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
search number: 61
searchResultIdx: 9
# 입력값이 99일 때,
nums: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
search number: 99
searchResultIdx: -1순위
순위란?
수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다.
import random
nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)] # 길이가 20이가 아이템이 0인 리스트 구조
print(f'nums: {nums}')
print(f'ranks: {ranks}')
for idx, num1 in enumerate(nums):
for num2 in nums:
if num1 < num2:
ranks[idx] += 1
print(f'nums: {nums}')
print(f'ranks: {ranks}')
for i, num in enumerate(nums):
print(f'num: {num} \t rank: {ranks[idx] + 1}')# 결괏값:
nums: [60, 72, 98, 83, 91, 92, 87, 90, 70, 100, 81, 69, 71, 51, 85, 84, 52, 99, 97, 57]
ranks: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
nums: [60, 72, 98, 83, 91, 92, 87, 90, 70, 100, 81, 69, 71, 51, 85, 84, 52, 99, 97, 57]
ranks: [16, 12, 2, 10, 5, 4, 7, 6, 14, 0, 11, 15, 13, 19, 8, 9, 18, 1, 3, 17]
num: 60 rank: 18
num: 72 rank: 18
num: 98 rank: 18
num: 83 rank: 18
num: 91 rank: 18
num: 92 rank: 18
num: 87 rank: 18
num: 90 rank: 18
num: 70 rank: 18
num: 100 rank: 18
num: 81 rank: 18
num: 69 rank: 18
num: 71 rank: 18
num: 51 rank: 18
num: 85 rank: 18
num: 84 rank: 18
num: 52 rank: 18
num: 99 rank: 18
num: 97 rank: 18
num: 57 rank: 18순위(실습)
실습
학급 학생(20명)들의 중간고사와 기말고사 성적을 이용해서 각각의 순위를 구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력하는 프로그램을 만들어보자. (시험 성적은 난수를 이용한다.)
- 모듈
class RankDeviation:
def __init__(self, mss, ess):
self.midStuScos = mss
self.endStuScos = 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.midStuScos, self.midRanks)
def getMidRank(self):
return self.midRanks
def setEndRank(self):
self.setRank(self.endStuScos, 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'mid_rank: {mRank} \t end_rank: {self.endRanks[idx]} \t Deviation: {deviation}')- 모듈 사용
import rankMod as rm
import random
midStuScos = random.sample(range(50, 101), 20)
endStuScos = random.sample(range(50, 101), 20)
rd = rm.RankDeviation(midStuScos, endStuScos)
rd.setMidRank()
print(f'midStuScores: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')
rd.setEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')
rd.printRankDeviation()# 결괏값:
midStuScores: [75, 98, 51, 77, 66, 82, 94, 52, 97, 62, 67, 95, 93, 59, 63, 81, 85, 86, 50, 71]
mid_rank: [10, 0, 18, 9, 13, 7, 3, 17, 1, 15, 12, 2, 4, 16, 14, 8, 6, 5, 19, 11]
endStuScos: [81, 97, 60, 79, 52, 100, 53, 51, 75, 90, 83, 88, 76, 94, 70, 96, 77, 91, 61, 85]
end_rank: [9, 1, 16, 10, 18, 0, 17, 19, 13, 5, 8, 6, 12, 3, 14, 2, 11, 4, 15, 7]
mid_rank: 10 end_rank: 9 Deviation: ↑1
mid_rank: 0 end_rank: 1 Deviation: ↓1
mid_rank: 18 end_rank: 16 Deviation: ↑2
mid_rank: 9 end_rank: 10 Deviation: ↓1
mid_rank: 13 end_rank: 18 Deviation: ↓5
mid_rank: 7 end_rank: 0 Deviation: ↑7
mid_rank: 3 end_rank: 17 Deviation: ↓14
mid_rank: 17 end_rank: 19 Deviation: ↓2
mid_rank: 1 end_rank: 13 Deviation: ↓12
mid_rank: 15 end_rank: 5 Deviation: ↑10
mid_rank: 12 end_rank: 8 Deviation: ↑4
mid_rank: 2 end_rank: 6 Deviation: ↓4
mid_rank: 4 end_rank: 12 Deviation: ↓8
mid_rank: 16 end_rank: 3 Deviation: ↑13
mid_rank: 14 end_rank: 14 Deviation: =0
mid_rank: 8 end_rank: 2 Deviation: ↑6
mid_rank: 6 end_rank: 11 Deviation: ↓5
mid_rank: 5 end_rank: 4 Deviation: ↑1
mid_rank: 19 end_rank: 15 Deviation: ↑4
mid_rank: 11 end_rank: 7 Deviation: ↑4