Ch3 알고리즘 01-24 (알고리즘1-5)

알고리즘 : 문제를 풀어나가는 절차

1. 선형 검색

• 선형(일렬)으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾음

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1

n = 0
while True:
    if n == len(datas):
        searchResultIdx = -1
        break
    elif datas[n] == searchData:
        searchResultIdx = n
        break
    n += 1

print(f'searchResultIdx: {searchResultIdx}')

• 보초법 : 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화함
  -> 만약 찾아낸 인덱스값이 맨 끝 인덱스라면, 그 숫자는 그 전까지 한 개도 없었다는 뜻
  -> 마지막 인덱스 이전에 검색됐다면, 찾는 숫자가 이미 있었다는 뜻

datas.append(searchData)         # 찾으려는 숫자를 데이터 맨 끝에 넣기

n = 0
while True:
    if datas[n] == searchData:
        if n != len(datas) - 1:       # 찾으려는 숫자가 맨 끝 인덱스가 아닐 때
            searchResultIdx = n
        break                      # 같은 숫자를 찾자마자 break함
    n += 1

• 리스트에서 가장 앞에 있는 '7' 인덱스 검색

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')

searchNum = int(input('찾으려는 숫자 입력: '))
searchIdx = -1

nums.append(searchNum)

n = 0
while True:
    if nums[n] == searchNum:
        if n != len(nums) - 1:
            searchIdx = n
        break                      # break 위치 잘 보기!!!
    n += 1

print(f'nums: {nums}')
print(f'nums length: {len(nums)}')

if searchIdx < 0:
    print('not search index')
else:
    print('search index: {}'.format(searchIdx))

• 리스트에 있는 모든 '7'의 인덱스, 개수 검색

def searchNum(tempNums):
    searchNum = int(input('찾으려는 숫자 입력: '))
    searchResultIdxs = []

    tempNums.append(searchNum)

    n = 0
    while True:
        if tempNums[n] == searchNum:
            if n != len(tempNums) - 1:
                searchResultIdxs.append(n)
            else:
                break
        n += 1

    return searchResultIdxs

-> 함수 사용 어렵!!! 복습 제일 필요하다..

2. 이진 검색

• '정렬'되어 있는 자료구조에서 중앙값과의 크고 작음을 이용하여 데이터를 검색함
• 찾으려는 값이 중앙값에서 up,down인지 알아내고 그걸 반복 (검색범위를 점차 좁혀나감)

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('search data: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]

print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')

while searchData >= datas[0] and searchData <= datas[len(datas)-1]:
    if searchData == datas[len(datas)-1]:   # 마지막 데이터일 경우를 따로 정해주지 않으면 무한루프에 빠짐
        searchResultIdx = len(datas) - 1
        break
    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')
    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')
    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: {searchResultIdx}')

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print(f'nums: {nums}')
nums.sort()              # 이진 검색은 '정렬' 필요!!
print(f'nums: {nums}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]

while searchData >= nums[0] and searchData <= nums[len(nums) - 1]:
    if searchData == nums[len(nums) - 1]:
        searchResultIdx = len(nums) - 1
        break
    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
    elif searchData == midVal:
        searchResultIdx = midIdx
        break

3. 순위

• 수의 크고 작음을 이용해서 수의 순서를 정하는 것
• 수끼리 하나하나 비교해서 더 작은 값의 인덱스를 1씩 올려줌(순위는 수가 클수록 작은것)

import random

nums = random.sample(range(50, 101), 20)  # 중복 없이 랜덤뽑기

ranks = [0 for i in range(20)]    # nums 숫자들 순서대로 각각의 순위를 저장

print(f'nums: {nums}')
print(f'ranks: {ranks}')

for idx, num1 in enumerate(nums):
    for num2 in nums:
        if num1 < num2:
            ranks[idx] += 1

print(f'nums: {nums}')
print(f'ranks: {ranks}')

for idx, num in enumerate(nums):
    print(f'nums: {num} \t rank: {ranks[idx]+1}')

• 모듈, 클래스, 함수를 이용하기
• rankModule 코드

class RankDeviation:

    def __init__(self, mss, ess):
        self.midStuScos = mss
        self.endStuScos = ess
        self.midRanks = [0 for i in range(len(mss))]
        self.endRanks = [0 for i in range(len(mss))]
        self.rankDeviation = [0 for i in range(len(mss))]


    def setRank(self, ss, rs):     # 점수, 순위
        for idx, sco1 in enumerate(ss):
            for sco2 in ss:
                if sco1 < sco2:
                    rs[idx] += 1

    def setMidRank(self):
        self.setRank(self.midStuScos, self.midRanks)

    def getMidRank(self):
        return self.midRanks

    def setEndRank(self):
        self.setRank(self.endStuScos, self.endRanks)

    def getEndRank(self):
        return self.endRanks

    def printRankDeviation(self):
        for idx, mRank in enumerate(self.midRanks):
            deviation = mRank - self.endRanks[idx]

            if deviation > 0:
               deviation = '↑' + str(abs(deviation))
            elif deviation < 0:
               deviation = '↓' + str(abs(deviation))
            else:
                deviation = '=' + str(abs(deviation))
            print(f'mid_rank: {mRank} \t end_rank: {self.endRanks[idx]} \t Deviation: {deviation}')

• 실행파일

import rankModule as rm
import random

midStuScos = random.sample(range(50, 101), 20)
endStuScos = random.sample(range(50, 101), 20)

rd = rm.RankDeviation(midStuScos, endStuScos)

rd.setMidRank()
print(f'midStuScos: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')

rd.printRankDeviation()

-> !!!! 다시 보기 !!!!

• abs() : 절댓값 구하기

4. 버블 정렬

• 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘

nums = [10, 2, 7, 21, 0]
print(f'not sortednums: {nums}')

length = len(nums) - 1

for i in range(length):       # 4번 돔
    for j in range(length - i):     # 맨 끝은 제외하고 반복문을 돔
        if nums[j] > nums[j+1]:
            nums[j], nums[j+1] = nums[j+1], nums[j]  # 서로의 값을 바꿈
        print(nums)
    print()
print(f'sorted nums: {nums}')

not sortednums: [10, 2, 7, 21, 0]
[2, 10, 7, 21, 0]
[2, 7, 10, 21, 0]
[2, 7, 10, 21, 0]
[2, 7, 10, 0, 21]    # 가장 큰 21이 맨 끝으로 옴

[2, 7, 10, 0, 21]
[2, 7, 10, 0, 21]
[2, 7, 0, 10, 21]    # 21은 고정시키고, 나머지 중에서 가장 큰 10이 끝으로 옴

[2, 7, 0, 10, 21]
[2, 0, 7, 10, 21]    # 21, 10은 고정, 나머지 세개 숫자 비교

[0, 2, 7, 10, 21]

sorted nums: [0, 2, 7, 10, 21]

• 20명 랜덤 키(중복 있음)를 받아서 정렬하기 (모듈 사용)
• 모듈

import copy

def bubbleSort(ns, deepCopy=True):    # 깊은복사로 하겠다(데이터를 그대로 복사해와서 새로운 걸 만듬)
    if deepCopy:
        cns = copy.copy(ns)           # 가져온 데이터를 사용하지 않고 깊은복사를 한 새로운 데이터를 사용.
    else:
        cns = ns

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

    return cns

import random as rd
import sortModule as sm

students = []

for i in range(20):
    students.append(rd.randint(170, 185))  # 170~185 범위

print(f'students: {students}')

sortedStudents = sm.bubbleSort(students)  # (students, deepCopy=False)를 하면 앝은복사가 됨.

print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')

• 그냥 실행하면 얕은복사가 됨 -> 함수에 사용한 원본데이터가 바뀌어서 나옴!
• 깊은복사로 바꾸어주면 -> 원본데이터는 그대로 유지한채, 데이터를 복사한 새로운 데이터를 함수에 사용

5. 삽입 정렬

• 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾음
• 정렬이 되어 있는 앞 데이터와 비교해서 자신의 삽입 위치를 찾아 들어감

nums = [5, 10, 2, 1, 0]

for i1 in range(1, len(nums)):       # 인덱스1부터 시작(맨앞 데이터는 이동하지X)
    i2 = i1 - 1
    cNum = nums[i1]

    while nums[i2] > cNum and i2 >= 0:    # cNum이 앞 정렬되어 있는 데이터들과 순차적으로 하나씩 비교되어야 함. i2는 앞에 있는 비교대상 데이터므로 인덱스 0이상이어야만 함. 내림차순은 '<'로만 바뀌면 됨
        nums[i2+1] = nums[i2]            # 앞 데이터를 그 다음데이터에 할당 
        i2 -= 1                    # 인덱스를 점점 앞으로 이동해가며 비교

    nums[i2+1] = cNum         # ?? 여길 아직 이해 못 함!!

print(f'nums: {nums}')

nums: [5, 10, 2, 1, 0]     # 5,10은 이미 정렬되어있으니 2부터 위치를 바꿈
nums: [2, 5, 10, 1, 0]
nums: [1, 2, 5, 10, 0]
nums: [0, 1, 2, 5, 10]

-> 어려움!!!!!

• 모듈 만들어서 사용하기
• sortMod 모듈

class SortNumbers:

    def __init__(self, ns, asc=True):
        self.nums = ns
        self.isAsc = asc

    def isAscending(self, flag):
        self.isAsc = flag

    def setSort(self):

        for i1 in range(1, len(self.nums)):
            i2 = i1 - 1
            cNum = self.nums[i1]

            if self.isAsc:
                while self.nums[i2] > cNum and i2 >= 0:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1
            else:
                while self.nums[i2] < cNum and i2 >= 0:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1

            self.nums[i2+1] = cNum

    def getSortedNumbers(self):
        return self.nums

    def getMinNumber(self):
        if self.isAsc:
            return self.nums[0]
        else:
            return self.nums[len(self.nums)-1]

    def getMaxNumber(self):
        if self.isAsc:
            return self.nums[len(self.nums)-1]
        else:
            return self.nums[0]

• 실행파일

import sortMod as sm
import random

nums = random.sample(range(1, 1000), 100)
print(f'not sorted numbers: {nums}')

sn = sm.SortNumbers(nums)

# 오름차순
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by ASC : {sortedNumbers}')

# 내림차순
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by DESC : {sortedNumbers}')

# 최솟값, 최댓값
print(f'min: {sn.getMinNumber()}')
print(f'max: {sn.getMaxNumber()}')

6. 선택 정렬

• 주어진 리스트 중에 최솟값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬

nums = [4, 2, 5, 1, 3]
print(f'nums: {nums}')

for i in range(len(nums)-1):    # 기준 데이터는 맨 끝-1 까지 이동
    minIdx = i

    for j in range(i+1, len(nums)):   # 최솟값 구하기: 기준데이터+1부터 끝까지 비교하면서 최솟값을 찾음
        if nums[minIdx] > nums[j]:
            minIdx = j

    nums[i], nums[minIdx] = nums[minIdx], nums[i] # 기준 데이터와 최솟값 데이터를 교체함
    
	print(f'nums: {nums}')
    
print(f'fianl nums: {nums}')

• 바뀌는 과정

nums: [4, 2, 5, 1, 3]
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 3, 4, 5]
nums: [1, 2, 3, 4, 5]
final nums: [1, 2, 3, 4, 5]

• 모듈 만들어 사용하기
• sortMod 모듈

def sortNumber(ns, asc=True):

    if asc:                            # 오름차순
        for i in range(len(ns)-1):
            minIdx = i

            for j in range(i+1, len(ns)):
                if ns[minIdx] > ns[j]:
                    minIdx = j

            ns[i], ns[minIdx] = ns[minIdx], ns[i]

    else:                             # 내림차순
        for i in range(len(ns)-1):
            minIdx = i

            for j in range(i+1, len(ns)):
                if ns[minIdx] < ns[j]:
                    minIdx = j

            ns[i], ns[minIdx] = ns[minIdx], ns[i]

    return ns

• 실행파일

import random
import sortMod as sm
import copy

scores = random.sample(range(50, 101), 20)

print(f'scores: {scores}')   # 원본 데이터
result = sm.sortNumber(copy.deepcopy(scores))  # 정렬한 데이터
print(f'result: {result}')

print(f'scores: {scores}')   # 원본 데이터
result = sm.sortNumber(copy.deepcopy(scores), asc=False)  # 정렬한 데이터
print(f'result: {result}')

import copy
copy.deepcopy()
-> 깊은 복사로 원본데이터 유지 가능

• 그나마 정렬 중에서 선택정렬이 제일 낫다! 최솟값만 찾아주면 됨

7. 최댓값

• 자료구조에서 가장 큰 값을 찾음
• 클래스 만들어 사용해보기

class MaxAlgorithm:

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

    def getMaxNum(self):

        self.maxNum = self.nums[0]

        for n in self.nums:
            if self.maxNum < n:
                self.maxNum = n

        return self.maxNum

ma = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
maxNum = ma.getMaxNum()

print(f'maxNum: {maxNum}')

• 알파벳끼리 아스키코드값 비교해서 최댓값 구하기

class MaxAlgorithm:

    def __init__(self, cs):
        self.chars = cs
        self.maxChar = 0

    def getMaxChar(self):

        self.maxChar = self.chars[0]

        for c in self.chars:
            if ord(self.maxChar) < ord(c):      # 아스키코드값을 비교
                self.maxChar = c

        return self.maxChar

chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = MaxAlgorithm(chars)
maxChar = mc.getMaxChar()
print(f'maxChar: {maxChar}')

8. 최솟값

• 자료구조에서 가장 작은 값을 찾음

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

• 알파벳 아스키코드값 최솟값 구하기

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

chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
ma = MinAlgorithm(chars)
minChar = ma.getMinChar()
print(f'minChar: {minChar}')

9. 최빈값 (최댓값 이용해서 구함)

• 데이터에서 빈도수가 가장 많은 데이터 구하기
• 데이터에서 가장 큰 수(최댓값)를 구하고, 0부터 최댓값까지의 하나하나의 갯수를 세어서 저장할 리스트(indexes)를 만듬. 새로 만든 리스트(indexes)에, 각 숫자의 인덱스 자리에 1씩 더해줌. 예를들어 숫자 3이 있으면 indexes 리스트에서 인덱스 3 위치에 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, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlgo = MaxAlgorithm(nums)
maxAlgo.setMaxIdxAndNum()
maxNum = maxAlgo.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의 인덱스로 생각해서 1씩 더함
    indexes[n] += 1
print(f'indexes: {indexes}')

maxAlgo = MaxAlgorithm(indexes)    # indexes에서의 최댓값을 구함-> 그게 빈도수이고, 해당 인덱스가 최빈값임.
maxAlgo.setMaxIdxAndNum()
maxNum = maxAlgo.getMaxNum()
maxNumIdx = maxAlgo.getMaxNumIdx()
print(f'maxNum: {maxNum}')           # 4
print(f'maxNumIdx: {maxNumIdx}')     # 7

print(f'즉, {maxNumIdx}의 빈도수가 {maxNum}로 가장 높다.')

• 클래스모듈 만들어 사용하기

class MaxAlgorithm:

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

    def setMaxNumIdxAndNum(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

• 실행파일(5점 단위의 랜덤 성적별 빈도수 구하기)

import maxScore as ms
import random

scores = []

for i in range(100):
    rn = random.randint(71, 100)  # 중복 있음
    if rn != 100:
        rn -= (rn % 5)     # 점수를 5의 배수로 만들기 위해 5로 나눈 나머지를 빼줌
    scores.append(rn)

print(f'scores: {scores}')
print(f'scores length: {len(scores)}')


# 최댓값 알고리즘
maxAlgo = ms.MaxAlgorithm(scores)
maxAlgo.setMaxNumIdxAndNum()
maxNum = maxAlgo.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] += 1
print(f'indexes: {indexes}')

# 각 성적별 빈도수 출력하기(반복문 이용)
n = 1
while True:
    maxAlgo = ms.MaxAlgorithm(indexes)
    maxAlgo.setMaxNumIdxAndNum()
    maxNum = maxAlgo.getMaxNum()
    maxNumIdx = maxAlgo.getMaxNumIdx()

    if maxNum == 0:
        break

    print(f'{n}. {maxNumIdx}빈도수: {maxNum} \t', end='')
    print('+' * maxNum)

    indexes[maxNumIdx] = 0    # 최빈값 출력후 0으로 만들면서 그 다음 최빈값을 출력하기 위함

    n += 1

1. 80빈도수: 21 	+++++++++++++++++++++
2. 95빈도수: 20 	++++++++++++++++++++
3. 75빈도수: 16 	++++++++++++++++
4. 90빈도수: 16 	++++++++++++++++
5. 85빈도수: 15 	+++++++++++++++
6. 70빈도수: 11 	+++++++++++
7. 100빈도수: 1 	+

10. 근삿값

• 특정 값(참값)에 가장 가까운 값 구하기

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

• 근삿값의 학점 출력하기 모듈

def getNearNum(av):

    baseScores = [95, 85, 75, 65, 55]  # 입력할 평균점수의 근삿값을 구할 리스트
    nearNum = 0
    minNum = 100

    for n in baseScores:
        absNum = abs(n - av)
        if absNum < minNum:
            minNum = absNum
            nearNum = n

    if nearNum == 95:
        return 'A'
    elif nearNum == 85:
        return 'B'
    elif nearNum == 75:
        return 'C'
    elif nearNum == 65:
        return 'D'
    elif nearNum <= 55:
        return 'F'

import nearMod as nm

scores = []

kor = int(input('input kor score: '))
scores.append(kor)
eng = int(input('input eng score: '))
scores.append(eng)
mat = int(input('input mat score: '))
scores.append(mat)
sci = int(input('input sci score: '))
scores.append(sci)
his = int(input('input his score: '))
scores.append(his)

totalScore = sum(scores)
print(f'totalScore: {totalScore}')

avgScore = totalScore / len(scores)
print(f'avgScore: {avgScore}')

grade = nm.getNearNum(avgScore)
print(f'grade: {grade}')

11. 평균

• 여러 수나 양의 중간값을 갖는 수

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: {round(average, 2)}')

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

• 체조선수의 점수 평균을 구하고, 기존 순위와 합쳐 몇 위가 되는지 구하기 (근삿값 이용)
• 모듈 만들어 이용

class Top5Players:

    def __init__(self, cs, ns):
        self.currentScores = cs
        self.newScores = ns

    def setAlignScore(self):

        nearIdx = 0
        nearScore = 0
        minNum = 10.0

        for i, s in enumerate(self.currentScores):
            absNum = abs(self.newScores - s)

            if absNum < minNum:
                minNum = absNum
                nearIdx = i
                nearScore = s

        if self.newScores >= self.currentScores[nearIdx]:
            for i in range((len(self.currentScores)-1), nearIdx, -1):
                self.currentScores[i] = self.currentScores[i-1]

            self.currentScores[nearIdx] = self.newScores
        else:
            for i in range((len(self.currentScores)-1), nearIdx+1, -1):
                self.currentScores[i] = self.currentScores[i-1]

            self.currentScores[nearIdx] = self.newScores

    def getFinalTop5Scores(self):
        return self.currentScores

import near

scores = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
top5PlayerScores = [9.12, 8.95, 8.12, 7.90, 7.88]
print(f'top5PlayerScores: {top5PlayerScores}')

total = 0; average = 0

for n in scores:
    total += n
average = round(total / len(scores), 2)

print(f'total: {total}')
print(f'average: {average}')

tp = near.Top5Players(top5PlayerScores, average)
tp.setAlignScore()
top5PlayerScores = tp.getFinalTop5Scores()
print(f'top5PlayerScores: {top5PlayerScores}')

-> 다시 보기!!!!

12. 재귀

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

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

recursion(10)

• 결과값

**********
*********
********
*******
******
*****
****
***
**
*

• 팩토리얼 계산

def factorial(num):

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

print(f'factorial(10): {factorial(10)}')

• 재귀 알고리즘 이용한 최대공약수 계산
  -> 유클리드 호제법 이용 : 두 자연수 n1, n2에 대하여 (n1>n2) n1을 n2로 나눈 나머지를 r이라 할 때, n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다.

def gcd(n1, n2):
    if n1 % n2 == 0:
        return n2
    else:
        return gcd(n2, n1 % n2)         % n1과 n2의 최대공약수는 n2와 (n1 % n2)의 최대공약수와 같음

print(f'gcd(82, 32): {gcd(82, 32)}')    # 2
print(f'gcd(96, 40): {gcd(96, 40)}')    # 8

• 반복문 이용해서 최대공약수 계산

def greatestCommonDivide(n1, n2):

    maxNum = 0
    for i in range(1, (n1+1)):
        if n1 % i == 0 and n2 % i == 0:
            maxNum = i
    return maxNum

print(greatestCommonDivide(82, 32))      # 2
print(greatestCommonDivide(96, 40))      # 8

<제로베이스 데이터 취업 스쿨>