선형 검색
- 일렬로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다
- 인데스 0부터 9까지 순차적으로 검색 -> 검색 성공 or 검색 실패
datas = [3,2,5,7,9,1,2,4,3,8]
print(f'datas: {datas}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1 #존재하지 않는 인덱스를 주기 위함
n=0
while True:
if n == len(datas): #datas 길이 끝까지 갔는데 데이터가 없을 때
print('찾으려는 데이터가 존재하지 않습니다.')
break
elif datas[n] == searchData:
searchResultIdx = n
break
n += 1
print(f'searchResultIdx: {searchResultIdx}')
...
datas: [3, 2, 5, 7, 9, 1, 2, 4, 3, 8]
찾으려는 숫자 입력: 8
searchResultIdx: 9보초법
- 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다
- 인덱스 0부터 10까지 순차적으로 검색(10번째에 9 임의로 추가) -> 9 검색 -> 검색 성공: 마지막 이전에 9가 검색된 경우 / 검색 실패: 마지막에 9가 검색된 경우
datas = [4,7,10,2,4,7,0,2,7,3,9]
print(f'datas: {datas}')
searchData = 7
searchResultIdx = -1 #존재하지 않는 인덱스를 주기 위함
sumData = 0
n=0
while True:
if n == len(datas):
break
elif datas[n] == searchData:
print(f'7의 위치(인덱스): {n}')
sumData += 1
n += 1
print(f'7의 개수: {sumData}')
...
datas: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
7의 위치(인덱스): 1
7의 위치(인덱스): 5
7의 위치(인덱스): 8
7의 개수: 3<파이썬 실습>
- datas에서 7의 위치와 몇 개가 존재하는지 출력하는 프로그램을 생성해보세요.
datas = [4,7,10,2,4,7,0,2,7,3,9]
searchData = int(input('검색할 숫자 입력: '))
datas.append(searchData) #보초법으로 마지막에 검색할 숫자 넣기
searchResultIdx = []
n=0
while True:
if datas[n] == searchData:
if n != len(datas) - 1: #보초법에 의해 추가된 숫자라면 제외
searchResultIdx.append(n)
else:
break
n += 1
print(f'datas: {datas}')
print(f'searchResultIdx: {searchResultIdx}')
print(f'검색할 숫자 {searchData}의 총 개수: {len(searchResultIdx)}')
...
검색할 숫자 입력: 7
datas: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
searchResultIdx: [1, 5, 8]
검색할 숫자 7의 총 개수: 3- 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈으르 다음 요건에 따라 만들어보자.
def searchNumberByLineAlgorithm(ns, sn):
searchResultIdx = -1
print(f'Numbers: {ns}')
print(f'Search Number: {sn}')
n=0
while True:
if n == len(ns): #찾다가 끝까지 온 것이면 Fail
print('Search Fail')
break
if ns[n] == sn:
searchResultIdx = n
print('Search Success')
print(f'Search result Index: {searchResultIdx}')
break
n += 1
return searchResultIdx
------실행파일------
import lineMod
import random
if __name__ == '__main__':
rNums = random.sample(range(1,21), 10)
searchNum = int(input('input search number: '))
resultIdx = lineMod.searchNumberByLineAlgorithm(rNums, searchNum)
if resultIdx == -1:
print('No result found')
print(f'resultIdx: {resultIdx}')
else:
print('>>> Search Results <<<')
print(f'resultIdx: {resultIdx}')
print(f'result number: {rNums[resultIdx]}')
....
input search number: 8
Numbers: [9, 14, 12, 13, 18, 8, 6, 10, 17, 2]
Search Number: 8
Search Success
Search result Index: 5
>>> Search Results <<<
resultIdx: 5
result number: 8이진 검색
- 이진 검색: 정렬되어 있는 자료 구조에서 중앙값과의 크고 작음을 이용해서 검색 범위를 좁혀나가면서 데이터를 검색한다.
- 정렬되어 있어야 하기 때문에 sort() 함수 활용
datas = [1,2,3,4,5,6,7,8,9,10,11]
startIdx = 0
endIdx = len(datas) - 1
midIdx = (startIdx+endIdx) // 2 #시작+끝 인덱스 나누기 2의 몫
midVal = datas[midIdx]
searchData = int(input('검색할 숫자 입력: '))
searchDataIdx = -1
while searchData in datas:
if searchData == midVal:
searchDataIdx = midIdx
break
elif searchData == datas[len(datas) - 1]:
searchDataIdx = len(datas) - 1
break
elif searchData > midVal:
startIdx = midIdx
midIdx = (startIdx+endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData < midVal:
endIdx = midVal
midIdx = (startIdx+endIdx) // 2
midVal = datas[midVal]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
print(f'{searchData}의 위치 {searchDataIdx}')
...
검색할 숫자 입력: 10
midIdx: 7
midVal: 8
midIdx: 8
midVal: 9
midIdx: 9
midVal: 10
10의 위치 9순위
- 순위: 수의 크고 작음을 이용해서 수의 순위를 정하는 것
< 파이썬 실습> - 학급 학생(20명)들의 중간고사와 기말고사 성적을 이용해서 각각의 순위를
구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력하는 프로그램을
만들어 보자.(시험 성적은 난수를 이용한다.)
class RandDeviation:
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(ess))]
self.randDeviation = [0 for i in range(len(mss))]
def setRank(self, ss, rs):
for idx, score1 in enumerate(ss):
for score2 in ss:
if score1 < score2:
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'midRank: {mRank}, \t endRank: {self.endRanks[idx]}, \t Deviation: {deviation}')
------ 실습 파일 ------
import rankMod
import random
midStuScos = random.sample(range(50, 101), 20)
endStuScos = random.sample(range(50, 101), 20)
rd = rankMod.RandDeviation(midStuScos, endStuScos)
rd.setMidRank()
print(f'midStuScos: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')
rd.setEndRank()
rd.getEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')
rd.printRankDeviation()
...
midStuScos: [98, 100, 94, 84, 93, 75, 77, 55, 80, 51, 56, 73, 52, 68, 65, 57, 60, 83, 66, 79]
mid_rank: [1, 0, 2, 4, 3, 9, 8, 17, 6, 19, 16, 10, 18, 11, 13, 15, 14, 5, 12, 7]
endStuScos: [89, 53, 74, 77, 72, 54, 71, 85, 98, 62, 68, 86, 58, 94, 76, 92, 52, 57, 91, 59]
end_rank: [4, 18, 9, 7, 10, 17, 11, 6, 0, 13, 12, 5, 15, 1, 8, 2, 19, 16, 3, 14]
midRank: 1, endRank: 4, Deviation: ↓3
midRank: 0, endRank: 18, Deviation: ↓18
midRank: 2, endRank: 9, Deviation: ↓7
midRank: 4, endRank: 7, Deviation: ↓3
midRank: 3, endRank: 10, Deviation: ↓7
midRank: 9, endRank: 17, Deviation: ↓8
midRank: 8, endRank: 11, Deviation: ↓3
midRank: 17, endRank: 6, Deviation: ↑11
midRank: 6, endRank: 0, Deviation: ↑6
midRank: 19, endRank: 13, Deviation: ↑6
midRank: 16, endRank: 12, Deviation: ↑4
midRank: 10, endRank: 5, Deviation: ↑5
midRank: 18, endRank: 15, Deviation: ↑3
midRank: 11, endRank: 1, Deviation: ↑10
midRank: 13, endRank: 8, Deviation: ↑5
midRank: 15, endRank: 2, Deviation: ↑13
midRank: 14, endRank: 19, Deviation: ↓5
midRank: 5, endRank: 16, Deviation: ↓11
midRank: 12, endRank: 3, Deviation: ↑9
midRank: 7, endRank: 14, Deviation: ↓7 - 알파벳 문자들과 정수들에 대한 순위를 정하는 프로그램을 순위 알고리즘을 이용해서 만들어 보자. 단, 알파벳은 아스키코드 값을 이용한다.
[32, ‘a’, ‘z’, 45, ‘G’, 39, 50, ‘T’, ‘t’, 22, 31, 55, ‘s’, 63, 59, ‘E’]
datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
print(f'datas: {datas}')
ranks = [0 for i in range(len(datas))]
ascIIDatas = []
for data in datas:
if str(data).isalpha(): #isalpha: 알파벳이냐 아니냐! 내가 썼던 코드: type(datas[i]) == type('data')
ascIIDatas.append(ord(data))
else:
ascIIDatas.append(data)
print(f'ascIIDatas: {ascIIDatas}')
for idx, data1 in enumerate(ascIIDatas):
for data2 in ascIIDatas:
if data1 < data2:
ranks[idx] += 1
print(f'ranks: {ranks}')
for i, d in enumerate(ascIIDatas):
print(f'data: {d:>2} \t rank: {(ranks[i]+1):>2}') #오른쪽정렬: ':>2'
.....
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: 97 rank: 4
data: 122 rank: 1
data: 45 rank: 12
data: 71 rank: 6
data: 39 rank: 13
data: 50 rank: 11
data: 84 rank: 5
data: 116 rank: 2
data: 22 rank: 16
data: 31 rank: 15
data: 55 rank: 10
data: 115 rank: 3
data: 63 rank: 8
data: 59 rank: 9
data: 69 rank: 7버블 정렬
- 버블 정렬: 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
def bubbleSort(ns, deepCopy=True):
if deepCopy: #깊은 복사
cns = copy.copy(ns) #ns를 copy해서 cns라는 완전히 새로운 변수를 생성 => students는 그대로 유지 가능
else:
cns = ns #얕은 복사
length = len(cns) - 1 #버블 정렬 시, 처음의 숫자를 마지막 앞의 숫자까지만 비교하면 되기 때문에 -1을 해줌.
for i in range(length):
for j in range(length-i):
if cns[j] > cns[j+1]: #비교하려는 ns[j]의 값 보다 그 다음의 값인 ns[j+1]이 더 크다면
cns[j], cns[j+1] = cns[j+1], cns[j] #비교했던 ns[j]와 그 다음의 순서인 ns[j+1]과의 값을 바꾸어 줌.
return cns
-----실행 파일-----
import random
import copy
students = []
for i in range(21):
students.append(random.randint(170,185))
print(f'students: {students}')
sortedStudents = bubbleSort(students, deepCopy=True)
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')
...
students: [172, 177, 183, 171, 177, 175, 184, 173, 178, 181, 183, 170, 173, 180, 179, 172, 182, 178, 175, 180, 178]
students: [172, 177, 183, 171, 177, 175, 184, 173, 178, 181, 183, 170, 173, 180, 179, 172, 182, 178, 175, 180, 178]
# 깊은 복사했기 때문에 students는 변형되지 않고 유지됨
sortedStudents: [170, 171, 172, 172, 173, 173, 175, 175, 177, 177, 178, 178, 178, 179, 180, 180, 181, 182, 183, 183, 184]삽입 정렬
- 삽입 정렬: 정렬되어 있는 자료 배열과 비교해서 정렬 위치를 찾고 값을 넣어줌.
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)): # 2번째의 수부터 시작해서, 이전번째의 수가 현재의 수보다 크면 앞으로 이동 => range 1부터 시작
i2 = i1 - 1 # 이전번째를 i2로 지정
cNum = self.nums[i1] # 현재 기준이 되는 숫자
if self.isAsc: #오름차순
while self.nums[i2] > cNum and i2 >= 0: # 이전번째의 인덱스가 0보다 작으면 안됨.
self.nums[i2 + 1] = self.nums[i2]
i2 -= 1
else: #내림차순
while self.nums[i2] < cNum and i2 >= 0: # 이전번째의 인덱스가 0보다 작으면 안됨.
self.nums[i2 + 1] = self.nums[i2]
i2 -= 1
self.nums[i2 + 1] = cNum
def getSortedNumbers(self):
return self.nums
def getMinNumbers(self):
if self.isAsc:
return self.nums[0]
else:
return self.nums[len(self.nums)-1]
def getMaxNumbers(self):
if self.isAsc:
return self.nums[len(self.nums)-1]
else:
return self.nums[0]
-----실행 파일-----
import insertMod
import random
import copy
nums = random.sample(range(1, 1001), 10)
print(f'numbers: {nums}')
sn = insertMod.SortNumbers(nums, asc=True)
# 오름차순
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by asc: {sortedNumbers}')
# 내림차순
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by desc: {sortedNumbers}')
# 최솟값과 최댓값
print(f'min: {sn.getMinNumbers()}')
print(f'max: {sn.getMaxNumbers()}')
.....
numbers: [809, 715, 295, 586, 414, 2, 529, 638, 872, 510]
sortedNumbers by asc: [2, 295, 414, 510, 529, 586, 638, 715, 809, 872]
sortedNumbers by desc: [872, 809, 715, 638, 586, 529, 510, 414, 295, 2]
min: 2
max: 872선택 정렬
- 선택 정렬: 최소값을 찾아 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘
- 현재 값을 기준으로 현재 값을 포함한 다음의 숫자들 중 최솟값을 가장 맨 앞으로 교체
- 현재 값을 기준으로 현재 값을 포함한 다음의 숫자들 중 최솟값을 가장 맨 앞으로 교체
- 실습: 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다.
def sortNumber(num, asc=True):
if asc: #오름차순
for i in range(len(num)-1):
minIdx = i
for j in range(i+1, len(num)):
if num[minIdx] > num[j]:
minIdx = j
num[i], num[minIdx] = num[minIdx], num[i]
else: #내림차순
for i in range(len(num) - 1):
minIdx = i
for j in range(i + 1, len(num)):
if num[minIdx] < num[j]:
minIdx = j
num[i], num[minIdx] = num[minIdx], num[i]
return num
------ 실행 파일 -------
import selectSortMod as sm
import random
import copy
num = random.sample(range(50,101), 20)
print(f'num: {num}')
print(f'result ASC: {sm.sortNumber(copy.deepcopy(num))}')
#깊은 복사했기 때문에 원본이 정렬되지 않고 그대로 유지(훼손되지 않았음)
print(f'num: {num}')
print(f'result DESC: {sm.sortNumber(copy.deepcopy(num), asc=False)}')
.....
num: [59, 79, 66, 53, 81, 58, 91, 97, 68, 92, 75, 89, 50, 52, 80, 74, 71, 70, 72, 78]
result ASC: [50, 52, 53, 58, 59, 66, 68, 70, 71, 72, 74, 75, 78, 79, 80, 81, 89, 91, 92, 97]
num: [59, 79, 66, 53, 81, 58, 91, 97, 68, 92, 75, 89, 50, 52, 80, 74, 71, 70, 72, 78]
result DESC: [97, 92, 91, 89, 81, 80, 79, 78, 75, 74, 72, 71, 70, 68, 66, 59, 58, 53, 52, 50]최댓값 알고리즘
- 자료 구조에서 가장 큰 값을 찾는다
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])
maxVal = ma.getMaxNum()
print(f'최댓값: {maxVal}')
......
최댓값: 20최솟값 알고리즘
- 자료 구조에서 가장 작은 값을 찾는다
class MinAlgorithm:
def __init__(self, ns):
self.nums = ns
self.minNum = 0
def getMinNum(self):
self.minNum = self.nums[0]
for n in self.nums:
if self.minNum > n:
self.minNum = n
return self.minNum
ma = MinAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
minVal = ma.getMinNum()
print(f'최솟값: {minVal}')
.....
최솟값: -11최빈값 알고리즘
- 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다.
- 데이터를 인덱스로 변환. 즉, nums의 값이 위치(=인덱스)인 indexes를 만들고 nums에 값이 존재할 때마다 1씩 더해주는 방식
- 실습: 최빈값 알고리즘을 이용해서 학생 100명의 점수 분포를 다음과 같이 나타내 보자.
class MaxAlgorithm:
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
self.maxNumIdx = 0
def getMaxNumAndIdx(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 getMaxNumIdx(self):
return self.maxNumIdx
----- 실행 파일 ------
import random
import max
scores = []
for i in range(11):
rn = random.randint(71, 101)
# if rn != 100:
rn = rn - (rn % 5)
scores.append(rn)
#랜덤으로 뽑은 수가 100점만 아니면, 5로 나눈 나머지를 빼서 단위 5로 맞추어줌.
print(f'scores: {scores}')
maxAlo = max.MaxAlgorithm(scores)
maxAlo.getMaxNumAndIdx()
maxNum = maxAlo.getMaxNum()
print(f'maxNum: {maxNum}')
maxNumIdx = maxAlo.getMaxNumIdx()
#인덱스 리스트 생성
indexes = [0 for i in range(maxNum+1)] #maxNum+1을 해줘야 scores와 길이가 맞는다
print(f'indexes: {indexes}')
print(len(indexes))
#인덱스 리스트에 빈도 저장
for n in scores:
indexes[n] = indexes[n] + 1
print(f'indexes: {indexes}')
n=1
while True:
maxAlo = max.MaxAlgorithm(indexes)
maxAlo.getMaxNumAndIdx()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
if maxNum == 0:
break
print(f'{n}. {maxNumIdx} 빈도수: {maxNum}\t', end='')
print('+'*maxNum)
indexes[maxNumIdx] = 0
#가장 빈도수가 높은 값을 0으로 바꾸어서 최빈값을 초기화 -> 다음 최빈값을 다음번째에 출력할 수 있음
n += 1
......
scores: [85, 80, 80, 70, 80, 85, 75, 80, 75, 80, 80]
maxNum: 85
indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
86
indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 6, 0, 0, 0, 0, 2]
1. 80 빈도수: 6 ++++++
2. 75 빈도수: 2 ++
3. 85 빈도수: 2 ++
4. 70 빈도수: 1 +근삿값 알고리즘
- 근삿값: 특정 값에 가장 가까운 값
def getNearNum(avgNum): #near.py로 저장
basicScores = [95, 85, 75, 65, 55]
nearNum = 0
minNum = 100
for n in basicScores:
absNum = abs(n-avgNum)
#(기준값-평균값)인 차이가 가장 작은 수를 nearNum으로 추출
if absNum < minNum:
minNum = absNum
nearNum = n
if nearNum == 95:
return 'A'
elif nearNum == 85:
return 'B'
elif nearNum == 75:
return 'C'
elif nearNum == 65:
return 'D'
elif nearNum <= 55:
return 'F'
------실행 파일-----
import near
import random
scores = random.sample(range(0,101),5)
print(f'scores: {scores}')
totalScore = sum(scores)
print(f'totalScore: {totalScore}')
avgScore = totalScore / len(scores)
print(f'avgScore: {avgScore}')
grade = near.getNearNum(avgScore)
print(f'grade: {grade}')
.....
scores: [80, 88, 79, 89, 78]
totalScore: 414
avgScore: 82.8
grade: B평균 알고리즘
- 평균: 여러 수나 양의 중간값을 갖는 수를 평균이라고 한다.
def getAverageScore(scores):
totalScore = 0
for n in scores:
totalScore += n
avgScore = totalScore / len(scores)
return avgScore
scores = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
print(f'averageScore: {getAverageScore(scores)}')
.....
averageScore: 8.39재귀 알고리즘
- 재귀: 나 자신을 다시 호출하는 것
<실습> - 팩토리얼 함수 구현하기
def factorial(num):
if num > 0:
return num * factorial(num-1)
else:
return 1
print(f'factorial(10): {factorial(5)}')
.....
factorial(10): 120- 유클리드 호제법으로 최대 공약수 계산하기
- 유클리드 호제법: 두 자연수 n1, n2에 대하여(이때 n1>n2), n1을 n2로 나눈 나머지를 r이라고 할 때, n1과 n2의 최대 공약수는 n2와 r의 최대공약수와 같다.
- 96 / 40의 나머지: 16 -> 40 / 16의 나머지: 8 -> 16/8 == 0이기 때문에, n2인 8이 96과 40의 최대공약수
- 유클리드 호제법: 두 자연수 n1, n2에 대하여(이때 n1>n2), n1을 n2로 나눈 나머지를 r이라고 할 때, n1과 n2의 최대 공약수는 n2와 r의 최대공약수와 같다.
def gcd(n1,n2):
if n1 % n2 == 0: #나누어떨어지는 수이면 최대공약수는 더 작은 수인 n2
return n2
else:
return gcd(n2, n1 % n2)
print(f'gcd(82, 32): {gcd(82, 32)}')
print(f'gcd(96,40): {gcd(96, 40)}')
.....
gcd(82, 32): 2
gcd(96,40): 8- 사용자가 정수 두개를 입력하면 작은 정수와 큰 정수 사이의 모든 정수의 합을 구하는 프로그램을 재귀 알고리즘을 이용해서 만들어보자.
class NumsSum:
def __init__(self, n1, n2):
self.bigNum = 0
self.smallNum = 0
self.setN1N2(n1, n2)
def setN1N2(self, n1, n2):
self.bigNum = n1
self.smallNum = n2
if n1 < n2:
self.bigNum = n2
self.smallNum = n1
def addNum(self, n):
if n <= 1:
return n
return n + self.addNum(n - 1)
def sumBetweenNums(self):
return self.addNum(self.bigNum - 1) - self.addNum(self.smallNum)
-----실행 파일-----
import mod
num1 = int(input(f'input number1: '))
num2 = int(input(f'input number2: '))
ns = mod.NumsSum(num1, num2)
result = ns.sumBetweenNums()
print(f'result: {result}')
.....
input number1: 10
input number2: 3
result: 39하노이의 탑
# 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')
else:
# (discCnt-1)개들을 경유 기둥으로 이동
moveDisc(discCnt-1, fromBar, viaBar, toBar)
# discCnt를 목적 기둥으로 이동
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')
# (discCnt-1)개들을 도착 기둥으로 이동
moveDisc(discCnt-1, viaBar, toBar, fromBar)
moveDisc(3, 1, 3, 2)
....
1disc: 1에서 3(으)로 이동!
2disc: 1에서 2(으)로 이동!
1disc: 3에서 2(으)로 이동!
3disc: 1에서 3(으)로 이동!
1disc: 2에서 1(으)로 이동!
2disc: 2에서 3(으)로 이동!
1disc: 1에서 3(으)로 이동!병합 정렬
- 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
- 합칠 때 각 수의 크고 작음을 비교해서 작은 수를 왼쪽으로 자리바꿈하면서 병렬 반복하여 정렬 진행
<실습>
- 합칠 때 각 수의 크고 작음을 비교해서 작은 수를 왼쪽으로 자리바꿈하면서 병렬 반복하여 정렬 진행
- 1~100 정수 중 10개의 난수 추출한 후, 병합 정렬 활용해 내림차순/오름차순으로 정렬하라.
def mSort(ns, ACS = True):
if len(ns) < 2:
return ns
#분할
midIdx = len(ns) // 2 #중간값
leftNums = mSort(ns[0:midIdx], ACS=ACS) #처음부터 중간값까지
# 이때 ACS=ACS를 넣어주어야, ACS=False 로 처음에 넣었던 값이 재귀로 돌아갈 때도 반영될 수 있음!
rightNums = mSort(ns[midIdx:len(ns)], ACS=ACS) #중간값부터 끝까지
#병합
mergeNums = []
leftIdx = 0; rightIdx = 0
if ACS:
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
# 자리 바꿈
if leftNums[leftIdx] < rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
else:
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
# 자리 바꿈
if leftNums[leftIdx] > rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
mergeNums = mergeNums + leftNums[leftIdx:]
mergeNums = mergeNums + rightNums[rightIdx:]
return mergeNums
import random
import copy
ns = random.sample(range(1,101), 10)
nums = copy.deepcopy(ns)
print(f'not sorted nums: {ns}')
print(f'mSort(nums) by ASC: {mSort(nums, ACS=True)}')
print(f'mSort(nums) by DESC: {mSort(nums, ACS=False)}')
.....
not sorted nums: [41, 73, 56, 59, 45, 51, 27, 16, 35, 19]
mSort(nums) by ASC: [16, 19, 27, 35, 41, 45, 51, 56, 59, 73]
mSort(nums) by DESC: [73, 59, 56, 51, 45, 41, 35, 27, 19, 16]퀵 정렬
- 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
<실습> - 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
def qSort(ns, acs=True):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
midVal = ns[midIdx] #기준값
smallNums = [] #왼쪽은 기준값보다 작은 수
sameNums = [] # 기준값과 동일한 값
bigNums = [] #오른쪽은 기준값보다 큰 수
for n in ns:
if n < midVal:
smallNums.append(n)
elif n == midVal:
sameNums.append(n)
else:
bigNums.append(n)
if acs:
return qSort(smallNums) + sameNums + qSort(bigNums)
else:
return qSort(bigNums, acs=acs) + sameNums + qSort(smallNums, acs=acs)
import random
import copy
ns = random.sample(range(1,101), 10)
nums = copy.deepcopy(ns)
print(f'not sorted nums: {ns}')
print(f'qSort(nums) by ASC: {qSort(nums, acs=True)}')
print(f'qSort(nums) by DESC: {qSort(nums, acs=False)}')
.....
not sorted nums: [40, 46, 86, 94, 49, 13, 26, 7, 52, 97]
qSort(nums) by ASC: [7, 13, 26, 40, 46, 49, 52, 86, 94, 97]
qSort(nums) by DESC: [97, 94, 86, 52, 49, 46, 40, 26, 13, 7]