[제로베이스] 데이터 사이언스 15기 - (05-24 알고리즘 스터디노트)

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

01 선형 검색 ~ 04 이진 검색

선형 검색

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print('datas: {}'.format(datas))
print('datas length: {}'.format(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('searchResultIdx: {}'.format(searchResultIdx))

• 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 보초법이라고 한다

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print('datas: {}'.format(datas))
print('datas length: {}'.format(len(datas)))

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1

datas.append(searchData)

n = 0
while True:
    if datas[n] == searchData:
        if n != len(datas) - 1:
            searchResultIdx = n
        break

    n += 1

print('datas: {}'.format(datas))
print('datas length: {}'.format(len(datas)))
print('searchResultIdx: {}'.format(searchResultIdx))

• (실습) 리스트에서 가장 앞에 있는 숫자 '7'을 검색하고 위치(인덱스)를 출력하자

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print('nums: {}'.format(nums))
print('nums length: {}'.format(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('nums: {}'.format(nums))
print('nums length: {}'.format(len(nums)))
print('searchResultIdx: {}'.format(searchResultIdx))

if searchResultIdx < 0:
    print('not search index')
else:
    print('search index: {}'.format(searchResultIdx))

• (실습) 리스트에서 숫자 '7'을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print('nums: {}'.format(nums))
print('nums length: {}'.format(len(nums)))

searchData = int(input('input search number: '))
searchResultIdxs = []

nums.append(searchData)

n = 0
while True:
    if nums[n] == searchData:
        if n != len(nums) - 1:
            searchResultIdxs.append(n)
        else:
            break

    n += 1

print('nums: {}'.format(nums))
print('nums length: {}'.format(len(nums)))
print('searchResultIdxs: {}'.format(searchResultIdxs))
print('searchResultCnts: {}'.format(len(searchResultIdxs)))

이진 검색

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다
  (정렬되어 있어야 사용 가능)
  

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print('datas: {}'.format(datas))
print('datas length: {}'.format(len(datas)))

searchData = int(input('search data: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]

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

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print('midIdx: {}'.format(midIdx))
        print('midVal: {}'.format(midVal))

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print('searchResultIdx: [{}]'.format(searchResultIdx))

• (실습) 리스트를 오름차순으로 정렬한 후 '7'을 검색하고 위치(인덱스)를 출력하자

 nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print('nums: {}'.format(nums))

nums.sort()
print('nums: {}'.format(nums))

searchData = int(input('search number: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]

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

순위 05 ~ 06

순위

• 수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다

import random

nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]

print('nums: {}'.format(nums))
print('ranks: {}'.format(ranks))

for idx, num1 in enumerate(nums):
    for num2 in nums:
        if num1 < num2:
            ranks[idx] += 1

print('nums: {}'.format(nums))
print('ranks: {}'.format(ranks))

for idx, num in enumerate(nums):
    print('num: {} \t rank: {}'.format(num, ranks[idx] + 1))

• (실습) 학급 학생(20명)들의 중간고사와 기말고사 성적을 이용해서 각각의 순위를 구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력하는 프로그램
  (시험 성적은 난수를 이용한다)

rankMod 모듈

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(mss))]
        self.rankDeviation = [0 for i in range(len(mss))]

    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('mid_rank: {} \t end_rank: {} \t Deviation: {}'.format(mRank, self.endRanks[idx], deviation))

rankEx.py

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('midStuScors: {}'.format(midStuScos))
print('mid_rank: {}'.format(rd.getMidRank()))

rd.setEndRank()
print('endStuScors: {}'.format(endStuScos))
print('end_rank: {}'.format(rd.getEndRank()))

rd.printRankDeviation()

07 버블 정렬 ~ 12 선택 정렬

버블 정렬

• 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 욺기는 알고리즘이다
  

nums = [10, 2, 7, 21, 0]
print('not sorted nums: {}'.format(nums))

length = len(nums) - 1
for i in range(length):
    for j in range(length - i):
        if nums[j] > nums[j + 1]:
            nums[j], nums[j + 1] = nums[j + 1], nums[j]

        print(nums)
    print()

print('sorted nums: {}'.format(nums))

• (실습) 새 학년이 되어 학급에 20명의 새로운 학생들이 모였다 학생들을 키 순서로 줄 세워보자 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성한다

sortMod 모듈

import copy

def bubbleSort(ns, deepCopy=True):

깊은 복사

    if deepCopy:
        cns = copy.copy(ns)

얕은 복사

    else:
        cns = ns

    length = len(cns) - 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

bubbleEx.py

import random as rd
import sortMod as sm

students = []

for i in range(20):
    students.append(rd.randint(170, 185))

print('students: {}'.format(students))

깊은 복사

sortedStudent = sm.bubbleSort(students, deepCopy=True)

얕은 복사

sortedStudent = sm.bubbleSort(students, deepCopy=False)

print('students: {}'.format(students))
print('sortedStudents: {}'.format(sortedStudent))

삽입 정렬

• 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다
  

오름차순

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

내림차순

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

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

sortMod 모듈

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:
                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 getMinNumber(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]

insertEx.py

import random
import sortMod as sm

nums = random.sample(range(1, 1000), 100)
print('not sorted numbers: {}'.format(nums))

# 객체 생성

sn = sm.SortNumbers(nums)

# 오름차순

sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print('sortedNumbers by ASC: {}'.format(sortedNumbers))

# 내림차순

sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print('sortedNumbers by DESC: {}'.format(sortedNumbers))

# 최대, 최솟값

print('min: {}'.format(sn.getMinNumber()))
print('max: {}'.format(sn.getMaxNumber()))

선택 정렬

• 주어진 리스트 중에 최솟값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘

nums = [4, 2, 5, 1, 3]
print('nums: {}'.format(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

    nums[i], nums[minIdx] = nums[minIdx], nums[i]
    print('nums: {}'.format(nums))

print('fianl nums: {}'.format(nums))

• (실습) 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자
  (시험 정수는 50부터 100까지로 한다)

sortMod 모듈

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

selectionSortEx.py

import random
import sortMod as sm
import copy

scores = random.sample(range(50, 100), 20)

copy.deepcopy()로 원본을 훼손하지않고 가져올 수 있음

print('scores: {}'.format(scores))
result = sm.sortNumber(copy.deepcopy(scores))
print('result: {}'.format(result))

print('scores: {}'.format(scores))
result = sm.sortNumber(copy.deepcopy(scores), asc=False)
print('result: {}'.format(result))

13 최댓값 ~ 16 최솟값

최댓값

• 자료구조에서 가장 큰 값을 찾는다
  

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])

최댓값 반환

maxNum = ma.getMaxNum()
print('maxNum: {}'.format(maxNum))

• (실습) 리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘

class MaxAlgorithm:
    def __init__(self, cs):
        self.chars = cs
        self.maxchar = 0

    def getMaxChar(self):
        self.maxChar = self.chars[0]

# ord() -> 문자열을 아스키코드로 변환시켜줌

        for c in self.chars:
            if ord(self.maxChar) < ord(c):
                self.maxChar = c

        return self.maxChar

chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = MaxAlgorithm(chars)
maxChar = mc.getMaxChar()
print('maxChar: {}'.format(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, 7, 10, 0, 8, 20, -11])
minNum = ma.getMinNum()
print('minNum: {}'.format(minNum))

• (실습) 리스트에서 아스키코드가 가장 작은 값을 찾는 알고리즘

class MinAlgorithm:
    def __init__(self, cs):
        self.chars = cs
        self.minChar = 0

    def getMinChar(self):
        self.minChar = self.chars[0]

        for c in self.chars:
            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('minChar: {}'.format(minChar))

17 최빈값 ~ 20 근삿값

최빈값

• 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다
  

class MaxAlgorithm:
    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumIdx = 0

    def setMaxIndAndNum(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.setMaxIndAndNum()
maxNum = maxAlo.getMaxNum()
print('maxNum: {}'.format(maxNum))

indexes = [0 for i in range(maxNum + 1)]
print('indexes: {}'.format(indexes))
print('indexes length: {}'.format(len(indexes)))

for n in nums:
    indexes[n] = indexes[n] + 1
print('indexes: {}'.format(indexes))

maxAlo = MaxAlgorithm(indexes)
maxAlo.setMaxIndAndNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
print('maxNum: {}'.format(maxNum))
print('maxNumIdx: {}'.format(maxNumIdx))

print('즉, {}의 빈도수가 {}로 가장 높다.'.format(maxNumIdx, maxNum))

• (실습) 최빈값 알고리즘을 이용해서 학생 100명의 점수 분포를 다음과 같이 나타내 보자
  

maxScore.py

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

modeEx.py

import random
import maxScore as ms

scores = []

for i in range(100):
    rn = random.randint(71, 100)
    if rn != 100: rn = rn - (rn % 5)
    scores.append(rn)

print('scores: {}'.format(scores))
print('scores length: {}'.format(len(scores)))

# 최댓값 알고리즘
maxAlo = ms.MaxAlgorithm(scores)
maxAlo.setMaxNumIdxAndNum()
maxNum = maxAlo.getMaxNum()
print('maxNum: {}'.format(maxNum))

# 인덱스 리스트 생성
indexes = [0 for i in range(maxNum + 1)]
print('indexes: {}'.format(indexes))
print('indexes length: {}'.format(len(indexes)))

# 인덱스 리스트에 빈도 저장
for n in scores:
    indexes[n] = indexes[n] + 1
print('indexes: {}'.format(indexes))

n = 1
while True:
    maxAlo = ms.MaxAlgorithm(indexes)
    maxAlo.setMaxNumIdxAndNum()
    maxNum = maxAlo.getMaxNum()
    maxNumIdx = maxAlo.getMaxNumIdx()

    if maxNum == 0:
        break
    print('{}. {}빈도수: {}\t'.format(n, maxNumIdx, maxNum), end='')
    print('+' * maxNum)
    indexes[maxNumIdx] = 0
    n += 1

근삿값

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

import random

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

inputNum = int(input('input number: '))
print('inputNum: {}'.format(inputNum))

nearNum = 0
minNum = 50

for n in nums:
    absNum = abs(n - inputNum)
    # print('absNum: {}'.format(absNum))

    if absNum < minNum:
        minNum = absNum
        nearNum = n

print('nearNum: {}'.format(nearNum))

• (실습) 근삿값 알고리즘을 이용해서 시험 점수를 입력하면 학점이 출력되는 프로그램을 만들어보자
  

near 모듈

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'

nearEx.py

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

# 평균
avgScore = totalScore / len(scores)
print('avgScore: {}'.format(avgScore))

# 등급
grade = near.getNearNum(avgScore)
print('grade: {}'.format(grade))

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)))

재미있었던 부분

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

어려웠던 부분

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

느낀점 및 내일 학습 계획

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