알고리즘에 대해 알아보자!
- 선형 검색
- 이진 검색
- 순위
- 버블 정렬
1.선형 검색
선형검색 이란?
선으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는 것
- idx 0 부터 끝번호 까지 순차적으로 검색한다
- 결과는 '검색 성공' or '검색 실패'
■ 선형 검색
- Key Point !
찾으려는 데이터가 없어서 끝까지(len(datas)) 찾아보는 문장
if n == len(datas):
searchResultIdx = -1
break- 아래 예제로 자세히 알아보자!
datas = [3,2,5,7,9,1,0,8,6,4]
print(f'datas : {datas}')
print(f'length : {len(datas)}')
searchData = int(input('찾으려는 숫자 : '))
#우리가 찾는 숫자(searchResultIdx)가 몇번째 인덱스에 있는지 알고 싶음
# 존재하지 않는 숫자인 -1로 먼저 설정
searchResultIdx = -1
n = 0
while True :
⭐
if n == len(datas): #n이 끝까지 갔다 = 검색한 결과가 없다(=일치하는 데이터가 없다)는 것과 같은 말
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]
length : 10
찾으려는 숫자 : 7
searchResultIdx : 3■ 보초법
마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화 하는 방법
- idx 0 부터 끝번호 까지 순차적으로 검색한다
- '검색 성공' : 마지막 이전에 원하는 숫자를 찾은 경우
- '검색 실패' : 마지막에 원하는 숫자가 검색된 경우
- 선형검색/보초법의 차이점
1)datas.append(searchData): 아이템 추가
2)if n != len(datas) - 1: 끝에 있는 아이템인지 조사
3) 끝까지 가서 찾는 문장(len(data))이 없음
datas = [3,2,5,7,9,1,0,8,6,4]
print(f'datas : {datas}')
print(f'length : {len(datas)}')
searchData = int(input('찾으려는 숫자 : '))
searchResultIdx = -1
datas.append(searchData) ⭐
n =0
while True:
if datas[n] == searchData: # 입력한 숫자가 있다면
if n != len(datas) - 1: # 그런데, n이 맨끝에 있는 값이 아니네?
searchResultIdx = n # 이전에 찾았네!
break # 끝!
n += 1
print(f'datas : {datas}')
print(f'data length : {len(datas)}')
print(f'searchResultIdx : {searchResultIdx}')▼
datas : [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
length : 10
찾으려는 숫자 : 11
datas : [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 11] ⭐ #11이 추가 됨
data length : 11 ⭐#없는 숫자를 .append()해서 길어짐
searchResultIdx : -1 ⭐
# 없는 숫자를 .append() 했기 때문에(원래 없던 숫자를 추가해서)
# 위에 설정해둔 "searchResultIdx = -1"에 따라서 -1자리로 표현됨■ 실습_1
Q >
리스트에서 가장 앞에 있는 숫자 7 을 검색하고 위치(인덱스)를 출력하라
- nums = [4,7,10,2,4,7,0,2,7,3,9]
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('찾으려는 숫자 입력: '))
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(f'찾으려는 {searchData}가(이) 없습니다.')
else:
print(f'찾으려는 {searchData}의 위치(인덱스)는 {searchResultIdx}입니다.')▼
없는 숫자 '50'을 찾는 경우
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
nums length: 11
찾으려는 숫자 입력: 50
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 50]
nums length: 12
searchResultIdx: [-1]
찾으려는 50가(이) 없습니다.있는 숫자 '7'을 찾는 경우
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
nums length: 11
찾으려는 숫자 입력: 7
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
nums length: 12
searchResultIdx: [1]
찾으려는 7의 위치(인덱스)는 1입니다.■ 실습_2
Q >
리스트에서 7 을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하라
- 함수X 풀이
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('찾으려는 숫자 입력: '))
searchResultIdxs = [] # list() 선언
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'searchResultCount: {len(searchResultIdxs)}')- 함수O 풀이
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
def searchNum(tempNums):
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdxs = []
tempNums.append(searchData)
n =0
while True:
if tempNums[n] == searchData:
if n != len(tempNums) -1 :
searchResultIdxs.append(n)
else:
break
n += 1
return searchResultIdxs
searchResultIdxs = searchNum(nums)
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdxs : {searchResultIdxs}')
2. 이진 검색
정렬되어 있는자료구조에서 중앙값과의 크고 작음을 이용해 데이터를 검색한다.
- 데이터가 정렬되어 있어야 한다..!!!
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,]
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
# datas = [1, 3, 4, 6, 7, 8, 9, 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() 문장이 최고...!
# len(datas)-1 : "끝에 있는 데이터"라는 뜻
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}]')▼
datas: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length: 11
찾으려는 숫자 입력: 6
midIdx: 5
midVal: 6
searchResultIdx: [5]■ 실습
Q >
리스트를 오름차순(.sort())으로 정렬한 후 7 을 검색하고 위치(인덱스)를 출력하자
- num = [4,10,22,5,0,17,7,11,9,61,88]
nums = [4,10,22,5,0,17,7,11,9,61,88]
print(f'nums: {nums}')
print('-'*25)
nums.sort()
print(f'nums: {nums}')
print('-'*25)
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]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData == midVal:
searchResultIdx = midIdx
break
print(f'searchResultIdx: [{searchResultIdx}]')▼
nums: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
-------------------------
nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
-------------------------
찾으려는 숫자 : 10
searchResultIdx: [5]
3. 순위
순위 란?
수의 크고 작음을 이용해서 수의 순서를 정하는 것
- 가장 큰 숫자는 '0'
- 가장 작은 숫자는 '끝자리'
# 순위 알고리즘 : 보통 rank 를 씀
# 20개를 랜덤 모듈을 이용해서 뽑는다.
import random
nums = random.sample(range(50,101), 20) #중복되지 않게 랜덤 : .sample() 이용
ranks = [0 for i in range(20)] # [0으로 값을 초기화 하고, i를 20번 반복하겠다]
print(f'nums: {nums}')
print(f'ranks: {ranks}')
print('-'*50)
for idx, num1 in enumerate(nums):
for num2 in nums:
if num1 < num2:
ranks[idx] += 1 # 기존 값(idx)에 1을 더함. 그래야 큰게 뒤로 한칸 밀림
print(f'nums : {nums}')
print(f'ranks : {ranks}')
print('-'*50)
# 보기 좋게 정렬
for idx, num in enumerate(nums):
print(f'num : {num} \t rank: {ranks[idx] +1 }')
▼
nums: [73, 71, 77, 79, 95, 66, 87, 60, 67, 92, 89, 81, 76, 84, 75, 86, 72, 63, 94, 97]
ranks: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
--------------------------------------------------
nums : [73, 71, 77, 79, 95, 66, 87, 60, 67, 92, 89, 81, 76, 84, 75, 86, 72, 63, 94, 97]
ranks : [13, 15, 10, 9, 1, 17, 5, 19, 16, 3, 4, 8, 11, 7, 12, 6, 14, 18, 2, 0]
--------------------------------------------------
num : 73 rank: 14
num : 71 rank: 16
num : 77 rank: 11
num : 79 rank: 10
num : 95 rank: 2
num : 66 rank: 18
num : 87 rank: 6
num : 60 rank: 20
num : 67 rank: 17
num : 92 rank: 4
num : 89 rank: 5
num : 81 rank: 9
num : 76 rank: 12
num : 84 rank: 8
num : 75 rank: 13
num : 86 rank: 7
num : 72 rank: 15
num : 63 rank: 19
num : 94 rank: 3
num : 97 rank: 1■ 실습
Q >
학급학생(20명)들의 중간고사와 기말고사 성적을 이용해 각각의 순위를 구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력 (시험 성적은 난수를 이용한다)
- class.py
import random
class RankDeviation: # RankDeviation : 편차
def __init__(self, mss, ess): # mss:중간고사 ess:기말고사
self.midStuScos = mss
self.endStuScos = ess
# ▼ 순위: 0으로 초기화, mss에 들어온 수의 갯수(길이)만큼 반복
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): # 순위 결정 ss:점수 rs:순위
for idx, sco1 in enumerate(ss): # ss에 대한 rs를 구해라
for sco2 in ss:
if sco1 < sco2: # 작을 때
rs[idx] += 1 # 인덱스가 1자리 씩 뒤로 밀림
# 중간고사 성적을 setRank로 던지면, "def setRank(self, ss, rs)"로 가서 알아서 중간 점수를 주는 문장
def setMidRank(self):
self.setRank(self.midStuScos, self.midRanks)
# 중간고사의 순위를 갖고 싶다, return
def getMidRank(self):
return self.midRanks
# 기말고사 성적을 setRank로 던지면, "def setRank(self, ss, rs)"로 가서 알아서 기말 점수를 주는 문장
def setEndRank(self):
self.setRank(self.endStuScos, self.endRanks)
# 기말고사의 순위를 갖고 싶다, return
def getEndRank(self):
return self.endRanks
# ▼편차 출력
def printRankDeviation(self):
# 중간(getMidRank), 기말(getEndRank)의 순위를 비교해서 올라갔는지, 내려갔는지를 비교
for idx, mRank in enumerate(self.midRanks):
deviation = mRank - self.endRanks[idx]
if deviation > 0:
deviation = '↑' + str(abs(deviation)) # abs: 절대값, 화살표가 문자이므로 str로 캐스팅
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}')(+)
- 실행문.py
import rankMod as rm
import random
midStuScos = random.sample(range(50, 101), 20) # 중간고사 성적 (50~100점 까지, 20명)
endStuScos = random.sample(range(50, 101), 20)
# 객체 생성 = 중간, 기말 점수 초기화
rd = rm.RankDeviation(midStuScos, endStuScos)
# setMidRank 호출
rd.setMidRank()
print(f'midStuScos: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')
# setEndRank 호출
rd.setEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')
# 중간고사 대비 기말고사의 편차 순위가 올라갔는지 출력
rd.printRankDeviation()▼
midStuScos: [62, 100, 79, 90, 95, 75, 64, 71, 88, 52, 57, 50, 55, 87, 72, 85, 86, 82, 83, 60]
mid_rank: [14, 0, 9, 2, 1, 10, 13, 12, 3, 18, 16, 19, 17, 4, 11, 6, 5, 8, 7, 15]
endStuScos: [89, 57, 87, 83, 98, 76, 52, 64, 96, 86, 61, 88, 58, 78, 80, 92, 69, 51, 67, 56]
end_rank: [3, 16, 5, 7, 0, 10, 18, 13, 1, 6, 14, 4, 15, 9, 8, 2, 11, 19, 12, 17]
mid_rank: 14 end_rank: 3 Deviation: ↑11
mid_rank: 0 end_rank: 16 Deviation: ↓16
mid_rank: 9 end_rank: 5 Deviation: ↑4
mid_rank: 2 end_rank: 7 Deviation: ↓5
mid_rank: 1 end_rank: 0 Deviation: ↑1
mid_rank: 10 end_rank: 10 Deviation: =0
mid_rank: 13 end_rank: 18 Deviation: ↓5
mid_rank: 12 end_rank: 13 Deviation: ↓1
mid_rank: 3 end_rank: 1 Deviation: ↑2
mid_rank: 18 end_rank: 6 Deviation: ↑12
mid_rank: 16 end_rank: 14 Deviation: ↑2
mid_rank: 19 end_rank: 4 Deviation: ↑15
mid_rank: 17 end_rank: 15 Deviation: ↑2
mid_rank: 4 end_rank: 9 Deviation: ↓5
mid_rank: 11 end_rank: 8 Deviation: ↑3
mid_rank: 6 end_rank: 2 Deviation: ↑4
mid_rank: 5 end_rank: 11 Deviation: ↓6
mid_rank: 8 end_rank: 19 Deviation: ↓11
mid_rank: 7 end_rank: 12 Deviation: ↓5
mid_rank: 15 end_rank: 17 Deviation: ↓2
4. 버블 정렬
버블 정렬 이란?
처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
nums = [10,2,7,21,0]
print(f'정렬 전 숫자 : {nums}')
length = len(nums) -1
for i in range(length):
for j in range(length - i ): # 하나 작은 곳 까지만 반복되야 해서 i 를 빼준다
if nums[j] > nums[j+1]: # ex. 10하고 7하고 비교할 때,
# temp = nums[j] # temp에 j 값을 넣어 놓고
# nums[j] = nums[j+1] #j에 다음 숫자를 넣어 자리를 바꿈
# nums[j+1] = temp # 다음 숫자에 temp를 담으면 결과적으로 자리가 완전히 바뀌게 됨
# ▼ 위 3개 문장이 아래 한문장으로 요약이 가능..!
nums[j], nums[j+1] = nums[j+1], nums[j]
print(nums)
print()
print(f'정렬 후 숫자 : {nums}')▼
정렬 전 숫자 : [10, 2, 7, 21, 0]
[2, 10, 7, 21, 0]
[2, 7, 10, 21, 0]
[2, 7, 10, 21, 0]
[2, 7, 10, 0, 21]
[2, 7, 10, 0, 21]
[2, 7, 10, 0, 21]
[2, 7, 0, 10, 21]
[2, 7, 0, 10, 21]
[2, 0, 7, 10, 21]
[0, 2, 7, 10, 21]
정렬 후 숫자 : [0, 2, 7, 10, 21]■ 실습
Q >
새학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워보자.
학생들의 키는 random 모듈을 이용해서 170-185사이로 생성한다.
copy(얕은/깊은)
개념 참고 url
- class.py
# 모듈 이용
import copy
def bubbleSort(ns, deepCopy = True):
# ns : nums(받을 숫자)의 약어
if deepCopy:
cns = copy.copy(ns)
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- 실행.py
import sortMod as sm # class 이용
import random as rd # 랜덤 모듈
students = [] # 배열 하나 만들어 놓고
for i in range(20): # 20명을 랜덤하게 뽑아서
students.append(rd.randint(170, 185)) # 키 정보 추가
print(f'students: {students}') # 어떤 값들이 있는지 출력해 봄
print(f'students length: {len(students)}')
# 얕은 복사
# sortedStudents = sm.bubbleSort(students, deepCopy=False)
# print(f'students: {students}')
# print(f'sortedStudents: {sortedStudents}')
# 깊은 복사
sortedStudents = sm.bubbleSort(students) # 오름차순 정렬
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')Daily Study Note
제로베이스 데이터 스쿨
비전공자의 데이터 공부법