[제로베이스] 데이터 사이언스 12기 - (02-20 스터디노트)

오늘 수강한 강의 - 알고리즘(21 ~ 30)

21 평균 ~ 26 하노이의 탑

평균

• 여러 수나 양의 중간값을 갖는 수를 평균이라고 한다

import random

nums = random.sample(range(0, 100), 10)
print('nums: {}'.format(nums))

total = 0
for n in nums:
    total += n

average = total / len(nums)
print('average: {}'.format(round(average, 2)))

• (예제) 50이상 90이하 수들의 평균

import random

nums = random.sample(range(0, 100), 30)
print('nums: {}'.format(nums))

total = 0
targetNums = []
for n in nums:
    if n >= 50 and n <= 90:
        total += n
        targetNums.append(n)

average = total / len(targetNums)
print('targetNums: {}'.format(targetNums))
print('average: {}'.format(round(average, 2)))

• (예제) 정수들의 평균

nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print('nums: {}'.format(nums))

targetNums = []
total = 0
for n in nums:
    if n - int(n) == 0:
        total += n
        targetNums.append(n)

average = total / len(targetNums)
print('targetNums: {}'.format(targetNums))
print('average: {}'.format(round(average, 2)))

• (예제) 실수들의 평균

nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print('nums: {}'.format(nums))

targetNums = []
total = 0
for n in nums:
    if n - int(n) != 0:
        total += n
        targetNums.append(n)

average = total / len(targetNums)
print('targetNums: {}'.format(targetNums))
print('average: {}'.format(round(average, 2)))

• (실습) 다음은 어떤 체조선수의 점수이다
  평균을 구하고 순위를 정하는 알고리즘을 만들어보자
  

near 모듈

class Top5Players:
    def __init__(self, cs, ns):
        self.currentScores = cs
        self.newScore = ns

    def setAlignScores(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
                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

averageEx.py

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('top5PlayerScores: {}'.format(top5PlayerScores))

total = 0
average = 0
for n in scores:
    total += n

average = round(total / len(scores), 2)

print('total: {}'.format(total))
print('average: {}'.format(average))

tp = near.Top5Players(top5PlayerScores, average)
tp.setAlignScores()
top5PlayerScores = tp.getFinalTop5Scores()
print('top5PlayerScores: {}'.format(top5PlayerScores))

재귀

• 나 자신을 다시 호출하는 것을 재귀라고 한다
  

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

recusion(10)

• (예제) 10! (10의 팩토리얼)

def factorial(num):
    if num > 0:
        return num * factorial(num - 1)
    else:
        return 1

print('factorial(10): {}'.format(factorial(10)))

• (실습) 재귀 알고리즘을 이용한 최대 공약수 계산
  

재귀

def gcd(n1, n2):
    if n1 % n2 == 0:
        return n2
    else:
        return gcd(n2, n1 % n2)

print('gcd(82, 32): {}'.format(gcd(82, 32)))
print('gcd(96, 40): {}'.format(gcd(96, 40)))

반복문

def gcd(n1, n2):
    maxNum = 0
    for i in range(1, (n1 + 1)):
        if n1 % i == 0 and n2 % i == 0:
            maxNum = i

    return maxNum

print('gcd(82, 32): {}'.format(gcd(82, 32)))
print('gcd(82, 32): {}'.format(gcd(96, 40)))

하노이의 탑

• 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다
  
  하노이의 탑 직접 해보기

• (실습) 파이썬을 이용해서 하노이의 탑 게임 진행 과정을 출력

        # 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
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)

27 병합 정렬 ~ 30 퀵 정렬

병합 정렬

• 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다
  
  

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('mergedNums: {}'.format(mSort(nums)))

• (실습) 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈
  

sortMod.py

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

mergeEx.py

import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 101), 10)
print('not sorted rNums: {}'.format(rNums))
print('sorted rNums ASC: {}'.format(sm.mSort(rNums)))
print('sorted rNums DESC: {}'.format(sm.mSort(rNums, asc=False)))

퀵 정렬

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

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('qSort(nums): {}'.format(qSort(nums)))

• (실습) 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈
  

sortMod.py

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)

quickEx.py

import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 100), 10)
print('not sorted rNums: {}'.format(rNums))
print('sorted rNums ASC: {}'.format(sm.qSort(rNums)))
print('sorted rNums DESC: {}'.format(sm.qSort(rNums, asc=False)))

재미있었던 부분

병합 정렬과 퀵 정렬을 사용하여 난수나 이미 있는 수의 리스트를 정렬하는 방법을 배운 것이 가장 기억에 남는다

어려웠던 부분

재귀 함수 처음 부분은 어렵지 않았지만 하노이의 탑에서 머리가 멈추는 느낌이 들었다 너무 헷갈리고 직접 그려보고 나서야 조금은 이해를 했다 아직 백퍼센트 이해하지는 못한 것 같다

느낀점 및 내일 학습 계획

하노이의 탑을 직접 게임을 해보며 이해하려고 노력중인데 아직도 어렵다
오늘은 하노이의 탑을 중심적으로 복습해야겠다
내일은 알고리즘 문제풀이를 할 예정이다