[제로베이스] 데이터 사이언스 12기 - (02-17 스터디노트)

오늘 수강한 강의 - 알고리즘(01 ~ 12)

01 선형 검색 ~ 04 이진 검색

선형 검색

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

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print('datas: {}'.format(datas))
print('datas length: {}'.format(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('searchResultIdx: {}'.format(searchResultIdx))

• 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 보초법이라고 한다

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print('datas: {}'.format(datas))
print('datas length: {}'.format(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('datas: {}'.format(datas))
print('datas length: {}'.format(len(datas)))
print('searchResultIdx: {}'.format(searchResultIdx))

• (실습) 리스트에서 가장 앞에 있는 숫자 '7'을 검색하고 위치(인덱스)를 출력하자

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print('nums: {}'.format(nums))
print('nums length: {}'.format(len(nums)))

searchData = int(input('input search number: '))
searchResultIdx = -1

nums.append(searchData)

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

    n += 1

print('nums: {}'.format(nums))
print('nums length: {}'.format(len(nums)))
print('searchResultIdx: {}'.format(searchResultIdx))

if searchResultIdx < 0:
    print('not search index')
else:
    print('search index: {}'.format(searchResultIdx))

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

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print('nums: {}'.format(nums))
print('nums length: {}'.format(len(nums)))

searchData = int(input('input search number: '))
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('nums: {}'.format(nums))
print('nums length: {}'.format(len(nums)))
print('searchResultIdxs: {}'.format(searchResultIdxs))
print('searchResultCnts: {}'.format(len(searchResultIdxs)))

이진 검색

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다
  (정렬되어 있어야 사용 가능)
  

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print('datas: {}'.format(datas))
print('datas length: {}'.format(len(datas)))

searchData = int(input('search data: '))
searchResultIdx = -1

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

while searchData <= datas[len(datas) - 1] and searchData >= datas[0]:
    if searchData == datas[len(datas) - 1]:
        searchResultIdx = len(datas) - 1
        break

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

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

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print('searchResultIdx: [{}]'.format(searchResultIdx))

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

 nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print('nums: {}'.format(nums))

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

searchData = int(input('search number: '))
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]

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print('searchResultIdx: {}'.format(searchResultIdx))

순위 05 ~ 06

순위

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

import random

nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]

print('nums: {}'.format(nums))
print('ranks: {}'.format(ranks))

for idx, num1 in enumerate(nums):
    for num2 in nums:
        if num1 < num2:
            ranks[idx] += 1

print('nums: {}'.format(nums))
print('ranks: {}'.format(ranks))

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

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

rankMod 모듈

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('mid_rank: {} \t end_rank: {} \t Deviation: {}'.format(mRank, self.endRanks[idx], deviation))

rankEx.py

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('midStuScors: {}'.format(midStuScos))
print('mid_rank: {}'.format(rd.getMidRank()))

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

rd.printRankDeviation()

07 버블 정렬 ~ 12 선택 정렬

버블 정렬

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

nums = [10, 2, 7, 21, 0]
print('not sorted nums: {}'.format(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(nums)
    print()

print('sorted nums: {}'.format(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

bubbleEx.py

import random as rd
import sortMod as sm

students = []

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

print('students: {}'.format(students))

깊은 복사

sortedStudent = sm.bubbleSort(students, deepCopy=True)

얕은 복사

sortedStudent = sm.bubbleSort(students, deepCopy=False)

print('students: {}'.format(students))
print('sortedStudents: {}'.format(sortedStudent))

삽입 정렬

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

오름차순

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

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('nums: {}'.format(nums))

내림차순

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

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('nums: {}'.format(nums))

• (실습) 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자

sortMod 모듈

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]

insertEx.py

import random
import sortMod as sm

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

# 객체 생성

sn = sm.SortNumbers(nums)

# 오름차순

sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print('sortedNumbers by ASC: {}'.format(sortedNumbers))

# 내림차순

sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print('sortedNumbers by DESC: {}'.format(sortedNumbers))

# 최대, 최솟값

print('min: {}'.format(sn.getMinNumber()))
print('max: {}'.format(sn.getMaxNumber()))

선택 정렬

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

nums = [4, 2, 5, 1, 3]
print('nums: {}'.format(nums))

for i in range(len(nums) - 1):
    minIdx = i

    for j in range(i + 1, len(nums)):
        if nums[minIdx] > nums[j]:
            minIdx = j

    nums[i], nums[minIdx] = nums[minIdx], nums[i]
    print('nums: {}'.format(nums))

print('fianl nums: {}'.format(nums))

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

sortMod 모듈

def sortNumber(ns, asc=True):

    if asc:
        for i in range(len(ns) - 1):
            minIdx = i
            for j in range(i + 1, len(ns)):
                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)):
                if ns[minIdx] < ns[j]:
                    minIdx = j
            ns[i], ns[minIdx] = ns[minIdx], ns[i]

    return ns

selectionSortEx.py

import random
import sortMod as sm
import copy

scores = random.sample(range(50, 100), 20)

copy.deepcopy()로 원본을 훼손하지않고 가져올 수 있음

print('scores: {}'.format(scores))
result = sm.sortNumber(copy.deepcopy(scores))
print('result: {}'.format(result))

print('scores: {}'.format(scores))
result = sm.sortNumber(copy.deepcopy(scores), asc=False)
print('result: {}'.format(result))

재미있었던 부분

버블 정렬, 삽입 정렬을 이용하여 숫자를 확인하고 오름차순 내림차순으로 정렬하는 코드를 만들어본 것이 가장 기억에 남고 이해가 잘된 부분이었던 것 같다

어려웠던 부분

정렬 부분의 모듈은 혼자 만들어보다가 오류가 나거나 해설과 다른 부분이 있어서 확인하고 이해를 다시 하느라 더 오래걸렸던 것 같다
아직은 헷갈린다

느낀점 및 내일 학습 계획

강의를 따라갈때는 이해하고 넘어갔다고 생각했는데 막상 문제를 혼자 풀어보려 하니 틀린부분도 있고 막막할때도 있었다
특히 모듈이 그렇다 모듈에 익숙해지고 싶다
모듈 부분은 자주 봐야겠다
내일은 주말이다 복습과 알고리즘 공부를 더 할 에정이다