python - 알고리즘 2 : 데이터 취업 스쿨 스터디 노트 11/21

🔱최댓값, 최솟값

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

maxNum = numbers[0]

for num in numbers:
    if num > maxNum:
        maxNum = num

print(f'최댓값: {maxNum}')

>>>
최댓값: 20

반대로 하면 최솟값을 구할 수 있다.

🔱최빈값 mode

def maxNumber(list):
    maxNum = list[0]
    maxNumIdx = 0
    
    for idx, value in enumerate(list):
        if maxNum < value:
            maxNum = value
            maxNumIdx = idx

    return maxNumIdx, maxNum

numbers = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxNum = maxNumber(numbers)[1]
indexes = [0] * (maxNum + 1)

for num in numbers:
    indexes[num] += 1
    
mode = maxNumber(indexes)[0]
modeCnt = maxNumber(indexes)[1]

print(f'최빈값: {mode} ({modeCnt}회)')

>>>
최빈값: 7 (4회)

최빈값 문제 풀이

지금까지 다양한 문제들을 풀면서 어떤 경우에 클래스를 만드는 게 좋은지 아리송했는데, 이번 문제를 풀면서 조금 이해가 되었다.

⭐maxNum,maxNumIdx 값이 가지는 의미를 잘 생각해야 한다.

class MaxAlgotirhm:
    
    def __init__(self, list):
        self.numbers = list
        self.maxNum = 0
        self.maxNumIdx = 0
    
    def setMaxNum(self):
        for idx, value in enumerate(self.numbers):
            if self.maxNum < value:
                self.maxNum = value
                self.maxNumIdx = idx
    
    def getMaxNum(self):
        return self.maxNum
    
    def getMaxNumIdx(self):
        return self.maxNumIdx


import random

scores = []
for i in range(100):
    rNum = random.randint(71, 100)
    if rNum != 100: rNum = rNum - (rNum % 5)
    scores.append(rNum)
print(f'scores: {scores}')

# 최댓값 구하기
maxAlo = MaxAlgotirhm(scores)
maxAlo.setMaxNum()
maxNum = maxAlo.getMaxNum()
print(f'maxNum: {maxNum}')

# 인덱스 리스트
indexes = [0 for i in range(maxNum + 1)]
for score in scores:
    indexes[score] += 1
print(f'indexes: {indexes}')

# 빈도수 출력
n = 1
while True:
    maxAlo = MaxAlgotirhm(indexes)
    maxAlo.setMaxNum()
    maxNum = maxAlo.getMaxNum()
    maxNumIdx = maxAlo.getMaxNumIdx()

    if maxNum == 0: break

    print(f'{n}: {maxNumIdx}({maxNum}회)', '+' * maxNum)

    # 다음으로 많은 수로 넘어가기 위해
    indexes[maxNumIdx] = 0
    n += 1

>>>
scores: [100, 90, 75, 95, ...]
maxNum: 100
indexes: [..., 21, ... , 16, ... , 15, ... , 17, ... , 19, ... , 2]
1: 75(21회) +++++++++++++++++++++
2: 95(19회) +++++++++++++++++++
3: 90(17회) +++++++++++++++++
4: 80(16회) ++++++++++++++++
5: 85(15회) +++++++++++++++
6: 70(10회) ++++++++++
7: 100(2회) ++

🔱근삿값

근삿값은 특정 값(참 값)에 가장 가까운 값이다.

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

# 편차를 계산해서 리스트에 넣기
number = 11
absSub = [0] * len(numbers)

for idx, num in enumerate(numbers):
    absSub[idx] = abs(number - num)

# 편차가 가장 작은 값 구하기
minSub = absSub[0]
minSubIdx = 0

for idx, sub in enumerate(absSub):
    if minSub > sub:
        minSub = sub
        minSubIdx = idx

print(f'{number}의 근삿값: {numbers[minSubIdx]}')
print(f'편차: {minSub}')

>>>
11의 근삿값: 14
편차: 3

근삿값 문제 풀이

def approximative(avg):
    baseScores = {95: 'A', 85: 'B', 75: 'C', 65: 'D', 55: 'F'}
    minSub = 0
    result = ''
    
    for key, value in baseScores.items():
        absSub = abs(key - avg)
        if minSub == 0 or absSub < minSub:
            minSub = absSub
            result = value
        
    return result
        
scores = [75, 72, 80, 84, 85]

totalScore = sum(scores)
avgScore = totalScore / len(scores)
result = approximative(avgScore)

print(f'평균: {avgScore}')
print(f'최종 학점: {result}')

>>>
평균: 79.2
최종 학점: C

🔱평균

평균은 간단히 구할 수 있어서 다른 개념이 추가된 문제를 풀었다.

def setRankTop5(currentScores, newScore):
    nearIdx = 0
    minSub = 0
    
    for idx, score in enumerate(currentScores):
        absSub = abs(newScore - score)
        if minSub == 0 or absSub < minSub:
            minSub = absSub
            nearIdx = idx
    
    if newScore >= currentScores[nearIdx]:
        currentScores.insert(nearIdx, newScore)
    else:
        currentScores.insert(nearIdx+1, newScore)
    
    return currentScores[:5]

# 나의 최종 점수 구하기
myScores = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
myscore = round(sum(myScores) / len(myScores), 3)

# 현재 TOP5
scores = [9.12, 8.95, 8.12, 7.90, 7.88]
print(f'Top 5: {scores}')

# 새로운 TOP5
scores = setRankTop5(scores, myscore)
print(f'나의 점수: {myscore}')
print(f'new Top 5: {scores}')

>>>
Top 5: [9.12, 8.95, 8.12, 7.9, 7.88]
나의 점수: 8.39
new Top 5: [9.12, 8.95, 8.39, 8.12, 7.9]

🔱재귀

똑같은 과정을 반복하는 때에 사용하면 편리하다.

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

recursior(5)

>>>
*****
****
***
**
*

유클리드 호제법

계산 과정을 써보고 함수를 만드니까 한결 수월하다.

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

>>>
gcd(82, 32): 2
gcd(96, 40): 8

🔥하노이의 탑(재귀 함수 이용)

# 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def hanoi(diskCnt, fromBar, toBar, viaBar):
    if diskCnt == 1:
        print(f'{diskCnt}번 원판: {fromBar} -> {toBar}')

    else:
        # diskCnt-1개를 경유 기둥으로 이동
        hanoi(diskCnt-1, fromBar, viaBar, toBar)
        
        # diskCnt를 도착 기둥으로 이동
        print(f'{diskCnt}번 원판: {fromBar} -> {toBar}')
        
        # diskCnt-1개를 도착 기둥으로 이동
        hanoi(diskCnt-1, viaBar, toBar, fromBar)

hanoi(3, 1, 3, 2)

>>>
1번 원판: 1 -> 3
2번 원판: 1 -> 2
1번 원판: 3 -> 2
3번 원판: 1 -> 3
1번 원판: 2 -> 1
2번 원판: 2 -> 3
1번 원판: 1 -> 3

hanoi(3, 1, 3, 2)

⭐가장 긴 원판 제외한 나머지 원판을 경유 기둥으로 이동
else_1 : hanoi(2, 1, 2, 3)
    else_1 : hanoi(1, 1, 3, 2)
        if : 1번 원판 1 ➡ 3
    else_2 : 2번 원판 1 ➡ 2
    else_3 : hanoi(1, 3, 2, 1)
        if : 1번 원판 3 ➡ 2
        
⭐가장 긴 원판을 도착 기둥으로 이동
else_2 : 3번 원판 1 ➡ 3

⭐나머지 원판을 도착 기둥으로 이동
else_3 : hanoi(2, 2, 3, 1)
    else_1 : hanoi(1, 2, 1, 3)
        if : 1번 원판 2 ➡ 1
    else_2 : 2번 원판 2 ➡ 3
    else_3 : hanoi(1, 1, 3, 2)
        if : 1번 원판 1 ➡ 3

🔥🔥🔥병합 정렬(재귀 함수 이용)

자료구조를 분할하고, 분할된 자료구조를 정렬한 후 다시 병합하는 방법이다.
스스로 설명할 수 있을 때까지 보고 또 봐야겠다.😂

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


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

>>>
not sorted rNums: [18, 90, 98, 72, 65, 45, 22, 38, 63, 40]
sorted rNums ASC: [18, 22, 38, 40, 45, 63, 65, 72, 90, 98]
sorted rNums DESC: [98, 90, 72, 65, 63, 45, 40, 38, 22, 18]

🔥🔥퀵 정렬(재귀 함수 이용)

기준 값보다 작은 값, 큰 값으로 분리한 후 다시 합치는 방법이다.

def qSort(ns, asc=True):
    
    if len(ns) < 2:
        return ns
    
    # 기준 값 지정
    midIdx = len(ns) // 2
    midValue = ns[midIdx]
    
    # 작은 값, 큰 값으로 분리
    smallNums = []
    sameNums = []
    bigNums = []
    
    for n in ns:
        if n < midValue:
            smallNums.append(n)
        elif n == midValue:
            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)
        

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

>>>
not sorted rNums: [55, 27, 7, 88, 60, 95, 68, 72, 93, 39]
sorted rNums ASC: [7, 27, 39, 55, 60, 68, 72, 88, 93, 95]
sorted rNums DESC: [95, 93, 88, 72, 68, 60, 55, 39, 27, 7]