▷ 오늘 학습 내용: 알고리즘 강의(4~7)
08_최빈값
최빈값 → 데이터에서 빈도수가 가장 많은 데이터
class MaxAlgorithm:
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
self.maxNumIdx = 0
def setMaxIdxAndNum(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 getMaxNumIndx(self):
return self.maxNumIdx nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlo = MaxAlgorithm(nums)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
indexes = [0 for i in range(maxNum+1)]
for n in nums:
indexes[n] = indexes[n] +1
maxAlo = MaxAlgorithm(indexes)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIndx()
print(f'최빈값: {maxNumIdx}, 빈도수: {maxNum}')09_근삿값
근삿값: 특정 값(참값)에 가장 가까운 값
import random
nums = random.sample(range(0,50), 20)
inputN = int(input('input number: '))
nearNum = 0 #근삿값 0으로 지정해줌
minNum = 50 #근삿값과의 차이(가장 큰 숫자 모르면 최댓값 알고리즘으로 구하기)
for n in nums:
absNum = abs(n- inputN) #절댓값으로 구하기
if absNum < minNum:
minNum = absNum
nearNum = n
print(f'nearNum: {nearNum}')10_평균
여러 수나 양의 중간값을 갖는 수
# random numbers 30개 중에서 50이상 90이하 수들의 평균
import random
nums = random.sample(range(0,100), 30)
total = 0
listNums = []
for n in nums:
if n>=50 and n<=90:
total += n
listNums.append(n)
average = total / len(listNums)
print(f'listNums: {listNums}')
print(f'average: {round(average,2)}')11_재귀
재귀: 나 자신을 다시 호출하는 것
- n1, n2의 최대공약수를 재귀 알고리즘으로 출력하기
def gcd(n1,n2):
if n1 % n2 == 0:
return n2
else:
return gcd(n2,n1 % n2)
print(f'gcd(82,32) : {gcd(82,32)}')
print(f'gcd(96,40) : {gcd(96,40)}')12_하노이의 탑
# 1disc (1 → 3), 2disc (1 → 2), 1disc (3 → 2), 3disc (1 → 3),
# 1disc (2 → 1), 2disc (2 → 3), 1disc (1 → 3)
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)13_병합 정렬
자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
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)}')14_퀵 정렬
기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
def qSort(ns):
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)
return qSort(smallNums) + sameNums + qSort(bigNums)
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(f'sortedNums: {qSort(nums)}')📝 알고리즘 이해하는 시간 때문에 강의 듣는 시간도 길어졌다. 하노이의 탑 이해하는데 진짜 오래걸렸고 재귀함수 너무 어렵다..
▷ 내일 학습 계획: 알고리즘 강의(문풀 1~3)
