[4주차1일차] Chapter 06_알고리즘 알고리즘4

최솟값

최솟값

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

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

nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]
ma = MinAlgorithm(nums)
minNum = ma.getMinNum()
print(f'minNum: {minNum}')

# 결괏값:
minNum: -11

최솟값(실습)

최솟값

리스트에서 아스키코드가 가장 작은 갑승ㄹ 찾는 알고리즘을 만들어보자.

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

 # 결괏값:
minChar: A

최빈값

최빈값

데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다.

cf) index리스트를 만들고 nums리스트의 최댓값만큼 0의 개수를 설정함. 해당하는 인덱스에 +1
ex) nums가 '7'이면 사전에 최댓값의 개수만큼 0으로 설정해두었던 indexs 리스트에서 인덱스가 7인 곳에 +1

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, 5, 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 # 인덱스값에 +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}로 가장 높다.')

결괏값:

indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
indexes length: 18
indexes: [0, 1, 0, 1, 0, 1, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
maxNum: 4
maxNumIdx: 7
즉, 7의 빈도수가 4로 가장 높다.

최빈값(실습)

실습

최빈값 알고리즘을 이용해서 학생 100명의 점수 분포를 다음과 같이 나타내보자.

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.setMaxNumberAndNum()
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.setMaxNumberAndNum()
    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

결괏값:

scores: [90, 70, 75, 70, 75, 75, 70, 70, 80, 90, 95, 95, 90, 75, 85, 75, 85, 70, 90, 95, 80, 80, 75, 70, 75, 75, 75, 70, 85, 80, 95, 90, 95, 80, 70, 70, 80, 95, 75, 75, 85, 95, 75, 80, 70, 90, 90, 90, 75, 80, 70, 90, 75, 85, 75, 70, 70, 75, 80, 70, 80, 80, 80, 75, 80, 100, 90, 85, 75, 85, 90, 90, 70, 75, 80, 90, 90, 90, 80, 75, 80, 70, 70, 85, 80, 85, 100, 80, 95, 80, 80, 85, 75, 75, 80, 95, 90, 80, 80, 80]
scores length: 100
maxNum: 100
indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
indexes length: 101
indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 22, 0, 0, 0, 0, 24, 0, 0, 0, 0, 10, 0, 0, 0, 0, 16, 0, 0, 0, 0, 9, 0, 0, 0, 0, 2]
1. 80빈도수: 24	++++++++++++++++++++++++
2. 75빈도수: 22	++++++++++++++++++++++
3. 70빈도수: 17	+++++++++++++++++
4. 90빈도수: 16	++++++++++++++++
5. 85빈도수: 10	++++++++++
6. 95빈도수: 9	+++++++++
7. 100빈도수: 2	++