알고리즘

1) 삽입정렬 (Insertion Sort)

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

for i1 in range(1,len(nums)):   #비교기준 인덱스
    i2 = i1 - 1 #비교 될 인덱스
    cNum = nums[i1] #비교기준 값

    #비교기준 값이 앞에 수와 비교해 제자리 찾아가는 반복문
    while nums[i2]>cNum and i2 >= 0:
        nums[i2+1] = nums[i2]
        i2 -= 1
    
    #비교기준값 제자리에 넣어주기
    nums[i2+1] = cNum

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

nums : [5, 10, 2, 1, 0]
nums : [2, 5, 10, 1, 0]
nums : [1, 2, 5, 10, 0]
nums : [0, 1, 2, 5, 10]
Final nums : [0, 1, 2, 5, 10]

실습1.

insertModuel.py

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]

insertSort.py (실행파일)

iimport random
import insertModuel as im

#1~1000난수 생성 후 100개 리스트로 반환
nums = random.sample(range(1,1000),100)
print(f'not sorted numbers = {nums}')

#객체 생성
sn = im.SortNumbers(nums)

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

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


#min max
print(f'min : {sn.getMinNumber()}')
print(f'man : {sn.getMaxNumber()}')

not sorted numbers = [609, 808, 896, . . . 413, 574]
sortedNumbers by Asc: [31, 33, 36,. . . 968, 970, 975]
sortedNumbers by Dsc : [975, 970, 968,. . . 36, 33, 31]
min : 31
man : 975

2) 선택정렬(Selection Sort)

#선택정렬
#주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 정렬하는 알고리즘

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

for i in range(len(nums)-1):
    #최소값이 있는 인덱스
    minIdx = i

    #비교를 하는 숫자 반복
    #한번 돌때면 한사이클 비교를 마쳤다는 것
    #마쳤다는 건 최소값이 있는 인덱스 번호를 알았다는 것
    for j in range(i+1, len(nums)):
        if nums[minIdx] > nums[j]:
            minIdx = j
    #자리바꿈
    nums[i], nums[minIdx] = nums[minIdx], nums[i]
    print(f'nums : {nums}')
print(f'sorted nums : {nums}')

not sorted 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]
sorted nums : [1, 2, 3, 4, 5]

실습1.

selectModuel.py

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

selectSort.py(실행파일)

import random
import selectModuel as sm

#원본 데이터를 손상하지 않고 함수마다 새로운 값을 주는 것
import copy #깊은복사를 위해

scores = random.sample(range(50,101),20)
print(f'not sorted scores : {scores}')
result1 = sm.sortNumber(copy.deepcopy(scores))
print(f'result asc: {result1}')
print()

#원본데이터 손상되지 않고 깊은 복사가 된걸 확인 할 수 있다.
print(f'not sorted scores : {scores}')
result2 = sm.sortNumber(copy.deepcopy(scores), asc=False)
print(f'result dsc : {result2}')

not sorted scores : [52, 59, 84, 56, 78, 86, 54, 81, 63, 65, 74, 73, 79, 72, 76, 70, 55, 100, 91, 61]
result asc: [52, 54, 55, 56, 59, 61, 63, 65, 70, 72, 73, 74, 76, 78, 79, 81, 84, 86, 91, 100]

not sorted scores : [52, 59, 84, 56, 78, 86, 54, 81, 63, 65, 74, 73, 79, 72, 76, 70, 55, 100, 91, 61]
result dsc : [100, 91, 86, 84, 81, 79, 78, 76, 74, 73, 72, 70, 65, 63, 61, 59, 56, 55, 54, 52]

3) 최대값, 최소값 검색

• 자료구조 내에 가장 큰 값과 가장 작은 값을 찾는 알고리즘

• 최대값

class SearchMax:
    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

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

ma = SearchMax(nums)
maxNum = ma.getMaxNum()

print(f'maxNum in nums = {maxNum}')

maxNum in nums = 20

-최소값

class SearchMin:
    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 = SearchMax(nums)
minNum = ma.getMaxNum()

print(f'minNum in nums = {maxNum}')

minNum in nums = -11

실습1.

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']
ma = MaxAlgorithm(chars)
maxChar = ma.getMaxChar()

print(f'MaxChar = {maxChar}')

ord() : 아스키 코드로 변환해주는 함수

MaxChar = x

4) 최빈값

#최빈값 : 빈도수가 가장 높은 데이터
#데이터에서 빈도수가 가장 많은 데이터를 최빈값 그것을 찾는 알고리즘
#리스트가 있으면 리스트 안의 숫자들을 인덱스 번호로 생각하자
#새로운 인덱스 리스트에 해당 인덱스의 값들이 나올 떄 마다 새로운 인덱스를 하나씩 더해준다.
#새로운 인덱스 리스트에서 가장 큰 값의 인덱스 번호가 가장 빈도수가 많은 수이다.

class SearchMax:
    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]
maAlo = SearchMax(nums)
maAlo.setMaxIdxAndNum()
maxNum = maAlo.getMaxNum()
print(f'maxNum = {maxNum}')

indexes = [0 for i in range(maxNum+1)]
print(indexes)
print(len(indexes))

for n in nums:
    indexes[n] += 1

print(f'indexes : {indexes}')

mi = SearchMax(indexes)
mi.setMaxIdxAndNum()
maxNum = mi.getMaxNum()
maxNumIdx = mi.getMaxNumIdx()
print(f'maxNum = {maxNum}')
print(f'maxNumIdx = {maxNumIdx}')
print()
print(f'즉, {maxNumIdx}의 빈도수가 {maxNum}번으로 가장 많다.')

maxNum = 17
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
18
indexes : [0, 1, 0, 1, 0, 0, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
maxNum = 4
maxNumIdx = 7

즉, 7의 빈도수가 4번으로 가장 많다.

실습1.

masScortModuel.py (최빈값 클래스)

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

modeEx.py (실행파일)

import random
import maxScoreModuel as ms

scores = []

for i in range(100):
    rn = random.randint(71,100)

    #점수를 5단위로 나오게 하기 위해
    #랜덤으로 나온 수에 랜덤수를 5로 나눈 나머지를 뺀다면 5단위 수가 된다.
    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.setMaxNumIdxAndNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
print(f'maxNum : {maxNum}')
print(f'maxNumIdx : {maxNumIdx}')

#빈도수 알아 볼 indexes 리스트 생성
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=0
while True:
    maxAlo = ms.MaxAlgorithm(indexes)
    maxAlo.setMaxNumIdxAndNum()
    maxNum = maxAlo.getMaxNum()
    maxNumIdx = maxAlo.getMaxNumIdx()

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

    #최대 빈도수를 출력하고 지워줘야 두번째 높은값이 출력된다.
    indexes[maxNumIdx] = 0

scores : [95, 85, 95,. . . 85, 95, 90]
scores length : 100
maxNum : 100
maxNumIdx : 75
indexes : [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, 9, 0, 0, 0, 0, 
15, 0, 0, 0, 0, 16, 0, 0, 0, 0, 18, 0, 0, 0, 0, 18, 0, 0, 0, 0, 22, 0, 0, 0, 0, 2]
1. 95빈도수 : 22	++++++++++++++++++++++
2. 85빈도수 : 18	++++++++++++++++++
3. 90빈도수 : 18	++++++++++++++++++
4. 80빈도수 : 16	++++++++++++++++
5. 75빈도수 : 15	+++++++++++++++
6. 70빈도수 : 9	+++++++++
7. 100빈도수 : 2	++

5) 근사값

#근삿값
#특정 값에 가장 가까운 값을 근삿값

import random

nums = random.sample(range(0,50),20)
print(f'nums = {nums}')

inptuNum = int(input('기준 숫자 : '))
print(f'input Num : {inptuNum}')

nearNum = 0

#데이터가 많아진다면 최댓값 알고리즘 이용해서 최댓값을 초기변수 값으로 해야 한다.
minNum = 50

#입력한 숫자와 난수로 생성된 숫자들의 차이의 절댓값
#이중에 가장 작은 값이 근삿값이다.
for n in nums:
     absNum = abs(n - inptuNum)

     if absNum < minNum:
         minNum = absNum
         nearNum = n

print(f'nearNum : {nearNum}')

nums = [43, 2, 13, 33, 8, 22, 3, 9, 30, 34, 21, 42, 40, 17, 47, 29, 18, 14, 6, 36]
기준 숫자 : 11
input Num : 11
nearNum : 13

실습1.

nearValueModuel.py

def getNearNum(an):

    #학점이 나뉘는 기준
    baseScores = [95,85,75,65,55]
    nearNum = 0
    minNum = 100

    for n in baseScores:
        absNum = abs(n - an)
        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'

nearValue.py (실행파일)

import nearValueModuel as nv

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

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

input kor score: 70
input eng score: 85
input mat score: 90
input sci score: 77
input his score: 89
totalScore : 411
avgScore : 82.2
grade : B

6) 평균값

• 여러 수나 양의 중간값을 갖는 수를 평균이라고 한다.

• 정수들의 평균

nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]

total = 0
targetNums = []
for n in nums:
    if n - int(n) == 0:
        targetNums.append(n)
        total += n

average = total / len(targetNums)
print(f'targetNums : {targetNums}')
print(f'average : {round(average,2)}')

targetNums : [4, 0, 5, 9, 3, 1, 11]
average : 4.71

실습1.

nearAl.py

• 5등 내의 평균 점수 넣기

class Top5Players:

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

    def setAlignScore(self):

        nearIdx = 0
        nearScore = 0
        minNum = 10

        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 getFinal5Scores(self):
        return self.currentScores

average.py (실행파일)

import nearAl as na

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
for n in scores:
    total += n

average = round(total / len(scores) ,2)
print(f'total : {total}')
print(f'average : {average}')

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

top5PlayerScores : [9.12, 8.95, 8.12, 7.9, 7.88]
total : 83.9
average : 8.39
top5PlayerScores : [9.12, 8.95, 8.39, 8.12, 7.9]