3.3 파이썬 알고리즘 실습 스터디노트3

근삿값

근삿값 알고리즘을 이용해서 시험 점수를 입력하면 학점이 출력되는 프로그램을 만들어라

95에 근삿값이면 A학점
85에 근삿값이면 B학점
75에 근삿값이면 C학점
65에 근삿값이면 D학점
55에 근삿값이면 F학점

모듈

def getNearNum(an):
	bascores = [95, 85, 75, 65, 55]
    nearNum = 0
    minNum = 100
    
    for n in bascores:
    	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'              

실행

import near

scores = []

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

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

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

grade = near.getNearNujm(avgScore)
print(f'grade : {grade})

재귀

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

#반복문을 쓴 방식
def greatestCommonDevide(n1, n2):
	maxNum = 0
    for i in range(1, (n1 + 1)):
    	if n1 % 1 == 0 and n2 % 1 == 0:
        	maxNum = i
    return maxNum
    
print('greatestCommonDevide(82, 32) : greatestCommonDevide(82, 32)}')
print('greatestCommonDevide(96, 40) : greatestCommonDevide(96, 40)}')


#재귀함수를 쓴 방식
def gcd(n1, n2):
	if n1 % n2 == 0:
    	return n2
        
    else:
    	return gcd(n2, n1 % n2)

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

병합 : 분할하고 다시 합친다.

1부터 100까지 난수 10개를 생성하고 다음의 요구사항을 만족하는 모듈을 만들어라

요구사항1) 병합정렬을 이용한 난수 정렬 모듈 구현
요구사항2) 위 모듈에 오름차순, 내림차순을 선택할 수 있는 옵션 추가

모듈

def mSort(ns, asc = True):
	if len(ns) < 2:
    	return ns
    
    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc = asc) #재귀함수에서 asc 값을 true로 변경하는 것이 아닌 통일성 있게 유지하고 싶을 때
    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 += leftNum[leftIdx:]
     mergeNums += rightNum[rightIdx:]
     return mergeNums

실행

import random as rd
import sortMod as sm

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

퀵 정렬

1부터 100까지 난수 10개를 생성하고 다음의 요구사항을 만족하는 모듈을 만들어라

요구사항1) 퀵 정렬을 이용한 난수 정렬 모듈 구현
요구사항2) 위 모듈에 오름차순, 내림차순을 선택할 수 있는 옵션 추가

모듈

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 n < midVal:
        	smallNums.append(n)
        elif n == midVal:
        	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 as rd
import sortMod as sm

rNums = rd.sample(range(1, 100), 10)
print(f'sorted rNums ASC : {sm.qSort(rNum, asc = True)}')
print(f'sorted rNums DESC : {sm.qSort(rNum, asc = False)}')