😢 스터디노트(알고리즘 1~7)

꼭꼭 다시풀어보기!! 😰

선형검색

• 선형검색 : 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다
• 보초법 : 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정

# 선형 검색
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 = [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

datas.append(searchData) # 찾으려는 숫자를 먼저 추가

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

print(f'datas : {datas}')
print(f'datas length : {len(datas)}')
print(f'searchResultIdx : {searchResultIdx}')

---

선형검색(실습)

💡 리스트에서 가장 앞에 있는 숫자 ‘7’을 검색하고 위치(인덱스)를 출력

# 리스트에서 가장 앞에 있는 숫자 ‘7’을 검색하고 위치(인덱스)를 출력

# nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
#
# searchNumber = int(input('숫자 검색 : '))
# searchNumberIndex = -1
# n = 0
# flag = True
# while flag:
#     if searchNumber != nums[n]:
#         searchNumberIndex = -1
#
#     elif searchNumber == nums[n]:
#         flag = False
#         searchNumberIndex = n
#         break
#     n += 1
#
# print(f'nums : {nums}')
# print(f'nums length : {len(nums)}')
# print(f'searchNumber : {searchNumber}')
# print(f'searchNumberIndex : {searchNumberIndex}')


nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

searchNumber = int(input('숫자 검색 : '))
searchNumberIndex = -1

nums.append(searchNumber)

n = 0
while True:
    if nums[n] == searchNumber:
        if n != len(nums)-1:
            searchNumberIndex = n
        break
    n += 1

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

if searchNumberIndex < 0:
    print('not search index')
else:
    print(f'search index : {searchNumberIndex}')

💡 리스트에서 숫자 ‘7’을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력

# 리스트에서 숫자 ‘7’을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

def searchNumber(n) :
    searchNumber = int(input('숫자 검색 : '))
    
    searchResultIdxs = []
    nums.append(searchNumber)
    n = 0
    while True:
        if nums[n] == searchNumber:
            if n != len(nums)-1:
                searchResultIdxs.append(n)
            else:
                break
        n += 1
    return searchResultIdxs

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

---

💡 이진검색

• 이진검색 : 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색
• 이진검색을 사용할 경우 데이터가 미리 정렬이 되어 있어야 한다

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

print(f'datas : {datas}')
print(f'data length : {len(datas)}')

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

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

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

while searchData <= datas[len(datas)-1] and searchData >= datas[0]: 
# 데이터 범위 안에 있어야 검색하는 의미가 있어서 조건 설정함
    if searchData == datas[len(datas)-1]:
        searchResultIdx = len(datas)-1
        break
    elif searchData > midVal:
        startIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')
    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')
    elif searchData == midVal:
        searchResultIdx = midIdx
        break
print(f'searchResultIdx : {searchResultIdx}')

---

이진검색(실습)

리스트를 오름차순으로 정렬한 후 ‘7’을 검색하고 위치(인덱스)를 출력

# 리스트를 오름차순으로 정렬한 후 ‘7’을 검색하고 위치(인덱스)를 출력

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

nums.sort()
print(f'nums : {nums}')

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

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

while searchData <= nums[(len(nums)-1)] and searchData >= nums[0]:
    if searchData == nums[len(nums)-1]:
        searchResultIdx = nums[len(nums)-1]
        break
    elif searchData > midVal:
        startIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')
    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')
    elif searchData == midVal:
        searchResultIdx = midIdx
        break
print(f'searchResultIdx : {searchResultIdx}')

---

💡 순위

• 순위 : 수의 크고 작음을 이용해서 수의 순서를 정하는 것

import random

nums = random.sample(range(50, 100),20)
print(nums)

ranks = [0 for i in range(20)] # ★
print(ranks)

for idx, num1 in enumerate(nums):
    for num2 in nums: # 조건을 만족하지 못하면 nums 다음 번호와 비교
        if num1 < num2:
            ranks[idx] += 1

ranks2 = [0 for i in range(20)] # ★
print(ranks)
print()

for idx, num1 in enumerate(nums):
    for num2 in nums: # 조건을 만족하지 못하면 nums 다음 번호와 비교
        if num1 > num2:
            ranks2[idx] += 1

print(nums)
print(ranks)
print(ranks2)

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

---

💡 순위(실습)

💡 학급 학생(20명)들의 중간고사와 기말고사 성적을 이용해서 각각의 순위를 구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력하는 프로그램을 만들어 보자.(시험 성적은 난수를 이용한다.)

import random

midStuScos = random.sample(range(50, 100),20)
mid_ranks = [0 for i in range(20)]
endStuScos = random.sample(range(50, 100),20)
end_ranks = [0 for i in range(20)]

# print(midStuScos)
# print(mid_ranks)
# print(endStuScos)
# print(end_ranks)

midSum = 0
midAvg = 0

for idx, n1 in enumerate(midStuScos):
    for n2 in midStuScos:
        if n1 < n2:
            mid_ranks[idx] += 1
#print(mid_ranks)

for idx, n1 in enumerate(endStuScos):
    for n2 in endStuScos:
        if n1 < n2:
            end_ranks[idx] += 1
#print(end_ranks)

deviationRank = [0 for i in range(20)]
for num in range(20):
    if mid_ranks[num] > end_ranks[num]:
        deviationRank[num] = '↑'+str(mid_ranks[num] - end_ranks[num])
    elif mid_ranks[num] < end_ranks[num]:
        deviationRank[num] = '↓'+str(abs(mid_ranks[num] - end_ranks[num]))
    elif mid_ranks[num] == end_ranks[num]:
        deviationRank[num] = '=' + str(mid_ranks[num] - end_ranks[num])
#print(deviationRank)

for num in range(len(mid_ranks)):
    print(f'mid_rank : {mid_ranks[num]}\t end_rank : {end_ranks[num]}\t'
          f' Deviation : {deviationRank[num]}')
print()

# 모듈 이용
# rank 파일

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(ess))]
        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'
                  f'Deviation : {deviation}')
#------------------------------------------------------------

# 모듈 이용
import random
import rank

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

rd = rank.RankDeviation(midStuScos, endStuScos)
rd.setMidRank()
print(f'midStuScores : {midStuScos}')
print(f'mid_rank : {rd.getMidRank()}')
rd.setEndRank()
print(f'endStuScores : {endStuScos}')
print(f'end_rank : {rd.getEndRank()}')

rd.printRankDeviation()

---

💡 버블정렬

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

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

length = len(nums) - 1

for i in range(length):
    for j in range(length-i):
        if nums[j] > nums[j+1]:
            # temp = nums[j]
            # nums[j] = nums[j+1]
            # nums[j+1] = temp

            nums[j], nums[j+1] = nums[j+1], nums[j] #위의 값바꾸는 것과 동일 ★★★★★
        print(nums)
    print()
print(f'sorted nums : {nums}')

---

💡 버블정렬(실습)

새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성

# sortMod 파일

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
    

# 새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로
# 줄 세워 보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성

import random
import sortMod

students = []
for i in range(20):
    students.append(random.randint(170, 185))

print(f'students : {students}')

sortedStudent = sortMod.bubbleSort(students)
print(f'students : {students}')
print(f'students : {sortedStudent}')

---

💡 삽입정렬

• 삽입정렬 : 정렬되어 있는 자료 배열과 비교해서 정렬 위치를 찾는다

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

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


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

---

💡 삽입정렬(실습)

💡 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 생성

# setMod2 파일

class sortNumbers:

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

    def isAcending(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 getSortedNumber(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]

# 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 생성

import random
import sortMod2

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

#객체 생성
sn = sortMod2.sortNumbers(nums)

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

# 내림차순(descending)
sn.isAcending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumber()
print(f'sorted numbers by DESC : {sortedNumbers}')

# 최소값과 최대값
print(f'min : {sn.getMinNumber()}')
print(f'max : {sn.getMaxNumber()}')

---

💡 선택정렬

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

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)): # 기준이 되는 숫자 이후부터 끝까지
        if nums[minidx] > nums[j]:
            minidx = j

    # tempNum = nums[i]
    # nums[i] = nums[minidx]
    # nums[minidx] = tempNum

    nums[i], nums[minidx] = nums[minidx], nums[i] # ★★★★★ 위의 숫자 바꾸기와 동일
    print(f'nums : {nums}')
    
print(f'final nums : {nums}')

---

💡 선택정렬(실습)

💡 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 생성. 시험 점수는 50부터 100까지로 한다

# select_sortMod 파일

class SortNumber:

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


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

    def setSort(self):
        for i in range(len(self.nums)-1):
            minIdx = i
            if self.isAsc:
                for j in range(i+1, len(self.nums)):
                    if self.nums[minIdx] > self.nums[j]:
                        minIdx = j
                self.nums[i], self.nums[minIdx] = self.nums[minIdx],self.nums[i]
            else:
                for j in range(i + 1, len(self.nums)):
                    if self.nums[minIdx] < self.nums[j]:
                        minIdx = j
                self.nums[i], self.nums[minIdx] = self.nums[minIdx],self.nums[i]

    def getSortNumbers(self):
        if self.isAsc:
            self.setSort()
            return self.nums
        else:
            self.setSort()
            return self.nums

# 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로
# 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다

import random
import select_sortMod
import copy

scores = random.sample(range(50, 100), 20)
print(f'not sorted scores : {scores}')
print(f'scores length : {len(scores)}')
print()


sc = select_sortMod.SortNumber(copy.copy(scores)) #★★★ 복사된 리스트로 정렬
print(f'not sorted scores : {scores}')
sc.isAcending(True)
print(f'result(ASC) : {sc.getSortNumbers()}')
print()
print(f'not sorted scores : {scores}')
sc.isAcending(False)
print(f'result(DESC) : {sc.getSortNumbers()}')

---

최댓값

• 최댓값 : 가장 큰 값

class MaxAlgorithm:

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

    def getMaxNum(self):
        self.maxNum = self.nums[0] # 처음엔 max값에 맨 앞의 값 부여

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

---

최댓값(실습)

• ord() : 문자열을 아스키코드로 반환

리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 생성

# 리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 생성

class MaxAlgorithm:

    def __init__(self, chars):
        self.chars = chars
        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}')

---

최솟값

• 최솟값 : 가장 작은 값

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

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

---

최솟값(실습)

리스트에서 아스키코드가 가장 작은 값을 찾는 알고리즘을 생성

# 리스트에서 아스키코드가 가장 작은 값을 찾는 알고리즘을 생성

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

---

💡 최빈값

• 최빈값 : 빈도수가 가장 많은 데이터

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]

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'index length : {len(indexes)}')

for n in nums:
    indexes[n] = indexes[n]+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}의 빈도수가 {maxNumIdx}로 가장 높다')

---

💡 최빈값(실습)

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

# 최빈값 알고리즘을 이용해서 학생 100명의 점수 분포를 다음과 같이 나타내기
import copy
import random

scores = []
for i in range(100): # ★★★★★
    rn = random.randint(71, 100)
    if rn != 100 :
        rn = rn - (rn % 5)
    scores.append(rn)

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

    def setMaxNumAndMaxNumIdx(self):
        self.maxNum = self.nums[0]
        self.maxNumIdx = 0

    def getMaxNumAndMaxNumIdx(self):
        for i, n in enumerate(self.nums):
            if n > self.maxNum:
                self.maxNum = n
                self.maxNumIdx = i
    def getMaxNum(self):
        return self.maxNum
    def getMaxNumIdx(self):
        return self.maxNumIdx


    def setSortMinNum(self):
        self.sortMinNum = self.nums[0]

    def sortNum(self):
        for i in range(len(self.nums)-1):
            for j in range(len(self.nums)-1-i):
                if self.nums[j] < self.nums[j+1]:
                    self.nums[j], self.nums[j+1] = self.nums[j+1],self.nums[j]




print(f'scores : {scores}')
sc = Algorithm(scores)
sc.setMaxNumAndMaxNumIdx()
sc.getMaxNumAndMaxNumIdx()

maxNum = sc.getMaxNum()
maxNumIdx = sc.getMaxNumIdx()
print(f'maxNum : {maxNum}')
print(f'maxNumIdx : {maxNumIdx}')

# 인덱스 리스트 생성
index = [0 for i in range(maxNum+1)]

# 인덱스 리스트에 빈도 저장
for sc in scores:
    index[sc] = index[sc] + 1
print(f'index : {index}')

#####내가 한 부분#####
# index2 = []
# for idx in index:
#     if idx != 0:
#        index2.append(idx)
# print(f'index2 : {index2}')
#
# idx2 = Algorithm(index2)
# idx2.setSortMinNum()
# idx2.sortNum()
# print(f'index2 : {index2}')
#
# n = 1
# for idx2 in index2:
#     for idx, num in enumerate(index):
#         if idx2 == num:
#             print(f'{n}. {idx}빈도수 : {num}\t', end='')
#             print('+'*num)
#             n += 1
#####내가 한 부분#####


n = 1
while True:
    maxAlo = Algorithm(index)
    maxAlo.setMaxNumAndMaxNumIdx()
    maxAlo.getMaxNumAndMaxNumIdx()
    maxNum = maxAlo.getMaxNum()
    maxNumIdx = maxAlo.getMaxNumIdx()

    if maxNum == 0:
        break

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

    index[maxNumIdx] = 0
    n += 1

---

💡 근삿값

• 근사값 : 특정 값(참값)에 가장 가까운 값

import random

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

inputNumber = int(input('input number : '))
print(f'inputNumber : {inputNumber}')

nearNum = 0
diffNum = 50 # 최소값과 최대값의 차이

for n in nums:
    absNumber = abs(n - inputNumber)
    #print(f'absNumber : {absNumber}')

    if absNumber < diffNum:
        diffNum = absNumber
        nearNum = n

print(f'nearNumber : {nearNum}')

---

💡 근삿값(실습)

근삿값 알고리즘을 이용해서 시험 점수를 입력하면 학점이 출력되는 프로그램을 생성
평균 점수에 따른 학점 기준 점수는 다음과 같다.

# near 파일


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 'E'

# 근삿값 알고리즘을 이용해서 시험 점수를 입력하면 학점이 출력되는 프로그램을 생성
# 평균 점수에 따른 학점 기준 점수는 다음과 같다.

import near

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 = near.getNearNum(avgScore)
print(f'grade : {grade}')

---

평균

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

import random

nums = random.sample(range(0, 100),100)
print(f'nums : {nums}')

total = 0
for n in nums:
    total += n

average = total / len(nums)
print(f'total : {total}, average : {average}')

# 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'total : {total}, 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:
        targetNums.append(n)
        total += n

average = total / len(targetNums)

print(f'total : {total}, 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:
        targetNums.append(n)
        total += n
print(f'nums : {targetNums}')
average = total / len(targetNums)

print(f'total : {total}, average : {round(average,2)}')

---

💡 평균(실습)

다음은 어떤 체조선수의 점수이다.평균을 구하고 순위를 정하는 알고리즘을 생성

#near2 파일

class Top5Players:
    def __init__(self, cs, ns):
        self.currentScores = cs
        self.newScore = ns

    def setAlignScore(self):

        nearIdx = 0
        nearScore = 0
        minNum = 10

        for i, score in enumerate(self.currentScores):
            absNums = abs(self.newScore - score)

            if absNums < minNum:
                minNum = absNums
                nearIdx = i
                nearScore = score
        if self.newScore >= self.currentScores[nearIdx]:
            for i in range(len(self.currentScores)-1, nearIdx, -1): # ★★★★★
                self.currentScores[i] = self.currentScores[i-1] # ex) 5번째에는 4번 값이 들어오고, 4번째에는 3번 값이 들어오고...
            self.currentScores[nearIdx] = self.newScore # 새로운 값은 근사값 위치에

        else:
            for i in range(len(self.currentScores)-1, nearIdx+1, -1): # ★★★★★
                self.currentScores[i] = self.currentScores[i-1] # ex) 5번째에는 4번 값이 들어오고, 4번째에는 3번 값이 들어오고...
            self.currentScores[nearIdx] = self.newScore # 새로운 값은 근사값 뒤에 배정
    def getFinalTop5Scores(self):
        return self.currentScores

# 다음은 어떤 체조선수의 점수이다.평균을 구하고 순위를 정하는 알고리즘을 생성
import near2


scores = [8.9, 7.6, 8.2, 9.1, 8.8, 8.1, 7.9, 9.4, 7.2, 8.7]
finalScores = [9.12, 8.95, 8.12, 7.90, 7.88]
total = 0
for sc in scores:
    total += sc

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

tp = near2.Top5Players(finalScores, average)
tp.setAlignScore()
tp.getFinalTop5Scores()
print('최종 전체 순위')
print(f'top5PlayerScores : {tp.getFinalTop5Scores()}')

---

재귀

• 재귀 : 나 자신을 다시 호출

#  반복문 대신 재귀 함수를 이용한 예
def recusion(num):
    if num > 0:
        print('*'*num)
        return recusion(num - 1)
    else:
        return 1

recusion(10)

# 재귀 함수를 이용한 팩토리얼 구하기

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

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

---

재귀(실습)

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

# 재귀 알고리즘을 이용한 최대 공약수 계산

# 유클리드 호제법
# • 두 자연수 n1, n2에 대하여 (n1 > n2) n1를 n2로 나눈 나머지를 r이라고 할 때,
# • n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다

def greatestCommonDevide(n1, n2):

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

print(f'greatestCommonDevide(82, 32) : {greatestCommonDevide(82, 32)}')
print(f'greatestCommonDevide(96, 40) : {greatestCommonDevide(96, 40)}')



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

---

💡 하노이의 탑

• 하노이의 탑 : 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약조건은 다음과 같다
  - 한 번에 한개의 원판만 옮길 수 있다
  - 큰 원판이 작은 원판 위에 있어서는 안 된다.

---

💡 하노이의 탑(실습)

파이썬을 이용해서 하노이의 탑 게임 진행 과정을 출력
• 한 번에 한개의 원판만 옮길 수 있다.
• 큰 원판이 작은 원판 위에 있어서는 안 된다

# 파이썬을 이용해서 하노이의 탑 게임 진행 과정을 출력
# • 한 번에 한개의 원판만 옮길 수 있다.
# • 큰 원판이 작은 원판 위에 있어서는 안 된다

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


moveDisc(3, 1, 3, 2) 

---

💡 병합정렬

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

nums = [8, 1, 4, 3, 2, 5, 10, 6]

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 # 왼쪽 리스트의 인덱스 +1
        else:
            mergeNums.append(rightNums[rightIdx])
            rightIdx += 1
    mergeNums = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rightNums[rightIdx:]

    return mergeNums # 오른쪽 리스트의 인덱스 +1

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

---

💡 병합정렬(실습)

💡 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 생성
요구 사항1) 병합정렬 알고리즘을 이용한 난수 정렬 모듈 구현
요구 사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가

# sortMod3 파일

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

    return mergeNums

# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 생성
# 요구 사항1) 병합정렬 알고리즘을 이용한 난수 정렬 모듈 구현
# 요구 사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가

import random as rd
import sortMod3 as sm

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

---

💡 퀵정렬

• 퀵정렬 : 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다

def qSort(ns):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

    smallNums = []; sameNums = []; bigNums=[]

    for n in ns:
        if n < midVal:
            smallNums.append(n)
        elif n == midVal:
            sameNums.append(n)
        else:
            bigNums.append(n)

    return qSort(smallNums) + sameNums + qSort(bigNums)

nums = [8, 1, 4, 3, 2, 5, 4, 70, 6, 8]

print(qSort(nums))

---

💡 퀵정렬(실습)

1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 생성
요구 사항1) 퀵정렬 알고리즘을 이용한 난수 정렬 모듈 구현
요구 사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가

# qSort 파일

def qSort(ns, asc = True):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

    smallNums = []; sameNums = []; bigNums = []


    for n in ns:
        if midVal > n:
            smallNums.append(n)
        elif midVal == n:
            sameNums.append(n)
        else:
            bigNums.append(n)

    if asc:
        return qSort(smallNums) + sameNums + qSort(bigNums)
    else:
        return qSort(bigNums, asc=False) + sameNums + qSort(smallNums, asc=False)

# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 생성
# 요구 사항1) 퀵정렬 알고리즘을 이용한 난수 정렬 모듈 구현
# 요구 사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가

import qSort
import copy
import random

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

💻 출처 : 제로베이스 데이터 취업 스쿨