파이썬 알고리즘

어느덧 제로베이스 데이터 스쿨을 수강한지도 한 달이 지났다.

이것 저것 정신없이 배우다 보니 한 달이라는 시간도 후다닥 지나버렸다... 코딩을 배운다는 것이 쉬운 일도 아니고 빠르게 성장하는 느낌도 못 받지만 조바심 가지지 않고 꾸준히 공부해 나갈 마음이다 :)

노트

6_001

# 선형검색: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
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(f'searchResultIdx: {searchResultIdx}')


# 보초법: 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
# 검색 성공: 마지막 이전에 '9'가 검색된 경우
# 검색 실패: 마지막에 '9'가 검색된 경우
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(f'searchResultIdx: {searchResultIdx}')

6_002

# 리스트에서 숫자 '7'을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자.
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'len(nums): {len(nums)}')

def findNum(tempNums):  # 함수화 해보기!!!

    searchNum = int(input('찾으려는 수 입력: '))
    searchNumIdxs = []

    tempNums.append(searchNum)

    n = 0
    while True:
        if tempNums[n] == searchNum:
            if n != len(tempNums) - 1:
                searchNumIdxs.append(n)
            else:
                break
        n += 1

    print(f'nums: {nums}')
    print(f'searchNumIdx: {searchNumIdxs}')

findNum(nums)

6_003

# 이진검색: 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

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

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

print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')

while datas[0] <= searchData <= datas[len(datas) - 1]:
    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}')

6_004

# 리스트를 오름차순으로 정렬한 후 '7'을 검색하고 위치(인덱스)를 출력하자.
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums.sort()
print(nums)

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

staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')

while nums[0] <= searchData <= nums[len(nums) - 1]:
    if searchData == nums[len(nums) - 1]:
        searchResultIdx = len(nums) - 1
        break

    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

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

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: {searchResultIdx}')

6_005

# 순위란? 수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다.
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'nums: {num} \t ranks: {ranks[idx] + 1}')

6_006

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

rd.setEndRank()
print(f'endStudScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')

rd.printRanksDeviation()


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 setEndRank(self):
        self.setRank(self.endStuScos, self.endRanks)

    def getMidRank(self):
        return self.midRanks

    def getEndRank(self):
        return self.endRanks

    def printRanksDeviation(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}')

6_007

# 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘이다.
nums = [10, 2, 7, 21, 0]
print(f'not sorted 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] # 위의 코드를 파이썬에서는 훨씬 간단하게 표현 가능하다!!

        print(nums)
    print()

print(f'sorted nums: {nums}')

6_008

# 새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자.
# 학생들의 키는 random 모듈을 이용해서 170 ~ 185 사이로 생성한다.
import random as rd
import sortMod as sm

students = []

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

print(f'students: {students}')

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

print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')


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

6_009

# 삽입정렬: 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
# 오름차순
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'ascending nums: {nums}')

# 내림차순
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'descending nums: {nums}')

6_010

# 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
# 요구 사항1) 생성된 난수들을 오름 차순 또는 내림 차순으로 정렬하는 알고리즘 구현
# 요구 사항2) 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
import random
import sortMod as sm

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

# 객체 생성
sn = sm.SortNumbers(nums)

# 오름차순
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by ASC: {sortedNumbers}')

# 내림차순
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by DESC: {sortedNumbers}')

# min & max
print(f'min: {sn.getMinNumber()}')
print(f'min: {sn.getMaxNumber()}')



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]

6_011

# 선택정렬: 주어진 리스트 중에 최솟값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정리하는 알고리즘이다.
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

    # tempNum = nums[i]
    # nums[i] = nums[minIdx]
    # nums[minIdx] = tempNum

    nums[i], nums[minIdx] = nums[minIdx], nums[i]  # 똑같은 코드를 파이썬에서는 한줄로 표현!!
    print(f'nums: {nums}')

print(f'final nums: {nums}')

6_012

import random
import sortMod as sm
import copy


scores = random.sample(range(50, 101), 20)
print(f'scores: {scores}')
print(f'scpres length: {len(scores)}')

# deepcopy: 깊은 복사를 이용해 복사본을 보내서 원본 유지 가능!!!
result = sm.sortNumber(copy.deepcopy(scores))
print(f'ascending result: {result}')

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



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

6_013

# nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]
# maxNum = nums[0]
#
# for n in nums:
#     if maxNum < n:
#         maxNum = n
# print(maxNum)

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(f'maxNum: {maxNum}')

6_014

# 리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 만들어보자.
class MaxAlgorithm:

    def __init__(self, cs):
        self.chars = cs
        self.maxChar = 0

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

        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(f'maxChar: {maxChar}')

6_015

# 최솟값: 자료구조에서 가장 작은 값을 찾는다.

class MinAlgorithm:
    def __init__(self, ns):
        self.nums = ns
        self.minNums = 0

    def getMinNums(self):
        self.minNums = self.nums[0]

        for n in self.nums:
            if self.minNums > n:
                self.minNums = n

        return self.minNums

nums = [-2, -4, 5, 7, -100, 10, 0, 8, 20, -11]
ma = MinAlgorithm(nums)
minNum = ma.getMinNums()
print(f'minNum: {minNum}')

6_016

# 리스트에서 아스키코드가 가장 작은 값을 찾는 알고리즘을 만들어보자.
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

chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
ma = MinAlgorithm(chars)
minChar = ma.getMinChar()
print(f'minChar: {minChar}')

6_017

# 최빈값: 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다.
# 최댓값 길이의 리스트를 만들어서 0부터 최댓값까지의 숫자의 개수를 기록한다.

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

    def setMaxIdx(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.setMaxIdx()
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.setMaxIdx()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
print(f'maxNum: {maxNum}')
print(f'maxNumIdx: {maxNumIdx}')

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

6_017

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(f'scores: {scores}')
print(f'scores length: {len(scores)}')

# 최댓값 알고리즘
maxAlo = ms.MaxAlgorithm(scores)
maxAlo.setMaxNumAndIdx()
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 scores:
    indexes[n] = indexes[n] + 1
print(f'indexes: {indexes}')

n = 1
while True:
    maxAlo = ms.MaxAlgorithm(indexes)
    maxAlo.setMaxNumAndIdx()
    maxNum = maxAlo.getMaxNum()
    maxNumIdx = maxAlo.getMaxNumIdx()
    print(f'maxNum: {maxNum}')

    if maxNum == 0:
        break

    print(f'{n}. {maxNumIdx}빈도수: {maxNum}\t', end='')
    print('+' * maxNum)

    indexes[maxNumIdx] = 0

    n += 1
    



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

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

6_019

# 근삿값: 특정 값에 가장 가까운 값을 근삿값이라고 한다.
# 특정 값과의 차이(절대값)을 모두 구해서 그 값이 가장 적은 값이 근삿값이다!!
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}')

6_020

# 근삿값 알고리즘을 이용해서 시험 점수를 입력하면 학점이 출력되는 프로그램을 만들어보자.
# 평균 점수에 따른 학점 기준 점수는 다음과 같다.
# 95에 근삿값이면 A학점
# 85에 근삿값이면 B학점
# 75에 근삿값이면 C학점
# 65에 근삿값이면 D학점
# 55에 근삿값이면 F학점

import nearMod

scores = []

kor = int(input('한국어 점수: '))
scores.append(kor)

eng = int(input('영어 점수: '))
scores.append(eng)

mat = int(input('수학 점수: '))
scores.append(mat)

sci = int(input('과학 점수: '))
scores.append(sci)

his = int(input('국사 점수: '))
scores.append(his)

totalScore = sum(scores)
print(f'totalScore: {totalScore}')

avgScore = totalScore / len(scores)
print(f'avgScore: {avgScore}')

grade = nearMod.getNearNum(avgScore)
print(f'grade: {grade}')



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'

6_021

# 평균: 여러 수나 양의 중간값을 갖는 수를 평균이라고 한다.
import random

# nums = random.sample(range(0, 100), 10)
# print(f'nums: {nums}')
#
# total = 0
# for n in nums:
#     total += n
#
# print(f'총합: {total}')
#
# avg = total / len(nums)
# print(f'평균: {avg}')

# # 50이상 90이하 수들의 평균
# nums = random.sample(range(0, 100), 30)
# print(f'nums: {nums}')
#
# targetNums = []
# total = 0
#
# for n in nums:
#     if 50 <= n <= 90:
#         targetNums.append(n)
#         total += n
# print(f'numInRange: {targetNums}')
# print(f'50이상 90이하 총합: {total}')
#
# avg = total / len(targetNums)
# print(f'50이상 90이하 평균: {round(avg, 2)}')


# 정수들만의 평균
nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print(f'nums: {nums}')

targetNums = []
total = 0

for n in nums:
    if n % 1 == 0:
        targetNums.append(n)
        total += n
print(f'targetNums: {targetNums}')

print(f'정수들의 합: {total}')
avg = total / len(targetNums)
print(f'정수들의 평균: {round(avg, 2)}')


# 소수들만의 평균
nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print(f'nums: {nums}')

targetNums = []
total = 0

for n in nums:
    if n % 1 != 0:
        targetNums.append(n)
        total += n
print(f'targetNums: {targetNums}')

print(f'소수들의 합: {total}')
avg = total / len(targetNums)
print(f'소수들의 평균: {round(avg, 2)}')

6_022

# 다음은 어떤 체조선수의 점수이다. 평균을 구하고 순위를 정하는 알고리즘을 만들어보자.
import nearMod

scores = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
topPlayerScores = [9.12, 8.95, 8.12, 7.90, 7.88]
print(f'top5" {topPlayerScores}')

total = 0

for n in scores:
    total += n
average = round(total / len(scores), 2)

print(f'총점: {total}')
print(f'평균: {average}')

top5 = nearMod.Top5Players(topPlayerScores, average)
top5.setAlignScore()
result = top5.getFinalTop5Scores()
print(f'top5 점수들: {result}')



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

6_023

코드를 입력하세요

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

recursion(10)



# 10! = 10 * 9 * ...... * 2 * 1 재귀 알고리즘을 이용해 표현!!
def factorial(num):
    fac = 1
    if num > 0:
       return num * factorial(num - 1)

    else:
        return 1
    
result = factorial(10)
print(f'10!: {result}')

6_024

# 재귀 알고리즘을 이용한 최대 공약수 계산
# 유클리드 호제법:
# 두 자연수 n1, n2에 대하여 (n1 > n2)n1를 n2로 나눈 나머지를 r이라고 할 때,
# n1과 n2의 최대공약수는 n2와 r의 최대공약후와 같다.
def gcd(n1, n2):
    if n1 % n2 == 0:
        return n2
    else:
        print(n1, n2)
        return gcd(n2, n1 % n2)

n1 = int(input('n1: '))
n2 = int(input('n2: '))

print(f'gcd({n1}, {n2}): {gcd(n1, n2)}')

6_025

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

6_026

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

6_027

# 병합정렬: 자료구조를 분할하고 각각의 분할된 자료구조를 장렬한 후 다시 병합하여 정렬한다.
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)}')

6_028

# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
# 요구사항1) 병합정렬 알고리즘을 이용한 난수 정렬 모듈 구현
# 요구사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가
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)}')



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

6_029

# 퀵정렬: 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
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))

6_030

# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
# 요구사항1) 퀵정렬 알고리즘을 이용한 난수 정렬 모듈 구현
# 요구사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가

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.qSort(rNums)}')
print(f'sorted rNums DESC: {sm.qSort(rNums, asc=False)}')



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)