[제로베이스] 4주차_알고리즘(문풀) 02

📌2/24 영상강의 6＿034 ~ 6＿042

🖥️ 버블 알고리즘을 이용해 오름차순, 내림차순으로 정렬하는 모듈을 만들어보자

#모듈

import copy

def bubbleAlgiruthm(ns,asc = True):

    c_ns = copy.copy(ns)
    length = len(c_ns)-1

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

                print(f'sorted nums :\t {c_ns}')
            print()

    else:
        for i in range(length):
            for j in range(length - i):
                if c_ns[j] < c_ns[j + 1]:
                    c_ns[j], c_ns[j + 1] = c_ns[j + 1], c_ns[j]

                print(f'sorted nums :\t {c_ns}')
            print()

    return c_ns


#실행부

import random as rd
import bubbleMod as bm

if __name__=='__main__':

    nums = rd.sample(range(1,21),10)
    print(f'not sorted nums :{nums}')

    result = bm.bubbleAlgiruthm(nums)
    print(f'sorted results ASC : {result}')
    result = bm.bubbleAlgiruthm(nums,asc=False)
    print(f'sorted results DESC : {result}')
    

• 중첩 for문 사용. 두번째 for문의 범위는 첫번째 for문에서 i를 뺀 만큼이다.
  마지막 비교는 끝 vs 끝-1 이므로

🖥️ 선택 정렬 알고리즘을 이용해 난수 10개를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자 (단, 정렬하는 과정도 출력하도록 한다)

#모듈

import copy

def selectAlgorithm(ns,asc=True):
    c_ns = copy.copy(ns)

    for i in range(len(c_ns)-1):
        minIdx = i

        for j in range(i+1,len(c_ns)):

            if asc:
                if c_ns[minIdx] > c_ns[j]:
                    minIdx = j

            else:
                if c_ns[minIdx] < c_ns[j]:
                    minIdx = j

        c_ns[i], c_ns[minIdx] = c_ns[minIdx], c_ns[i]
        print(f'nums:{c_ns}')

    return c_ns



실행부
import random as rd
import selectMod as sm

if __name__=='__main__':

    nums = rd.sample(range(1,21),10)
    print(f'not sorted nums:{nums}')
    print(f'sorted ASC : {sm.selectAlgorithm(nums)}')
    print()
    print(f'sorted DESC : {sm.selectAlgorithm(nums,asc=False)}')

• 앞부터 차례대로 본인을 키값으로 잡고 이후의 나머지 숫자중 최솟값과 자리바꿈한다.
  최솟값이 차곡차곡 앞으로 정렬된다.

🖥️1~100까지 난수 20개를 병합정렬 알고리즘을 이용해 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자
(정렬 과정도 출력한다)

#모듈

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)
    print(f'mergedNums:{ns}')
    print(f'leftNums:{leftNums},rightNums:{rightNums}')

    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 += leftNums[leftIdx:] ⭐
    mergedNums += rightNums[rightIdx:]

    print(f'mergedNums:{mergedNums}')
    return mergedNums
   
   
#실행부

import random as rd
import mergeMod as mm

if __name__=='__main__':
    nums = rd.sample(range(1,101),20)
    print(f'not sorted nums : {nums}')

    result = mm.mSort(nums)
    # print(f'result mergedNums:{result}')
    print()
    print(f'result mergedNums DESC:{mm.mSort(nums,asc = False)}')

• 리스트의 아이템을 1개로 분할 후 왼쪽 오른쪽으로 나눠서 비교하며 다시 병합한다
  기존 리스트를 1개로 쪼갤때 재귀함수 사용한다.
• ⭐연산이 끝난 후 꼬옥 leftNums,rightNums에 남아있는 아이템을 mergedNums에 붙여준다

🖥️ 1~50까지 난수 30개를 최댓값 알고리즘을 이용해 최댓값과 최댓값의 개수를 찾아보자

#모듈

class MaxALgorithm:

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

    def setMaxNum(self):
        for n in self.nums:
            if n > self.maxNum:
                self.maxNum = n


    def getMaxNum(self):
        self.setMaxNum()
        return self.maxNum

    def setMaxNumCnt(self):
        self.setMaxNum()

        for n in self.nums:
            if n == self.maxNum:
                self.maxNumCnt += 1

    def getMaxNumCnt(self):
        self.setMaxNumCnt()
        return self.maxNumCnt
        
        
#실행부
import random as rd
import maxMod as mm

if __name__=='__main__':
    nums = []
    for i in range(50):
        nums.append(rd.randint(1,30))

    print(f'nums:{nums}')
    ma = mm.MaxALgorithm(nums)
    print(f'max num : {ma.getMaxNum()}')
    print(f'max num count : {ma.getMaxNumCnt()}')

• 난수 발생시 중복될 수 있게 하려면 for문으로 난수를 뽑고 append로 난수리스트를 만든다

🖥️ 최근 30회차 로또번호를 가지고 최빈도 알고리즘을 이용해 모든 회차의 각 번호에 대한 빈도수를 출력해보자.

#모듈
class LottoMod:

    def __init__(self,ln):
        self.lottoNums = ln
        self.modList = [0 for n in range(1,47)]

    def getLottoNumMod(self):

        for roundNum in self.lottoNums:
            for num in roundNum:
                self.modList[num] = self.modList[num] + 1

        return self.modList

    def printLotto(self):

        if sum(self.modList) == 0:
            return None


        for i, n in enumerate(self.modList):
            if i != 0:
                print(f'번호 : {i:>2}, 빈도 : {n}, {"*"*n}')
                
                
#실행부
import mod

lottoNums = [[13, 23, 15, 5, 6, 39], [36, 13, 5, 3, 30, 16], [43, 1, 15, 9, 3, 38],
             [32, 42, 24, 45, 8, 31], [18, 39, 41, 11, 4, 9], [12, 39, 11, 38, 32, 5],
             [29, 25, 13, 6, 14, 8], [21, 33, 19, 20, 42, 7], [6, 28, 3, 45, 41, 24],
             [42, 15, 8, 5, 35, 4], [14, 4, 35, 24, 29, 3], [15, 20, 6, 37, 34, 39],
             [27, 5, 32, 15, 25, 19], [45, 25, 2, 8, 30, 43], [4, 19, 33, 10, 6, 24],
             [25, 26, 45, 23, 24, 16], [33, 28, 45, 21, 38, 24], [4, 30, 29, 28, 32, 38],
             [11, 28, 12, 2, 42, 3], [40, 29, 16, 8, 9, 28], [6, 9, 37, 30, 3, 35],
             [29, 18, 41, 28, 38, 15], [9, 31, 13, 44, 1, 36], [36, 1, 37, 32, 15, 12],
             [41, 32, 16, 6, 26, 33], [12, 43, 10, 29, 39, 9], [41, 9, 23, 35, 18, 17],
             [35, 38, 3, 28, 36, 31], [21, 44, 4, 29, 18, 7], [20, 23, 6, 2, 34, 44]]

lm = mod.LottoMod(lottoNums)
lm.getLottoNumMod()
lm.printLotto()

• 빈도수를 표시하기 위한 0만 있는 리스트의 맨 처음 0은 쓰임이 없다. 왜냐하면 로또번호에 0번이 없기 때문이디.
• print(f'{ i : > 2 }') -> i를 출력할 때 두자릿수 오른쪽 정렬로 보여준다

🖥️ 1~50까지의 난수 30개를 발생시켜 최솟값 알고리즘을 이용해 최솟값과 최솟값의 개수를 찾는 모듈을 만들어보자.

#모듈

class MinAlgorithm:

    def __init__(self,ns):
        self.nums = ns
        self.minNum = 0
        self.minNumCnt = 0

    def setMinNum(self):
        for n in self.nums:
            if n > self.minNum:
                self.minNum = n

    def getMinNum(self):
        self.setMinNum()
        return self.minNum

    def getMinNumCnt(self):
        self.setMinNum()

        for i in self.nums:
            if i == self.minNum:
                self.minNumCnt += 1

        return self.minNumCnt
        

#실행부

import random as rd
import minMod as mm

if __name__=='__main__':

    nums = []
    for i in range(30):
        nums.append(rd.randint(1,50))
    print(f'nums:{nums}')

    mn = mm.MinAlgorithm(nums)

    print(f'min num : {mn.getMinNum()}')
    print(f'min num cnt :{mn.getMinNumCnt()}') 

🖥️ 다음 표를 보고 재귀 알고리즘을 이용해 1월부터 12월까지 전월대비 매출 증감액을 표시해보자

sales = [1200, 1300, 12500, 11000, 10500, 98000, 91000, 10500, 11500, 12000, 12500]

def salesUpAndDown(ss):
    if len(ss) == 1:
        return ss

    print(f'sales : {ss}')
    currentSales = sales.pop(0)
    nextSales = ss[0]

    increase = nextSales - currentSales
    if increase > 0:
        increase = '+' + str(increase)
    print(f'매출 증감액 : {increase}')
    
    return salesUpAndDown(ss)


if __name__ == '__main__':
    salesUpAndDown(sales)

• pop()함수로 맨 처음 데이터를 빼내서 할당한다 .
• 재귀함수가 멈춰야 할 지점을 조건으로 걸어준다
• 문자 + 숫자는 불가능 하므로 숫자를 문자열로 캐스팅해서 덧셈한다.

마무리
분명 배웠는데 도통 기억이 나질 않는다... 넘 어렵다 헝
주말에 EDA를 시작해야하는데 가능하려남