그동안 열심히 배운 'Algorithm' 연습문제 21개를 풀어보자...!
검색 알고리즘
1. 선형 검색
- 모듈 : lineMod.py
#2.[2차] 작업
#사용자가 입력한 숫자를 발생시킨 10개의 정수(rNums) 중에서 찾는 모듈 제작
#3. 함수를 이용
#4. 매개변수 설정, ns: 외부네서 받을 숫자, sn: 찾으려는 숫자
def searchNumberByLineAlgorithm(ns, sn) :
searchResultIdx = -1 #5. 찾지 못했을 경우 -1 출력
print(f'Numbers : {ns}') #6. 찾으려는 대상이 되는 목록의 리스트 출력
print(f'Search Numbers : {sn}') #7. 찾으려는 타겟 출력
#[2차] end-----------------------------------------------------------------
#[4차] 작업
# ▼선형 검색이니까 숫자로 들어온 ns(리스트)를 모두 순환하면서 검색 비교하는 문장
n = 0
while True:
#▼검색 실패 경우
if n == len(ns): #9. 사용자가 입력한 숫자가 있는지 끝까지 검색을 했는데
print(('Search Fail')) #10. 검색이 안됐다.
break
# ▼검색 성공 경우
if ns[n] == sn: #11. 찾으려는 숫자와 동일한 경우
searchResultIdx = n #★★★ 12. 우리가 찾으려는 값 = searchResultIdx
print('Search SUCCESS')
print(f'Search result INDEX : {searchResultIdx}')
break
n += 1
return searchResultIdx # 13. 최종 반환- 실행 : ex.py
#1. [1차] 작업
import lineMod
import random
if __name__ == '__main__' :
rNums = random.sample(range(1,21), 10)
searchNum = int(input('숫자 입력 : '))
#[1차] end----------------------------------------------
#[3차] 작업
#8. def searchNumberByLineAlgorithm(ns, sn) : 를 이용할 실행 문장
#8. resultIdx로 반환 받는 문장
resultIdx = lineMod.searchNumberByLineAlgorithm(rNums, searchNum)
#[3차]end------------------------------------------------
#[5차] 작업
if resultIdx == -1: #14. 실패한 경우
print('No results found')
print(f'search result index : {resultIdx}') #15. 실패하면 -1이 넘어와야 하기 때문에, 출력 문장 설정
else:
print('>>> search result <<<')
print(f'search result Index : {resultIdx}')
print(f'search result number : {rNums[resultIdx]}')▼
숫자 입력 : 8
Numbers : [12, 10, 13, 7, 1, 14, 16, 11, 18, 17]
Search Numbers : 8
Search Fail
No results found
search result index : -12. 이진 검색
내가 찾으려는 데이터가 앞/뒤 어디에 있는지 반씩 잘라가면서 검색 범위를 좁혀나가는 알고리즘
⭐전제조건 : 데이터가 정렬되어 있어야 한다
- 모듈 : binary.py
def searchNumberByBinaryAlgorithm(ns, sn):
searchResultIdx = -1 #2. 찾으려는 숫자
#3. ▼ 이진검색 기본 세팅 문장
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}')
# 4. ▼ 이진검색 알고리즘 세팅
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
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- 실행 : ex.py
import binaryMod
#1. 전역 변수 이용
if __name__ == '__main__' :
nums = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
searchNum = int(input('input search number: '))
resultIdx = binaryMod.searchNumberByBinaryAlgorithm(nums, searchNum)
print(f'nums: {nums}')
if resultIdx == -1:
print('No results found.')
print(f'search result index: {resultIdx}')
else:
print('>>> Search Results <<<')
print(f'search result index: {resultIdx}')
print(f'search result number: {nums[resultIdx]}')▼
input search number: 8
staIdx: 0, endIdx: 17
midIdx: 8, midVal:13
-staIdx: 0, endIdx: 8
-midIdx: 4, midVal: 7
+staIdx: 4, endIdx: 8
+midIdx: 6, midVal: 10
-staIdx: 4, endIdx: 6
-midIdx: 5, midVal: 8
nums: [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
>>> Search Results <<<
search result index: 5
search result number: 8순위 알고리즘
순위 알고리즘으로 순위를 정한 다음에 순위에 따라서 다시 재 정렬하는 알고리즘 구현..!
⭐순위 알고리즘
: 개수 만큼 '0'으로 해준다음, 각각 다 비교(전체 아이템과 비교)해서 내가 얼마나 큰지, 큰 만큼 +1을 해서 새로운 리스트를 만듬
1. 순위
- 모듈 : rank.py
def rankAlgorithm(ns): # ns로 데이터를 받음
# ▼ 총 20개의 '0'을 가진 ranks 리스트를 만드는 문장
ranks = [0 for i in range(len(ns))]
for idx, n1 in enumerate(ns):
# 중첩 반복문 사용 이유 : 나(n1)와 n2 가 얼만큼 큰지 비교해야 하기 때문
for n2 in ns:
if n1 < n2:
ranks[idx] += 1 # 기존의 값에 +1 한다 = 반복하면서 순위가 정해짐(끝까지 1번씩 돔)
print(f'nums : {ns}')
print(f'ranks : {ranks}')
# ▼ 원본(nums)이 갖고 있는 아이템들을 재정렬 해주는 문장
for i, n in enumerate(ns):
print(f'nums : {n} \t rank : {ranks[i]+1}')
# 해당하는 숫자의 랭크 출력해 봄
# ranks[i]+1 : 0등은 없으니까, +1을 해줌으로써 1등 부터 시작되어 출력되게 만듬
# ▼ 정렬 하기 위해서 선언
sortedNums = [0 for n in range(len(ns))]
# 처음에는 0으로 초기화, ns의 길이만큼 0으로 초기화
# ranks의 인덱스, 순위 정보 가져 오기
for idx, rank in enumerate(ranks):
# rank 인덱스 자리에 ns의 인덱스를 넣어 줌
sortedNums[rank] = ns[idx]
# 새롭게 만들어진 리스트를 반환
return sortedNums- 실행 : ex.py
import rankMod
import random
if __name__ == '__main__' :
nums = random.sample(range(50,101), 20)
sNums = rankMod.rankAlgorithm(nums)
print(f'sNums : {sNums}')▼
nums : [81, 73, 80, 99, 63, 85, 77, 86, 57, 50, 64, 74, 89, 75, 95, 58, 56, 55, 93, 54]
ranks : [6, 11, 7, 0, 13, 5, 8, 4, 15, 19, 12, 10, 3, 9, 1, 14, 16, 17, 2, 18]
nums : 81 rank : 7
nums : 73 rank : 12
nums : 80 rank : 8
nums : 99 rank : 1
nums : 63 rank : 14
nums : 85 rank : 6
nums : 77 rank : 9
nums : 86 rank : 5
nums : 57 rank : 16
nums : 50 rank : 20
nums : 64 rank : 13
nums : 74 rank : 11
nums : 89 rank : 4
nums : 75 rank : 10
nums : 95 rank : 2
nums : 58 rank : 15
nums : 56 rank : 17
nums : 55 rank : 18
nums : 93 rank : 3
nums : 54 rank : 19
sNums : [99, 95, 93, 89, 86, 85, 81, 80, 77, 75, 74, 73, 64, 63, 58, 57, 56, 55, 54, 50]2. 순위
숫자에 대해서 나보다 큰 녀석이 있으면 +1을 해서 순위를 정하는 알고리즘
- 숫자는 숫자로
- str은 아스키코드 값을 이용
- 0순위 없게 만들 것 (1순위 부터 시작하게...!)
str(문장).isalpha()
앞파벳 인지 아닌지 확인해주는 코드
ord() 함수
아스키코드로 바꿔주는 함수
datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
print(f'datas: {datas}')
#1. 문자를 아스키코드 값으로 다 변환
ascIIDatas = [] #2. 변수 설정
for data in datas: #3. 반복을 하면서 '문자'를 발견하면 '아스키코드값'으로 변환
if str(data).isalpha(): #4. str().isalpha() : 알파벳 인지 아닌지 확인해주는 코드를 이용
ascIIDatas.append(ord(data)) #5. ord()함수 : 아스키코드로 바꾸는 함수
continue
ascIIDatas.append(data) #6. 숫자인 경우, 바로 추가
print(f'ascIIDatas: {ascIIDatas}')
#7. 순위 리스트 설정
#8. len(ascIIDatas) 개수 만큼 '0'으로 하는 리스트 생성 문장
ranks = [0 for i in range(len(ascIIDatas))]
for idx, data1 in enumerate(ascIIDatas):
for data2 in ascIIDatas:
if data1 < data2:
ranks[idx] += 1 #9. 나보다 크면 인덱스에 +1해서 다시 비교
print(f'ranks: {ranks}')
#▼각각의 데이터가 순위가 어떻게 되는지 출력
for i, d in enumerate(datas):
print(f'data:{d:>2} \t rank:{ranks[i] + 1}')
# ranks[i] + 1 : 0순위 없게, 1순위 부터 시작하게 설정▼
datas: [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
ascIIDatas: [32, 97, 122, 45, 71, 39, 50, 84, 116, 22, 31, 55, 115, 63, 59, 69]
ranks: [13, 3, 0, 11, 5, 12, 10, 4, 1, 15, 14, 9, 2, 7, 8, 6]
data:32 rank:14
data: a rank:4
data: z rank:1
data:45 rank:12
data: G rank:6
data:39 rank:13
data:50 rank:11
data: T rank:5
data: t rank:2
data:22 rank:16
data:31 rank:15
data:55 rank:10
data: s rank:3
data:63 rank:8
data:59 rank:9
data: E rank:7버블 정렬
⭐버블 정렬
: 데이터가 있을 때 첫번째 부터 하나씩 비교를 하다가 큰 숫자가 나오면 뒤로 밀어냄
오름/내림차순을 선택해서 정렬할 수 있도록 코딩할 것
- 모듈 : bubleMod.py
#1. 깊은 복사를 위한 copy 모듈 사용
import copy
def sortBybubleSortAlgorithm(ns, asc=True):
#ns(숫자)를 받음
c_ns = copy.copy(ns) #2. 새로운 copy(ns)를 만들어 줌, 원본 그래도 유지됨.
length = len(c_ns) - 1 #전체 길이 중 -1번째
for i in range(length): # 길이만큼 중첩반복문을 돌림
for j in range(length-i): # 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- 실행 : ex.py
import random
import bubleMod
if __name__ == '__main__':
#랜덤하게 숫자 정렬 출력
nums = random.sample(range(1, 21), 10)
print(f'not sorted nums: {nums}')
# 오름차순 정렬 출력 (by ASC : 오름차순)
result = bubleMod.sortBybubleSortAlgorithm(nums)
print(f'sorted nums by ASC: {result}')
# 내림차순 정렬 출력 (by DESC : 내림차순)
result = bubleMod.sortBybubleSortAlgorithm(nums, asc=False)
print(f'sorted nums by DESC: {result}')▼
not sorted nums: [8, 18, 20, 19, 6, 3, 15, 10, 13, 17]
sorted nums by ASC: [3, 6, 8, 10, 13, 15, 17, 18, 19, 20]
sorted nums by DESC: [20, 19, 18, 17, 15, 13, 10, 8, 6, 3]삽입 정렬
⭐삽입 정렬
이미 정렬되어 있는 데이터 만 보고 내가 들어갈 자리를 찾는 것
- 모듈 : insertMod.py
import copy
def sortInsertSortAlgorithm(ns, asc=True):
c_ns = copy.copy(ns) # copy 모듈의 ns를 copy해서 사용
for i1 in range(1, len(c_ns)): # 끝까지 가면서 비교
i2 = i1 -1
cNum = c_ns[i1] # cNum : 현재 숫자
# ▼ cNum(현재 숫자)가 들어갈 자리를 찾아야 함
if asc: # 오름차순
# i2 >= 0 = 0보다는 커야 한다, 그렇지 않으면 "out of range" 에러 발생
while c_ns[i2] > cNum and i2 >= 0:
c_ns[i2 +1] = c_ns[i2]
i2 -= 1
else: #내림차순
while c_ns[i2] < cNum and i2 >= 0:
c_ns[i2 +1] = c_ns[i2]
i2 -= 1
c_ns[i2 +1] = cNum
print(f'nums: {c_ns}')
return c_ns- 실행 : ex.py
import random
import insertMod
if __name__ == '__main__' :
nums = random.sample(range(1,20), 10)
#오름차순
print(f'not sorted nums:\n{nums}')
result = insertMod.sortInsertSortAlgorithm(nums)
print(f'sorted nums by ASC:\n{result}')
#내림차순
print(f'not sorted nums:\n{nums}')
result = insertMod.sortInsertSortAlgorithm(nums, asc=False)
print(f'sorted nums by DESC:\n{result}')▼
not sorted nums:
[19, 16, 13, 3, 10, 15, 18, 14, 5, 6]
sorted nums by ASC:
[3, 5, 6, 10, 13, 14, 15, 16, 18, 19]
not sorted nums:
[19, 16, 13, 3, 10, 15, 18, 14, 5, 6]
sorted nums by DESC:
[19, 18, 16, 15, 14, 13, 10, 6, 5, 3]선택 정렬
⭐선택 정렬
본인이 키값이 되어 작은 숫자와 자리를 바꾸며 정렬을 이루는 방식
- 모듈 : selectMod.py
import copy
def sortSelectSortAlgorithm(ns, asc=True):
# 깊은 복사한 ns를 c_ns라는 새로운 리스트로 만들어 준다
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- 실행 : ex.py
import random
import selectMod
if __name__ == '__main__' :
nums = random.sample(range(1,20),10)
print(f'not sorted nums:\n{nums}')
result = selectMod.sortSelectSortAlgorithm(nums)
print(f'sorted nums by ASC:\n{result}')
print(f'not sorted nums:\n{nums}')
result = selectMod.sortSelectSortAlgorithm(nums, asc=False)
print(f'sorted nums by DESC:\n{result}')▼
not sorted nums:
[6, 5, 18, 17, 1, 10, 7, 2, 8, 3]
sorted nums by ASC:
[3, 6, 5, 18, 17, 1, 10, 7, 2, 8]
not sorted nums:
[6, 5, 18, 17, 1, 10, 7, 2, 8, 3]
sorted nums by DESC:
[6, 5, 18, 17, 1, 10, 7, 2, 8, 3]병합 정렬
⭐병합 정렬
중간 값을 구해서, 반으로 나누고, 반을 또 나누고 계속 나눈 뒤 병합할 때 작은걸 앞, 큰걸 뒤로 하면서 한개씩, 두개씩, 세개씩 병합해서 최종 리스트를 만든다
- 모듈 : mergeMod.py
# 나 = mSort
def mSort(ns, asc=True):
if len(ns) < 2: # = 더이상 분할 할 값이 없을때 = 1개 남았다는 얘기
return ns
# ▼ ▼ 분할 단계 ▼ ▼
midIdx = len(ns) // 2
# ▼ 재귀함수 니까!!!!!!
# ns에서 0부서 시작해서 midIdx 까지한 값을 mSort(나)에 다시 넣어라
leftNums = mSort(ns[0 : midIdx], asc=asc)
# ns에서 midIdx 부터 끝까지(len(ns))한 값을 mSort(나)에 다시 넣어라
rightNums = mSort(ns[midIdx : len(ns)], asc=asc)
# ▼ ▼ 배열 단계 ▼ ▼
mergedNums = [] # 리스트 만들고
leftIdx = 0; rightIdx = 0 #초기화 해주고
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
# 왼쪽idx가 왼졲idx보다 작고, 오른쪽idx가 오른쪽idx보다 작을때까지 반복해라
# 오름차순 이라면
if asc:
if leftNums[leftIdx] < rightNums[rightIdx]: # 왼쪽이 오른쪾 보다 작다면
mergedNums.append(leftNums[leftIdx]) # 작은걸 왼쪽에 붙인다
leftIdx +=1
# 내림차순 이라면
else:
mergedNums.append(rightNums[rightIdx])
rightIdx +=1
else:
if leftNums[leftIdx] > rightNums[rightIdx]:
mergedNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergedNums.append(rightNums[rightIdx])
rightIdx += 1
# ▼ ▼ 병합 단계 ▼ ▼
mergedNums += leftNums[leftIdx : ]
mergedNums += rightNums[rightIdx : ]
# print(f'mergedNums: {mergedNums}')
return mergedNums- 실행 : ex.py
import random
import mergeMod
rNums = random.sample(range(1,101), 20)
print(f'not sorted rNums: {rNums}')
print(f'merge sorted rNums by ASC: {mergeMod.mSort(rNums)}')
print(f'merge sorted rNums by DESC: {mergeMod.mSort(rNums, asc=False)}')▼
not sorted rNums: [6, 69, 42, 72, 65, 35, 78, 37, 51, 38, 76, 100, 87, 52, 32, 2, 21, 15, 99, 18]
merge sorted rNums by ASC: [2, 6, 15, 18, 21, 32, 35, 37, 38, 42, 51, 52, 65, 69, 72, 76, 78, 87, 99, 100]
merge sorted rNums by DESC: [100, 99, 87, 78, 76, 72, 69, 65, 52, 51, 42, 38, 37, 35, 32, 21, 18, 15, 6, 2]최댓값
1
- 최댓값 구하기
- 최댓값의 중복 갯수 찾기
- 모듈 : maxMod.py
class MaxAlgorithm:
def __init__(self, ns):
self.nums = ns # 초기화된 데이터
self.maxNum = 0 # 최기화 데이터 중에서 가장 큰 값
self.maxNumCnt = 0 # 가장 큰 값의 갯수
# 최댓값 설정 함수
def setMaxNum(self):
self.maxNum = 0 # 최대값 0으로 초기화
for n in self.nums:
if self.maxNum < n : # 작다는 건 최대값이 아니란 얘기
self.maxNum = n # 그럼 더 큰 n을 최대값으로 설정
# 최대값 만 다시 뽑아보겟다 (반환)
def getMaxNum(self):
self.setMaxNum()
return self.maxNum
# 중복된 갯수 파악 함수
def setMaxNumCnt(self):
self.setMaxNum() #혹시 모르니까 한번 구해주고,
for n in self.nums: # 반복하다가
if self.maxNum == n : # 같으면 n이 최대란 얘기니까
self.maxNumCnt += 1 # +1 해줘라
#갯수를 가져다 쓸 수 있게 하는 함수
def getMaxNumCnt(self):
self.setMaxNumCnt()
return self.maxNumCnt- 실행 : ex.py
import random
import maxMod
if __name__ == '__main__':
nums = []
for n in range(30):
nums.append(random.randint(1, 50))
# 30개 난수 출력
print(f'nums:\n{nums}')
# 가져오고 싶은 것들 다 쓰기
ma = maxMod.MaxAlgorithm(nums)
print(f'max num: {ma.getMaxNum()}')
print(f'max num cnt: {ma.getMaxNumCnt()}')▼
nums:
[26, 6, 26, 15, 30, 48, 24, 41, 14, 18, 42, 45, 49, 15, 3, 19, 10, 9, 49, 41, 12, 5, 26, 15, 3, 47, 18, 13, 21, 10]
max num: 49
max num cnt: 22
- 모듈 : maxMod.py
# ▼ 평균 구하기
def getAvg(ns):
total = 0
for n in ns:
total += n
return total / len(ns)
# ▼ 최댓값 구하기
def getMax(ns):
maxN = ns[0] #maxN은 첫번쨰 인덱스[0]로 설정하겠다
for n in ns:
if maxN < n: # maxN이 작다? 최댓값이 아니다
maxN = n # n이 최댓값이 됨
return maxN
# ▼ 편차 구하기
def getDeviation(n1, n2):
return round(abs(n1-n2), 2) #abs 절대 편차.- ex.py
import maxMod
scores = [100, 64, 94, 66, 75, 58, 99, 76, 96, 74,
54, 73, 88, 70, 68, 50, 95, 89, 69, 98]
score_avg = maxMod.getAvg(scores)
score_max = maxMod.getMax(scores)
#편차 구하기
deviation = maxMod.getDeviation(score_avg, score_max)
print(f'score_avg: {score_avg}')
print(f'score_max: {score_max}')
print(f'deviation: {deviation}')▼
score_avg: 77.8
score_max: 100
deviation: 22.2제로베이스 데이터 스쿨
Daily study note
비전공자의 데이터 공부법