스터디 노트 (알고리즘 19-30)_0725

📌 근삿값

• 특정 값(참값)에 가장 가까운 값을 근삿값이라고 한다.

import random
nums = random.sample(range(0, 50), 20) # 0~50까지의 숫자 20개를 nums에 할당한다.
print(f'nums : {nums}')

inputNum = int(input('input Number : '))
print(f'inputNum : {inputNum}')

nearNum = 0
minNum = 50 #데이터가 많으면 최댓값 알고리즘을 통해서 구한다.
#최댓값 설정을 해서 for문으로 근사값을 찾는 것을 용이하게 해준다
nearIdx = 0
for idx, n in enumerate(nums):
    absNum = abs(n - inputNum) #절댓값으로 덮어준다
    # print(f'absNum : {absNum}')

    if absNum < minNum: #절대값이 최소값보다 작을 때
        nearIdx = idx #idx를 최소값 idx로 초기화
        minNum = absNum #최소값을 절대값에 초기화
        nearNum = n #그때 근삿값은 n이다

print(f'nearNum : {nearNum}')
print(f'nearNumIdx : {nearIdx}')
>>>>
input Number : 45
inputNum : 45
nearNum : 43
nearNumIdx : 13

📌 근삿값 (실습)

#모듈코드
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(grade)
>>>>
input kor score : 80
input eng score : 70
input mat score : 60
input sci score : 90
input his score : 45
totalScore = 345
avgScore = 69.0
D

📌 근삿값 (실습 2)

#모듈
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) #차이를 계산
            #차이가 최솟값일때 근삿값이다.

            if absNum < minNum:
                minNum = absNum
                nearScore = s
                nearIdx = i


        if self.newScore >= self.currentScores[nearIdx]:
            #새로운 스코어가 근삿값보다 크거나 같을때
            for i in range (len(self.currentScores) - 1, nearIdx, -1):
                #5위부터 근삿값까지의 점수들은
                self.currentScores[i] = self.currentScores[i-1]
                #한칸씩 밀려남
            self.currentScores[nearIdx] = self.newScore
            #새로운 점수가 근삿값 자리에 끼워넣어짐

        else: #새로운 스코어가 근삿값보다 작을때
            for i in range (len(self.currentScores) - 1, nearIdx + 1, -1):
                #5위부터 근삿값 바로 아래 순위까지
                self.currentScores[i] = self.currentScores[i-1]
                #한칸씩 밀려남
            self.currentScores[nearIdx+1] = 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; average = 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)
tp.setAlignScore()
top5Scores = tp.getFinalTop5Scores()

print(f'{top5Scores}')

>>>>
top5PlayerScores : [9.12, 8.95, 8.12, 7.9, 7.88]
total : 83.9
average : 8.39
[9.12, 8.95, 8.39, 8.12, 7.9]

📌 재귀 알고리즘

• 나 자신을 다시 호출하는 것

def recusion(num):

    if num > 0:
        print('*' * num)
        return recusion(num - 1)

    else:
        return 1

recusion(10)
>>>>
**********
*********
********
*******
******
*****
****
***
**
*

📌 재귀 알고리즘 (실습)

 

출처 : 제로베이스 데이터 스쿨

def greatestCommonDevide(n1, n2):

    maxNum = 0
    for i in range(1, (n1+1)):
        if n1 % i == 0 and n2 % i == 0: #공약수를 구한다
            maxNum = i #i를 계속 새롭게 갱신, 최대공약수가 구해짐

    return maxNum

print(f'greatestCommonDevide(82, 32) : {greatestCommonDevide(82, 32)}')
print(f'greatestCommonDevide(96, 40) : {greatestCommonDevide(96, 40)}')

def gcd(n1, n2):

    if n1 % n2 == 0: #n1을 n2로 나눈 나머지가 0이 되면
        return n2 #n2를 반환한다

    else:
        return gcd(n2, n1 % n2) #n2를 n1을 n2로 나눈 나머지와 나눈다 (반복)

print(f'greatestCommonDevide(82, 32) : {gcd(82, 32)}')
print(f'greatestCommonDevide(96, 40) : {gcd(96, 40)}')

📌 하노이의 탑

def moveDisc(discCnt, fromBar, toBar, viaBar): #3, 1, 3, 2
    if discCnt == 1:
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}로 이동')
    else:
        moveDisc(discCnt-1, fromBar, viaBar, toBar)

        print(f'{discCnt}disc를 {fromBar}에서 {toBar}로 이동')

        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):
        # 각Nums의 길이가 Idx보다 클때까지
        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'nums : {nums}')
print(f'sorted nums : {mSort(nums)}')
>>>>
nums : [8, 1, 4, 3, 2, 5, 10, 6]
sorted nums : [1, 2, 3, 4, 5, 6, 8, 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 = [] #분할된 nums를 다시 합친다
    leftIdx = 0; rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums): # 각Nums의 길이가 Idx보다 클때까지

        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 rNums ASC : {sm.mSort(rNums)}')
print(f'sorted rNums DESC : {sm.mSort(rNums, asc=False)}')
>>>>
not sorted rNums : [32, 43, 30, 99, 55, 4, 49, 69, 16, 61]
sorted rNums ASC : [4, 16, 30, 32, 43, 49, 55, 61, 69, 99]
sorted rNums DESC : [99, 69, 61, 55, 49, 43, 32, 30, 16, 4]

📌 퀵정렬

• 기준보다 작은 값과 큰 값을 분리한 후, 다시 합친다

def qSort(ns, asc=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 asc:
        return qSort(smallNums, asc=asc) + sameNums + qSort(bigNums, asc=asc)
    else:
        return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums, asc=asc)

import quickMod
import random

nums = random.sample(range(1, 100), 10)

print(f'notSorted rNums : {nums}')

qSort=quickMod.qSort(nums)
print(f'merge sorted rNums ASC : {qSort}')

qSortdsce=quickMod.qSort(nums, False)
print(f'merge sorted rNums DSCE : {qSortdsce}')
>>>>
notSorted rNums : [74, 18, 42, 54, 24, 69, 34, 77, 71, 47]
merge sorted rNums ASC : [18, 24, 34, 42, 47, 54, 69, 71, 74, 77]
merge sorted rNums DSCE : [77, 74, 71, 69, 54, 47, 42, 34, 24, 18]