06_010 삽입 정렬

1부터 1000까지의 난수 100개 생성

1 - 생성된 난수들 오름 차순, 내림 차순 정렬하는 알고리즘 구현

2 - 생성된 난수 중 최솟값, 최댓값 반환하는 함수 구현

sortMod.py

class SortNumbers:

def __init__(self, ns, asc=True):  # 생성자 / asc -> 오름 / 내림차순 판별
    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]
    
    

insertSortEx.py

import random
import sortMod as sm

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

객체 생성

sn = sm.SortNumbers(nums)

ascending

sn.setSort()
sortedNumber = sn.getSortedNumbers()
print(f'sortedNumber by ASC: {sortedNumber}')

descending

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

min & max

print(f'MinNumber : {sn.getMinNumber()}')
print(f'MaxNumber : {sn.getMaxNumber()}')

06_011 선택정렬 - 가장 작은 데이터를 찾아 자리를 바꾸기

selectionSort

nums = [4, 2, 5, 1, 3]
print(f'nums 처음: {nums}')
for i in range(len(nums)-1): # 끝까지 안가도 됨, 끝에서 하나 앞까지만 / 렌지4 이면 인덱스 0, 1, 2, 3 까지만
minIdx = i

for j in range(i+1, len(nums)): # i보다 한 칸뒤부터, 끝까지
	if nums[minIdx] > nums[j]: # 뒷 숫자가 더 작으면 
		minIdx = 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'nums 파이널: {nums}')

06_012 선택정렬 실습

sortMod.py

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):
        maxIdx = i

        for j in range(i + 1, len(ns)):
            if ns[maxIdx] < ns[j]:
                maxIdx = j

        ns[i], ns[maxIdx] = ns[maxIdx], ns[i]

return ns

def sortNumber(ns, asc=True):

cnt = 0

for i in range(len(ns) - 1):
    targetIdx = i

    for j in range(i + 1, len(ns)):
        if asc:
            if ns[targetIdx] > ns[j]:
                targetIdx = j
                cnt += 1
        else:
            if ns[targetIdx] < ns[j]:
                targetIdx = j
                cnt += 1

    ns[i], ns[targetIdx] = ns[targetIdx], ns[i]

print(f'cnt: {cnt}')

return ns

selectionSortEx.py

import random
import sortMod as sm
import copy

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

ascending

result = sm.sortNumber(scores)

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

descending

result = sm.sortNumber(scores, asc=False)

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

06_013 최댓값 - 가장 큰 값 찾기

max

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

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

ma = MaxAlgorithm(['c', 'x', 'Q', 'A', 'e', 'P', 'p'])
maxChar = ma.getMaxChar()
print(f'maxChar: {maxChar}')

06_015 최솟값

min

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, -100, 0, 8, 20, -11])
minNum = ma.getMinNum()
print(f'minNum: {minNum}')

06_016 최솟값 실습 454

minEx

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

06_017 최빈값 / 빈도수가 가장 높은 데이터 찾기

mode.py

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 getMaxNumIdx(self):
    return self.maxNumIdx;

nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]

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

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

06_018 최빈값 실습

maxScore.py

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 getMaxNumIdx(self):
    return self.maxNumIdx;
  
  

modeEx

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

if maxNum == 0:
    break

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

n += 1

06_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: {nearNum}')

06_020 근삿값 실습

near.py

def getNearNum(an):
baseScore = [95, 85, 75, 65, 55]
nearNum = 0
minNum = 100

for n in baseScore:
    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(f'totalScore: {totalScore}')

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

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

06_021 평균

import random

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

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

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

50이상 90이하 수들의 평균

import random

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

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

print(f'targetNums: {targetNums}')
average = total / len(targetNums)
print(f'average: {round(average, 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 - int(n) == 0:
total += n
targetNums.append(n)

print(f'targetNums: {targetNums}')
average = total / len(targetNums)
print(f'average: {round(average, 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 - int(n) != 0:
total += n
targetNums.append(n)

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

06_022 평균 실습

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(f'Current scores: {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()
top5PlayerScores = tp.getFinalTop5Scores()
print(f'Final scores: {top5PlayerScores}')

near.py

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

    # print(f'nearIdx: {nearIdx}')
    # print(f'nearScore: {nearScore}')

    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+1] = self.newScore

    # print(f'self.currentScores: {self.currentScores}')

def getFinalTop5Scores(self):
    return self.currentScores
  
  

06_023 재귀알고리즘 / 나 자신을 다시 호출하자

def recusion(num):

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

recusion(10)

def factorial(num):

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

print(f'factorial(10): {factorial(10)}')

06_024 재귀 알고리즘(실습)

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

return maxNum

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

재귀함수

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

06_025 하노이의 탑

원판을 다른 기둥으로 옮기는 게임

06_026 하노이의 탑 실습

def moveDisc(discCnt, fromBar, toBar, viaBar): # 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
if discCnt == 1:
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')

else:
    moveDisc(discCnt-1, fromBar, viaBar, toBar)              # (discNo-1)개들을 경유 기둥으로 이동
    print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!') # discNo를 목적 기둥으로 이동
    moveDisc(discCnt-1, viaBar, toBar, fromBar)              # (discNo-1)개들을 도착 기둥으로 이동

moveDisc(3, 1, 3, 2)

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

mergedNums = []
leftIdx = 0; rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
    if leftNums[leftIdx] < rightNums[rightIdx]:
        mergedNums.append(leftNums[leftIdx])
        leftIdx += 1
    else:
        mergedNums.append(rightNums[rightIdx])
        rightIdx += 1

mergedNums = mergedNums + leftNums[leftIdx:]
mergedNums = mergedNums + rightNums[rightIdx:]
print(f'mergedNums: {mergedNums}')
return mergedNums

nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mergedNums: {mSort(nums)}')

06_028 병합 정렬

sortMod.py

def mSort(ns):
if len(ns) < 2:
return ns

midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx])
rightNums = mSort(ns[midIdx:len(ns)])

mergedNums = []
leftIdx = 0; rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
    if leftNums[leftIdx] < rightNums[rightIdx]:
        mergedNums.append(leftNums[leftIdx])
        leftIdx += 1
    else:
        mergedNums.append(rightNums[rightIdx])
        rightIdx += 1

mergedNums = mergedNums + leftNums[leftIdx:]
mergedNums = mergedNums + rightNums[rightIdx:]
return mergedNums

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)

mergedNums = []
leftIdx = 0; rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):

    if asc:

        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergedNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergedNums.append(rightNums[rightIdx])
            rightIdx += 1

    else:

        if leftNums[leftIdx] > rightNums[rightIdx]:
            mergedNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergedNums.append(rightNums[rightIdx])
            rightIdx += 1

mergedNums = mergedNums + leftNums[leftIdx:]
mergedNums = mergedNums + rightNums[rightIdx:]
return mergedNums

if name == 'main':
nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'merge sorted nums: {mSort(nums)}')
print(f'merge sorted nums: {mSort(nums, asc=False)}')

mergeEx.py

import random as rd
import sortMod as sm

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

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

06_030 퀵정렬

sortMod

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)

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)

if name == 'main':
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(f'quick sorted nums: {qSort(nums)}')
print(f'quick sorted nums: {qSort(nums, asc=False)}')

quickEx.py

import random as rd
import sortMod as sm

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