[python] search, ranking, sort, 최빈값, 재귀

선형검색(linear search)

: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾음.

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'searchResuldIdx: {searchResultIdx}')

• 보초법(sentinel method): 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정 간략화.

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'searchResuldIdx: {searchResultIdx}')

이진 검색(binary search)

: '정렬되어 있는' 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색.

순위(ranking)

: 수의 크고 작음을 이용해서 수의 순서를 정함.

import random

nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]      # 길이 20, item의 값 0인 리스트 생성

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 i, n in enumerate(nums):
    print(f'num: {n} \t rank: {ranks[i]+1}')

• [0 for i in range(20)]: 길이 20, item의 값 0인 리스트 생성

# 순위 실습
import rankMod as rm
import random

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

rd = rm.RankDeviation(midStuScos, finStuScos)
rd.setMidRank()
print(f'midStuScors: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')

rd.setFinRank()
print(f'finStuScors: {finStuScos}')
print(f'fin_rank: {rd.getFinRank()}')

rd.printRankDeviation()

# rankMod.py
class RankDeviation:

    def __init__(self, mid, fin):
        self.midStuScos = mid
        self.finStuScos = fin
        self.midRanks = [0 for i in range(len(mid))]  # 중간고사 순위 자료구조
        self.finRanks = [0 for i in range(len(mid))]  # 기말고사 순위
        self.rankDeviation = [0 for i in range(len(mid))]   # 편차

    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 setFinRank(self):
        self.setRank(self.finStuScos, self.finRanks)

    def getFinRank(self):
        return self.finRanks

    def printRankDeviation(self):

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

            if deviation > 0:
                deviation = '↑' + str(abs(deviation))

            elif deviation < 0:
                deviation = '↓' + str(abs(deviation))

            elif deviation == 0:
                deviation = '=' + str(abs(deviation))

            print(f'mid_rank: {mRank} \t fin_rank: {self.finRanks[idx]} \t Deviation: {deviation}')

07 버블 정렬 ~ 30 퀵 정렬(실습)

📌 정렬(sort)

버블 정렬(bubble sort)

두 값 자리 바꾸기:

# 1
temp = a       
a = b
b = temp

# 2 
a, b = b, a

# bubble sort

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]:
            nums[j], nums[j+1] = nums[j+1], nums[j]

print(f'sorted: {nums}')

• 버블 정렬 실습

import random as rd
import sortMod as sm

students = []

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

print(f'students: {students}')

sortedStudents = sm.bubbleSort(students)
print(f'sortedStudents: {sortedStudents}')

# sortMod.py
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

• copy module: 깊은 복사

삽입 정렬(insertion sort)

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

# 삽입 정렬, 오름차순

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

for i1 in range(1, len(nums)):       # 처음 값: i1 = 10, i2 = 5
    i2 = i1 - 1
    cNum = nums[i1]

    while nums[i2] > cNum and i2 >= 0:  # index 는 0 이하
        nums[i2 + 1] = nums[i2]   # 값 바꿈
        i2 -= 1

    nums[i2 + 1] = cNum

    print(f'nums: {nums}')

• 삽입 정렬 실습

import random
import sortMod as sm

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

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

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

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

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

# insertEx.py
class SortNumbers:

    def __init__(self, ns, asc=True):           # 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]

선택 정렬(selection sort)

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

• 실습

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

# sortMod.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)):   # i 다음 값부터 맨 뒤까지
                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)):  # i 다음 값부터 맨 뒤까지
                if ns[minIdx] < ns[j]:
                    minIdx = j

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

    return ns

병합 정렬(merge sort)

재귀함수 사용
: 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬.

def mSort(ns):

    if len(ns) < 2:      # 리스트 길이가 2보다 작으면 return
        return ns

	# 분할
    midIdx = len(ns) // 2     # 중간 데이터의 index
    leftNums = mSort(ns[0:midIdx])           # 0 ~ 중간값까지 분할
    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

        else:
            mergeNums.append(rightNums[rightIdx])
            rightIdx += 1

    mergeNums = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rightNums[rightIdx:]

    return mergeNums

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

퀵 정렬(quick sort)

재귀함수 사용
: 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.

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, 10, 6, 8]
print(f'qSort(nums): {qSort(nums)}')

📌 최빈값

# 최댓값 알고리즘
class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0   # 최댓값
        self.maxNumIdx = 0   #최댓값 index

    def setMaxIdxAndNum(self):    # 최댓값 & 그 index 구함
        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()    # 최댓값 & 그 index 설정
maxNum = maxAlo.getMaxNum()
print(f'maxNum: {maxNum}')

# 최댓값 길이만큼의 리스트 만듦
indexes = [0 for i in range(maxNum + 1)]

for n in nums:
    indexes[n] = indexes[n] + 1   # n 등장하면 index가 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}의 빈도수가 {maxNum}(으)로 가장 높다. ')

• 최빈값 실습

import random
import maxScore as ms

scores = []

for i in range(100):
    rn = random.randint(71, 100)
    if rn != 100: rn = rn - (rn % 5)  # 점수를 5단위로 재설정
    scores.append(rn)

print(f'scores: {scores}')

# 최댓값 알고리즘
maxAlo = ms.MaxAlgorithm(scores)
maxAlo.setMaxNumIdxAndNum()
maxNum = maxAlo.getMaxNum()

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

# index 리스트에 빈도 저장
for n in scores:
    indexes[n] = indexes[n] + 1

n = 1
while True:   # 빈도 출력

    maxAlo = ms.MaxAlgorithm(indexes)
    maxAlo.setMaxNumIdxAndNum()
    maxNum = maxAlo.getMaxNum()      #최댓값
    maxNumIdx = maxAlo.getMaxNumIdx()   #최댓값 index

    if maxNum == 0:
        break

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

    indexes[maxNumIdx] = 0       # 가장 높은 빈도수의 값 0으로 만듦

    n += 1

📌 재귀

• 하노이의 탑

# 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
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) # 3개의 원판을 1에서 3번 기둥으로 2번 기둥을 경유하여 이동