선형검색
선형검색이란?
- 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는것.
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}')
-
보초법
- 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화 한다.
- 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화 한다.
선형검색(실습)
- 리스트에서 가장 앞에 있는 숫자 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:
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('not search index')
else:
print(f'search index : {searchResultIdx}')
- 리스트에서 숫자 7을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자.
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('input search number : '))
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
print(f'nums : {nums}')
print(f'nums length : {len(nums)}')
searchnums = searchNum(nums)
print(f'searchResultIdxs : {searchnums}')
print(f'searchResultIdxsCnt : {len(searchnums)}')
이진검색
이진검색이란?
- 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
- 전체 데이터의 중간값과 찾을려는 숫자를 비교해서 점차적으로 검색 범위를 좁혀나가는 방법
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('search data : '))
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}')
이진검색(실습)
- 리스트를 오름차순으로 정렬한 후 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]
n = 0
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}')
순위
순위란?
- 수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다.
import random
nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]
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 idx, num in enumerate(nums):
print(f'num : {num} \t rank : {ranks[idx] + 1}')
순위(실습)
- 학급 학생(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(ess))]
self.rankDeviation = [0 for i in range(len(ess))]
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'midStuScos : {midStuScos}')
print(f'mid_ranks : {rd.getMidRank()}')
rd.setEndRank()
print(f'midStuScos : {endStuScos}')
print(f'end_ranks : {rd.getEndRank()}')
rd.printRankDeviation()
버블정렬
버블정렬이란?
- 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰숫자를 가장 끝으로 옮기는 알고리즘이다.
nums = [10, 2, 7, 21, 0]
print(f'nums : {nums}')
length = len(nums) -1
for i in range(length):
for j in range(length - i):
if nums[j] > nums[j+1]:
# temp = nums[j]
# nums[j] = nums[j+1]
# nums[j + 1] = temp
nums[j], nums[j+1] = nums[j+1], nums[j]
# nums[j], nums[j+1]여기에 nums[j+1]와 nums[j]를 각각 초기화 해주는 것
print(f'nums : {nums}')
print()
print(f'sorted nums : {nums}')
버블정렬(실습)
- 새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185 사이로 생성한다.
# 실행하는 함수 모듈
import copy
def bubbleSort(ns, deepCopy = True):
if deepCopy:
cns = copy.copy(ns)
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]:
cns[j], cns[j + 1] = cns[j + 1], cns[j]
return cns
# 실행문
import random as rd
import sortMod as sm
students = []
for i in range(20):
students.append(rd.randint(170,185))
print(f'students : {students}')
srtedStudents = sm.bubbleSort(students, deepCopy=False)
# 깊은복사 deepCopy=False
# 얕은복사 deepCopy=True
print(f'students : {students}')
print(f'srtedStudents : {srtedStudents}')- 깊은복사용
- 얕은복사용
삽입정렬
삽입정렬이란?
- 정렬되어 있는 자료 배열과 비교해서, 정렬위치를 찾는다.
nums=[5, 10, 2, 1, 0]
# 오름차순
for i1 in range(1, len(nums)):
i2 = i1 - 1
cNum = nums[i1]
while nums[i2] > cNum and i2 >= 0:
# 오름차순 >, 내림차순 <
nums[i2 + 1] = nums[i2]
i2 -= 1
nums[i2 + 1] = cNum
print(f'nums : {nums}')
print()
# 내림차순
nums=[0, 5, 2, 10, 1]
for i1 in range(1, len(nums)):
i2 = i1 - 1
cNum = nums[i1]
while nums[i2] < cNum and i2 >= 0: # 오름차순 >, 내림차순 <
nums[i2 + 1] = nums[i2]
i2 -= 1
nums[i2 + 1] = cNum
print(f'nums : {nums}')
삽입정렬(실습)
- 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자.
# 모듈
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)):
i2 = i1 - 1
cNum = self.nums[i1]
if self.isAsc: # 오름차순 True, 내림차순 False
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 getMindNumber(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 sortMod as sm
nums = random.sample(range(1, 1000), 100)
print(f'not sorted numbers : {nums}')
# 객체 생성
sn = sm.SortNumbers(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 DESC : {sortedNumbers}')
# min & max
print(f'min : {sn.getMindNumber()}')
print(f'max : {sn.getMaxNumber()}')
선택정렬
선택정렬이란?
- 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
nums = [4, 2, 5, 1, 3]
print(f'nums : {nums}')
for i in range(len(nums)-1):
minIdx = i
for j in range(i+1, len(nums)):
if nums[minIdx] > nums[j]:
minIdx = j
# 방법1
# tempNum = nums[i]
# nums[i] = nums[minIdx]
# nums[minIdx] = tempNum
# 방법2
nums[i], nums[minIdx] = nums[minIdx], nums[i]
print(f'nums : {nums}') # 순서확인용
print(f'final nums : {nums}')
선택정렬(실습)
- 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험점수는 50부터 100까지로 한다.
# 모듈
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 sortMod as sm
import copy
scores = random.sample(range(5, 100), 20)
print(f'scores : {scores}')
result = sm.sortNumber(copy.copy(scores)) # 복사를해서 원래 데이터를 회손하는걸 방지할 수 있다.
print(f'result : {result}') # 오름차순
print()
print(f'scores : {scores}')
result = sm.sortNumber(copy.copy(scores), asc=False)
print(f'result : {result}') # 내림차순
최댓값
최댓값이란?
- 자료구조에서 가장 큰 값을 찾는다.
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, -2, 5, 7, 10, 0, 8, 20, -11])
maxNum = ma.getMaxNum()
print(f'maxNum : {maxNum}')
최댓값(실습)
- 리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 만들어보자.
class MaxAlgorithm:
def __init__(self, cs):
self.char = cs
self.maxChar = 0
def getMaxChar(self):
self.maxChar = self.char[0]
for c in self.char:
if ord(self.maxChar) < ord(c):
# 문자열을 아스키코드로 반환해주는 함수로 ord()가있다.
# ord()로 아스키코드로 반환한후 비교하면된다.
self.maxChar = c
return self.maxChar
char = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = MaxAlgorithm(char)
maxChar = mc.getMaxChar()
print(f'maxChar : {maxChar}')
최솟값
최솟값이란?
- 자료구조에서 가장 작은 값을 찾는다.
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, 6, 10, 0, 8, 20, -11])
minNum = ma.getMinNum()
print(f'minNum : {minNum}')
최솟값(실습)
- 리스트에서 아스키코드가 가장 작은 값을 찾는 알고리즘을 만들어보자.
class MinAlgorithm:
def __init__(self, cs):
self.chas = cs
self.minChar = 0
def getMinChar(self):
self.minChar = self.chas[0]
for c in self.chas:
if ord(self.minChar) > ord(c):
self.minChar = c
return self.minChar
ma = MinAlgorithm(['c', 'x', 'Q', 'A', 'e', 'P', 'p'])
minChar = ma.getMinChar()
print(f'minChar : {minChar}')
최빈값
최빈값이란?
- 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다.
class MaxAlgorithm:
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
self.maxNumIdx = 0
def setMaxIdxAcdNum(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
nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlo = MaxAlgorithm(nums)
maxAlo.setMaxIdxAcdNum()
maxNum = maxAlo.getMaxNum()
print(f'maxNum : {maxNum}')
indexes = [0 for i in range(maxNum + 1)]
print(f'indexes : {indexes}')
print(f'indexes length : {len(indexes)}')
for n in nums:
indexes[n] = indexes[n] + 1
print(f'indexes : {indexes}')
maxAlo = MaxAlgorithm(indexes)
maxAlo.setMaxIdxAcdNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
print(f'maxNum : {maxNum}')
print(f'maxNumIdx : {maxNumIdx}')
print(f'즉, {maxNumIdx}의 빈도수가 {maxNum}로 가장 높다.')
최빈값(실습)
- 최빈값 알고리즘을 이용해서 학생 100명의 점수 분포를 다음과 같이 나타내 보자.
# 최대값 모듈
class MaxAlgorithm:
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
self.maxNumIdx = 0
def setMaxNumIdxAndNum(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 maxScore as ms
import random
score = []
for i in range(100):
rn = random.randint(71, 100)
if rn != 100: rn = rn - (rn % 5)
# rn이 100점이 아니면 5만위 점수로 재설정을 해준다.
score.append(rn)
# print(f'score : {score}')
# print(f'score length : {len(score)}')
# 최대값 알고리즘
maxAlo = ms.MaxAlgorithm(score)
maxAlo.setMaxNumIdxAndNum()
maxNum = maxAlo.getMaxNum()
# print(f'maxNum : {maxNum}')
# 인덱스 리스트 생성
indexes = [0 for i in range(maxNum + 1)]
# print(f'indexes : {indexes}')
# print(f'indexes length : {len(indexes)}')
# 인덱스 리스트에 빈도 저장
for n in score:
indexes[n] = indexes[n] + 1
# print(f'indexes : {indexes}')
n = 1
while True:
maxAlo = ms.MaxAlgorithm(indexes)
maxAlo.setMaxNumIdxAndNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
# print(f'maxNum : {maxNum}')
# print(f'maxNumIdx : {maxNumIdx}')
if maxNum == 0:
break
print(f'{n}, {maxNumIdx}빈도수 : {maxNum}\t', end='')
print('+' * maxNum)
indexes[maxNumIdx] = 0
n += 1
근삿값
근삿값이란?
- 특정값(참값)에 가장 가까운 값을 근사값이라고 한다.
import random
nums = random.sample(range(0,50),20)
print(f'nums : {nums}')
inputNum = int(input('input number : '))
print(f'inputNum : {inputNum}')
nearNum = 0
minNum = 50
for n in nums:
absNum = abs(n - inputNum)
# print(f'absNum : {absNum}')
if absNum < minNum:
minNum = absNum
nearNum = n
print(f'nearNum : {nearNum}')
근삿값(실습)
- 근삿값 알고리즘을 이용해서 시험 점수를 입력하면 학점이 출력되는 프로그램을 만들어보자. 평균 점수에 따른 학점 기준 점수는 다음과 같다.
# 모듈
def getNearNum(an):
baseScores = [95, 85, 75, 65, 55]
nearNum = 0
minNum = 100
for n in baseScores:
absNum = abs(n - an)
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
scores = []
kor = int(input('input kor score : '))
scores.append(kor)
eng = int(input('input eng score : '))
scores.append(eng)
mat = int(input('input mat score : '))
scores.append(mat)
sci = int(input('input sci score : '))
scores.append(sci)
his = int(input('input his score : '))
scores.append(his)
totalScore = sum(scores)
print(f'totalScore : {totalScore}')
avgScore = totalScore / len(scores)
print(f'avgScore : {avgScore}')
grade = near.getNearNum(avgScore)
print(f'grade : {grade}')
평균
평균이란?
- 여러 수나 양의 중간 값을 갖는 수를 평균이라고 한다.
import random
# nums = random.sample(range(0,100),10)
# print(f'nums : {nums}')
#
# total = 0
# for n in nums:
# total += n
#
# average = total / len(nums)
# print(f'average : {average}')
# 50이상 90이하 수들의 평균
import random
# nums = random.sample(range(0,100),30)
# print(f'nums : {nums}')
#
# total = 0
# targetNums = []
# for n in nums:
# if n >= 50 and n <= 90:
# total += n
# targetNums.append(n)
# average = total / len(nums)
# print(f'average : {round(average)}')
# print(f'targetNums : {targetNums}')
# 정수들의 평균
# nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
# total = 0
# targetNums = []
# for n in nums:
# if n - int(n) == 0:
# # 조건은 type(n) == int로도 출력할 수 있다.
# total += n
# targetNums.append(n)
# average = total / len(targetNums)
# print(f'average : {round(average, 2)}')
# print(f'targetNums : {targetNums}')
# 실수들의 평균
nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
total = 0
targetNums = []
for n in nums:
if n - int(n) != 0:
# 조건은 type(n) == float로도 출력할 수 있다.
total += n
targetNums.append(n)
average = total / len(targetNums)
print(f'average : {round(average, 2)}')
print(f'targetNums : {targetNums}')
예시 답안으로는 실수인 float으로만 했지만 정수 및 몇몇의 다른 조건으로도 가능하다.
평균(실습)
- 다음은 어떤 체조선수의 점수이다. 평균을 구하고 순위를 정하는 알고리즘을 만들어보자.
- 체조선수의 평균값을 구해서 현재 전체 순위에서 몇위에있는지 구하는 문제
# 모듈
class Top5Players:
def __init__(self, cs, ns):
self.currentScores = cs # 현재점수
self.newScore = ns # 새로운점수
def setAlignScore(self):
# 새로운 점수가 현재점수의 어디에 정렬되어야하는지 결정하는 것
nearIdx = 0
nearScore = 0
minNum = 10.0
for i,s in enumerate(self.currentScores):
absNum = abs(self.newScore - s) # abs()절대값
if absNum < minNum: # 최소값
minNum = absNum # 근삿값 구하기
nearIdx = i # 근삿값 구하기
nearScore = s # 근삿값 구하기
if self.newScore >= self.currentScores[nearIdx]: # 정렬중 앞쪽인지 뒷쪽인지 확인하는 것
for i in range(len(self.currentScores)-1, nearIdx, -1):
self.currentScores[i] = self.currentScores[i-1]
self.currentScores[nearIdx] = self.newScore
else:
for i in range(len(self.currentScores) - 1, nearIdx + 1, -1):
self.currentScores[i] = self.currentScores[i - 1]
self.currentScores[nearIdx] = self.newScore
def getFinalTop5Scores(self):
return self.currentScores
# 실행문
import near
scores = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
top5PlayerScores = [9.12, 8.95, 8.12, 7.90, 7.88]
print(f'top5PlayerScores : {top5PlayerScores}')
total = 0
for n in scores:
total += n
average = round(total / len(scores), 2)
print(f'total : {total}')
print(f'average : {average}')
tp = near.Top5Players(top5PlayerScores, average)
# 상위 5명의 점수, 평균값
tp.setAlignScore()
top5PlayerScores = tp.getFinalTop5Scores()
print(f'top5PlayerScores : {top5PlayerScores}')
재귀
재귀 알고리즘이란?
- 나 자신을 다시 호출하는 것을 재귀라고 한다.
def recusion(num):
if num > 0:
print('*' * num)
return recusion(num - 1)
else:
return 1
recusion(10)
# 10! = 10 * 9 * 7 * 6... 팩토리얼에서 재귀함수를 많이 쓰인다.
def factorial(num):
if num > 0:
return num * factorial(num -1)
else:
return 1
print(f'factorial(10) : {format(factorial(10), ",")}')
재귀 알고리즘(실습)
- 재귀 알고리즘을 이용한 최대 공약수 계산
# 반복문 for문을 이용한 최대공약수 구하기
def greatestCommonDevide(n1, n2):
maxNum = 0
for i in range(1, (n1 + 1)):
if n1 % i == 0 and n2 % i == 0:
maxNum = i
return maxNum
print(f'greatestCommonDevide(82, 32) : {greatestCommonDevide(82, 32)}')
print(f'greatestCommonDevide(96, 40) : {greatestCommonDevide(96, 40)}')
print()
# 재귀함수를 이용한 최대공약수 구하기
def gcd(n1, n2):
if n1 % n2 == 0:
return n2
else:
return gcd(n2, n1 % n2)
# n1 % n2 == 0이 될때까지 반복적으로 자신을 호출하여 최대공약수를 구한다.
print(f'gcd(82, 32) : {gcd(82, 32)}')
print(f'gcd(96, 40) : {gcd(96, 40)}')
하노이의 탑
하노이의 탑 이란?
- 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다. (재귀함수를 이용하면 된다.)
- 축1, 축2, 축3 과 축1에있는 원반을 위에서부터 a1, a2, a3이라고 가정하면 순서는 이렇다.
a1(축1) -> a1(축3) 이동
a2(축1) -> a2(축2) 이동
a1(축3) -> a1(축2) 이동
a3(축1) -> a3(축3) 이동
a1(축2) -> a1(축1) 이동
a2(축2) -> a2(축3) 이동
a1(축1) -> a1(축3) 이동하면
축1에 있었던 a1, a2, a3가 모두 축3으로 이동된다.
하노이의 탑 참조
- 축1, 축2, 축3 과 축1에있는 원반을 위에서부터 a1, a2, a3이라고 가정하면 순서는 이렇다.
하노이의 탑(실습)
- 파이썬을 이용해서 하노이의 탑 게임 진행 과정을 출력하자!
# 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
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)
병합정렬
병합정렬이란?
- 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
def mSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx])
rightNums = mSort(ns[midIdx:len(ns)])
mergeNums = []
leftIdx = 0; rightIdx = 0
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
nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mSort(nums) : {mSort(nums)}')
병합정렬(실습)
- 1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자.
def mSort(ns, asc=True):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx], asc=asc) # 오름차순 내림차순으로 재귀함수를사용할때도 명시해줘야함.
rightNums = mSort(ns[midIdx:len(ns)], asc=asc) # 여기까지가 분할하는 단계 재귀함수를 사용하여 끝까지 분할한다.
mergeNums = [] # 여기부터 병합 시작부분
leftIdx = 0; rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums): # 작은것은 앞으로 큰것은 뒤로 넘기기위한 조건
if asc:
if leftNums[leftIdx] < rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
else:
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 as rd
import sortMod as sm
rNums = rd.sample(range(1, 101),10)
print(f'not sorted rNums : {rNums}')
print(f'sorted rNum ASC : {sm.mSort(rNums)}')
print(f'sorted rNum DESC : {sm.mSort(rNums, asc=False)}')
퀵정렬
퀵정렬이란?
- 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
def qSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
midVal = ns[midIdx]
smallNums = [] # 왼쪽의 값들
sameNums = [] # 같은 값들
gidNums = [] # 오른쪽의 값들
for n in ns:
if n < midVal:
smallNums.append(n)
elif n == midVal:
sameNums.append(n)
else:
gidNums.append(n)
return qSort(smallNums) + sameNums + qSort(gidNums)
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(f'qSort(nums) : {qSort(nums)}')
퀵정렬(실습)
- 1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자.
# 모듈
def qSort(ns, asc=True):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2 # 기준값(리스트의 중간에 해당하는 값)
midVal = ns[midIdx] # 기준값의 value
smallNums = [] # 왼쪽의 값들
sameNums = [] # 같은 값들
bigNums = [] # 오른쪽의 값들
for n in ns:
if n < midVal:
smallNums.append(n)
elif n == midVal:
sameNums.append(n)
else:
bigNums.append(n)
if asc:
return qSort(smallNums, asc=asc) + sameNums + qSort(bigNums, asc=asc)
else:
return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums, asc=asc)
# 같은 값들의 리스트인 sameNums는 더이상 정렬할 수 없기때문에 재귀함수를 사용하지않음.
# 실행문
import random as rd
import sortMod as sm
rNums = rd.sample(range(1, 100),10)
print(f'not sorted rNums : {rNums}')
print(f'sorted rNums by ASC : {sm.qSort(rNums)}')
print(f'sorted rNums by DESC : {sm.qSort(rNums, asc=False)}')
코딩공부중