17번째 알고리즘 1~2 스터디 노트

내용요약

검색: 선형검색, 이진검색
순위: 순위
정렬: 버블정렬, 삽입정렬, 선택정렬

검색

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

# 실습 리스트에서 가장 앞에 있는 7을 검색하고 각각의 위치와 개수를 출력
# 선형검색
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdxs = []

nums.append(searchData)

n = 0
while True:

    if nums[n] == searchData:
        if n != len(nums) - 1:
            searchResultIdxs.append(n)
        else:
            break

    n += 1

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

# 보초법
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 n == len(datas):
    #     searchResultIdx = -1
    #     break

    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을 검색하고 위치 출력
# 이진검색
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print(f'nums: {nums}')

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

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

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

while searchData <= nums[len(nums)-1] and searchData >= nums[0]:

    if searchData == nums[len(nums)-1]:
        searchResultIdx = len(nums)-1
        break

    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx +  endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: [{searchResultIdx}]')

순위

• 순위
  수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다.
  

# 실습 학생 20명의 중간, 기말 성적을 이용해서 각각 순위를 구하고, 순위 변화를 출력
# 실행파일
import rankMod as rm
import random

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

rd = rm.RankDeviation(midStuScos, endStuScos)

rd.setMidRank()
print(f'midStuScos: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')

rd.printRankDeviation()

# 순위 클래스
import random

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

정렬

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

# 실습 20명의 키를 순서대로 정렬
# 실행파일 
import sortMod as sm
import random as rd

students = []

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

print(f'students: {students}')
print(f'students length: {len(students)}')

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

# 버블정렬 모듈
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

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

# 1부터 1000까지 난수 100개 생성한 후 오름,내림 차순으로 정렬하고 최대,최솟값 반환 
# 실행파일 
import random
import sortMod as sm

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

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

# ascending
sn.setSort()
sortedNumber = sn.getSortedNumbers()
print(f'sortedNumber by ASC: {sortedNumber}')

# descending
sn.isAscending(False)
sn.setSort()
sortedNumber = sn.getSortedNumbers()
print(f'sortedNumber by DESC: {sortedNumber}')

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

# 삽입정렬 클래스
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]

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

# 실습 20명의 시험점수를 오름, 내림순으로 정렬하는 모듈
# 실행파일
import random
import sortMod as sm
import copy

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

# ascending
# result = sm.sortNumber(scores)
result = sm.sortNumber(copy.deepcopy(scores))
print(f'result(ASC): {result}')

# descending
# result = sm.sortNumber(scores, asc=False)
result = sm.sortNumber(copy.deepcopy(scores), asc=False)
print(f'result(DESC): {result}')

# 선택정렬 모듈
def sortNumber(ns, asc=True):

    cnt = 0

    for i in range(len(ns) - 1):
        targetIdx = i

        for j in range(i + 1, len(ns)):
            if asc:
                if ns[targetIdx] > ns[j]:
                    targetIdx = j
                    cnt += 1
            else:
                if ns[targetIdx] < ns[j]:
                    targetIdx = j
                    cnt += 1

        ns[i], ns[targetIdx] = ns[targetIdx], ns[i]

    print(f'cnt: {cnt}')

    return ns

후기

알고리즘 단계가 어렵다고 해서 조금 걱정을 했는데 걱정보다 할 만했다. 파이썬에서 제공하는 함수를 사용하지 않고 한 단계씩 직접 알고리즘을 적용하여 실습해보니 재밌었지만 여러방법을 한번에 배우니까 알고리즘과 이름이 헷갈린다.

이글은 제로베이스 데이터 취업스쿨의 강의자료 일부를 발췌하여 작성되었습니다.