Python 알고리즘Ⅱ

최댓값

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

nums = [-2,-4,5,7,10,0,8,20,-11]

maxN = 0
for i in range(len(nums)):
    if maxN < nums[i]:
        maxN = nums[i]
        
print (maxN)	# 결과: 20

최소값

• 자료 구조에서 가장 작은 값을 찾는다.

class MinAlgorithm:
    def __init__(self, ns):
        self.nums = ns
        self.minNum = 0
        
    def getMinimum(self):
        self.minNum = self.nums[0]
        
        for i in self.nums:
            if self.minNum > i:
                self.minNum = i
                
        return self.minNum
    
nums = [-2,-4,5,7,10,0,8,20,-11]
numsClass = MinAlgorithm(nums)

print (numsClass.getMinimum()) # 결과 : -11

최빈값

• 데이터에서 빈도수가 가장 많은 데이터를 의미
• 가장 큰 수만큼의 N개의 0으로 구성된 리스트를 생성하여
  숫자를 인덱스화한 후 갯수를 센다.

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

class MaxAG:
    def __init__(self, nums):
        self.nums = nums
        
    def getMax(self):
        self.maxN = self.nums[0]
    
        for i,v in enumerate(self.nums):
            if self.maxN < v:
                self.maxN = v
                self.maxIdx = i
                
    def printOutMaxNum(self):
        return self.maxN
    
    def printOutMaxNumIdx(self):
        return self.maxIdx
    

numsClass = MaxAG(nums)
numsClass.getMax()
maxN = numsClass.printOutMaxNum()

#가장 큰 수만큼의 N개의 0으로 구성된 리스트를 생성
temp = [0 for i in range(maxN+1)]
for i in nums:
    temp[i] += 1
    
tempClass = MaxAG(temp)
tempClass.getMax()
print('최빈값은 %d, 빈도수는 %d' % (tempClass.printOutMaxNumIdx(), tempClass.printOutMaxNum()))
# 최빈값은 7, 빈도수는 5

근삿값

• 특정 값에 가장 가까운 값을 의미

nums = [7,43,14,44,6,26,24,3,25,47,2,32,27,38,18,17,33,29,28,0]

n = int(input("정수 입력: "))	#정수 입력: 11

obj = 0
temp = 100
for i in nums:
    if (n - i) > 0:
        gap = n - i
    else:
        gap = i - n
        
    if temp > gap:
        obj = i
        temp = gap

        
print ('근삿값: {} (차이: {})'.format(obj,temp))	#근삿값: 14 (차이: 3)

평균

• 데이터의 중간 값을 갖는 수

재귀

• 나 자신을 다시 호출하는 것
  

def recalling (n):
    if n > 0:
        print ('*'*n)
        return recalling(n-1)

    else:
        return 1
        
#------ 결과물 --------#
*****
****
***
**
*

하노이의 탑 ★★★★★

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

병합 정렬

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

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:] + rightNums[rightIdx:]
    
    return mergeNums

퀵 정렬

• 기준 값보다 작은 값과 큰값으로 분리한 후 다시 합친다.
  

def qickSort(ns):
    
    if len(ns) < 2:
        return ns
    
    midIdx = len(ns) // 2
    midV = ns[midIdx]
    
    smallList = []
    sameList = []
    bigList = []
    for i in ns:
        if i < midV:
            smallList.append(i)
        elif i == midV:
            sameList.append(i)
        else:
            bigList.append(i)
    
    return qickSort(smallList) + sameList + qickSort(bigList)

➰혼잣말

• 쉬운데?! 했다가도 혼자 코딩해보면 몇 시간이 걸리기 일쑤다...
• 하노이의 탑 어쩔거야! 병합 정렬 어쩔거야!!