[Zero-Base DS]스터디노트_알고리즘(02)

주요 학습내용

1. 근삿값

2. 평균

3. 재귀

4. 하노이의 탑

5. 병합 정렬

6. 퀵 정렬

I. 근삿값

1. 근삿값이란

• 특정 값(참값)에 가장 가까운 값을 근갓값이라고 한다

2. 파이썬 예제(근삿값)

95에 근사하면: A학점
85에 근사하면: B학점
75에 근사하면: C학점
65에 근사하면: D학점
55에 근사하면: E학점

1) 모듈(near) 생성

def getNearNum(an):  # 평균 n

    baseScores = [95, 85, 75, 65, 55]  # 기준 생성
    nearNum = 0
    minNum = 100  # 차이값 100으로 시작

    for n in baseScores:
        absNum = abs(n - an)  # (입력)평균값과 basescores간의 차이
        if absNum < minNum:   # 1st 시도일 경우, 차이값이 100보다 작으면
            minNum = absNum   # 차이값 = 해당 차이값으로 재할당
            nearNum = n       # 근사값 = n(basescores 중 가장 차이 적은 항목)

    # 점수 입력(FOR문 안에 있으면 안됨/ 근사값 다 구한 후 => 출력)
    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'

2) 모듈 참조하여 예제 풀이

# 근삿값 알고리즘 이용
# 시험 점수 입력하면 학점 출력(평균점수 기반)
# 95(A), 85(B), 75(C), 65(D), 55(F)
import near
scores = []

kor = int(input('input kor score: '))
scores.append(kor)
eng = int(input('input eng score: '))
scores.append(eng)
math = int(input('input math score: '))
scores.append(math)
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 = round(totalScore / len(scores), 1)
print(f'avgScore: {avgScore}')

print('-'*50)
grade = near.getNearNum(avgScore)
print(f'grade: {grade}')

출력 결과 :

II. 평균

1. 파이썬 예제

1-1) 방법 1. 모듈 사용

1) 모듈(near2) 생성

class Top5players:

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

    def setAlignScore(self):

        nearIdx = 0
        nearScore1 = 0
        minNum = 10.0

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

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

        # 근사값의 앞/뒤 어디로 들어갈지 설정
        if self.newScore >= self.currentScores[nearIdx]:
            for i in range(len(self.currentScores)-1, nearIdx, -1):
                self.currentScores[i] = self.currentScores[i-1]

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

2) 모듈 사용하여 예제 풀이

# 추가 선수 평균 구하기 + (추가 선수 더한)순위 정하기
# 현재 순위 : 9.12->8.95->8.12->7.90->7.88
import near2

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

total = 0
for n in scores:
    total += n
avg = round(total / len(scores), 2)
print(f'avg: {avg}')

tp = near2.Top5players(ranks, avg)
tp.setAlignScore()
newRank = tp.getFinalTop5Scores()
print(f'newRank: {newRank}')

출력 결과 :

1-2) 방법2. for문 사용

• 강의를 듣기 전 문제를 먼저 풀어봤을 때, class를 따로 생성하지 않고 for문을 통해 해당 문제를 풀이하였다. 풀이 방법은 아래와 같다.

# 추가 선수 평균 구하기 + (추가 선수 더한)순위 정하기
# 현재 순위 : 9.12->8.95->8.12->7.90->7.88

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

total = 0
for n in scores:
    total += n
avg = round(total / len(scores), 2)
print(f'avg: {avg}')

# 순위 찾기(내가 한 방법)
rank_idx = 0

for idx, r in enumerate(ranks):
    if avg > r:
        rank_idx = idx
        ranks.insert(rank_idx, avg)
        break
print(f'ranks: {ranks[0:5]}')

출력 결과 :

III. 재귀

1. 재귀란

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

  재귀 알고리즘의 개념적인 부분을 이해하는 건 어렵지 않았다. 하지만 예제에 적용하는데 있어 초반에 많은 어려움이 있었고, 현재도 쉽다고 느껴지진 않기에 추후 다시 복습을 통해 학습할 예정이다.

2. 파이썬 예제(재귀함수를 사용하여 팩토리얼 구하기)

def factorial(num):

    if num > 0:
        return num * factorial(num - 1)
    else:
        return 1
print(f'factorial(10): {format(factorial(10), ',')}')

출력 결과 :

IV. 하노이의 탑

1. 하노이의 탑

• 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다

  1. 한 번에 한개의 원판만 옮길 수 있다
  2. 큰 원판이 작은 원판 위에 있어서는 안 된다

2. 파이썬 예제(하노이의 탑)

# 재귀함수 사용하여 하노이의 탑 알고리즘 구하기
           # 원판 개수, 출발기둥,  도착,   경유
def moveDisc(discCnt, fromBar, toBar, viaBar):

    if discCnt == 1:  # 원판 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)
        # 이전 step에서 viaBar로 옮겨 놨기 때문에 from viaBar to toBar


moveDisc(3,1,3,2)

출력 결과 :

• 하노이의 탑은 개인적으로 어렸을 적 좋아하던 게임이라 수도 없이 많이 해봤는데, 그걸 프로그램으로 짜려니 정말 쉽지 않았다. 재귀함수를 한번이 아닌 여러번 이용해서 돌고 도는 부분이 머릿속으로만 그려서는 잘 이해되지 않았고, 따라서 그림으로 한 스텝씩 그려가며 이해하였다.
  

V. 병합 정렬

1. 병합 정렬이란

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

2. 파이썬 예제(병합 정렬)

1) 모듈(sort) 생성

# 병합정렬 실습 모듈

def mSort(ns, asc=True):

    # 개수가 2보다 작을 때 까지 분할
    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)
    # 재귀적으로 들어오는 함수에 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

2) 모듈 사용하여 문제 풀이

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

import random
import sort
nums = random.sample(range(1, 101), 10)
print(f'not sorted nums: {nums}')

print(f'sorted nums ASC: {sort.mSort(nums, asc=True)}')

print(f'sorted nums DESC: {sort.mSort(nums, asc=False)}')

출력 결과 :

VI. 퀵 정렬

1. 퀵 정렬이란

• 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합쳐서 정렬하는것
  

2. 파이썬 예제(퀵 정렬)

1) 모듈(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 n < midVal:
            smallNums.append(n)
        elif n == midVal:
            sameNums.append(n)
        elif n > midVal:
            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)

2) 모듈 사용하여 문제 풀이

# 1~100 난수 10개 생성
# 1) 퀵정렬 알고리즘 이용한 난수 정렬 모듈 구현
# 2) 오름차순과 내림차순을 선택할 수 있는 옵션 추가

import random
import qsort as qs

nums = random.sample(range(1, 101), 10)
print(f'not sorted nums: {nums}')
print(f'sorted nums_ASC: {qs.qSort(nums)}')
print(f'sorted nums_DESC: {qs.qSort(nums, asc=False)}')

출력 결과 :

[자료 출처: 제로베이스 데이터 취업 스쿨]