12_알고리즘2

📌최빈값

class maxAlgorithm:

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


    def setMaxNumAndInd(self):
        self.maxNum = self.nums[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]

maxAlgo = maxAlgorithm(nums)
maxAlgo.setMaxNumAndInd()
maxNum = maxAlgo.getMaxNum()
print(f'maxNum: {maxNum}')


indexes = [0 for i in range(maxNum + 1)]
for n in nums:
    indexes[n] = indexes[n] + 1
print(f'indexes: {indexes}')


ma= maxAlgorithm(indexes)
ma.setMaxNumAndInd()
maxNum = ma.getMaxNum()
maxNumIdx = ma.getMaxNumIdx()

print(f'최반값: {maxNumIdx}, 횟수: {maxNum}')

결과:
maxNum: 17
indexes: [0, 1, 0, 1, 0, 0, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
최반값: 7, 횟수: 4

---

📌근삿값

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)

    if absNum < minNum:
        minNum = absNum
        nearNum = n

print(f'nearNum: {nearNum}')

결과:
nums: [29, 16, 23, 25, 13, 45, 43, 17, 34, 6, 28, 10, 36, 49, 8, 9, 39, 21, 33, 38]
input number: 5
inputNum: 5
nearNum: 6

---

📌평균

import random

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

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

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




#50 이상 90이하의 평균
import random
nums = random.sample(range(0, 100), 30)
print(f'nums: {nums}')

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

average = total / len(targetNums)
print(f'targetNums: {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)
average = total / len(targetNums)
print(f'targetNums: {targetNums}')
print(f'average: {round(average, 2)}')

결과:
nums: [59, 27, 81, 77, 76, 39, 80, 44, 94, 97]
average: 67.4

nums: [94, 45, 27, 6, 17, 4, 49, 88, 5, 71, 75, 25, 58, 32, 63, 97, 24, 56, 99, 93, 98, 40, 61, 96, 69, 33, 90, 10, 67, 35]
targetNums: [88, 71, 75, 58, 63, 56, 61, 69, 90, 67]
average: 69.8

nums: [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
targetNums: [4, 0, 5, 9, 3, 1, 11]
average: 4.71

---

📌재귀

재귀 : 나 자신을 다시 호출하는 것

def recusion(num):

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

recusion(4)


# 10! 구하기
def factorial(num):

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

print(factorial(10))

결과:
@@@@
@@@
@@
@

3628800

---

📌하노이탑

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

결과:
1disc를 1에서 3(으)로 이동!
2disc를 1에서 2(으)로 이동!
1disc를 3에서 2(으)로 이동!
3disc를 1에서 3(으)로 이동!
1disc를 2에서 1(으)로 이동!
2disc를 2에서 3(으)로 이동!
1disc를 1에서 3(으)로 이동!

---

📌병합정렬

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

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(mSort(nums))

결과:
[1, 2, 3, 4, 5, 6, 8, 10]

---

📌퀵정렬

퀵정렬 : 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.

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

결과:
[1, 2, 3, 4, 4, 5, 6, 8, 8, 10]