230926_스터디노트(2)

Sihyun Kim·2023년 9월 26일

알고리즘

01_선형검색

알고리즘: 어떠한 문제를 풀기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것.

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

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]

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

n = 0
while True:
    if n == len(datas):
        break
    elif datas[n] == searchData:
        searchResultIdx = n
        break
        
    n += 1

print(searchResultIdx)

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

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]

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(searchResultIdx)

02_선형검색(실습)

리스트에서 가장 앞에 있는 7을 검색하고 인덱스 출력

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

searchNum = 7
searchIdx = -1

n = 0
while True:
    if nums[n] == searchNum:
        searchIdx = n
        break

    n += 1

print(searchIdx)

리스트에서 7을 모두 검색하고 각각의 인덱스와 검색 개수 출력

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

searchNum = 7
searchIdx = -1
searchIdxList = []
searchCnt = 0

n = 0
while True:
    if n >= len(nums):
        break

    elif nums[n] == searchNum:
        searchIdx = n
        searchIdxList.append(n)
        print(f'숫자 7의 인덱스: {searchIdx}')
        searchCnt += 1

    n += 1

print(f'숫자 7의 인덱스 리스트: {searchIdxList}')
print(f'숫자 7의 개수: {searchCnt}')

🙄

앞으로는 보초법에 익숙해져야 하는 듯?!

n = 0
while True:
    if nums[n] == searchNum:
        if n != len(nums) - 1:
            searchIdxList.append(n)
            searchCnt += 1
        else: break

    n += 1

print(f'숫자 7의 인덱스 리스트: {searchIdxList}')
print(f'숫자 7의 개수: {searchCnt}')

03_이진 검색

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

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

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

searchData = int(input('숫자 입력: '))
searchIdx = -1

while searchData in datas:
    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]

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

    elif searchData == midVal:
        searchIdx = midIdx
        break

print(f'searchIdx: {searchIdx}')

04_이진 검색(실습)

7을 찾고 인덱스를 출력하기

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

nums.sort()

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

while searchData in nums:
    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:
        searchIdx = midIdx
        break

print(f'{searchData}의 인덱스: {searchIdx}')

05_순위

수의 크고 작음을 이용해서 수의 순서를 정하는 것

import random
numsList = random.sample(range(50,100), 20)
rankList = [0 for i in range(20)]
print(numsList)

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

for i in range(len(numsList)):
    print(f'{numsList[i]}: {rankList[i] + 1}위')

06_순위(실습)

class Deviation:

    def __init__(self, ms, es):
        self.midscore = ms
        self.finScore = es
        self.midRank = [0 for i in range(len(ms))]
        self.finRank = [0 for i in range(len(ms))]
        self.deviation = [0 for i in range(len(ms))]

    def setRank(self, list1, list2):
        for idx, score1 in enumerate(list1):
            for score2 in list1:
                if score1 < score2:
                    list2[idx] += 1

    def setMidRank(self):
        self.setRank(self.midscore, self.midRank)

    def getMidRank(self):
        return self.midRank

    def setFinRank(self):
        self.setRank(self.finScore, self.finRank)

    def getFinRank(self):
        return self.finRank

    def printRankDeviation(self):

        for idx, midR in enumerate(self.midRank):
            deviation = midR - self.finRank[idx]

            if deviation > 0:
                dev = '↑' + str(abs(deviation))
            elif deviation < 0:
                dev = '↓' + str(abs(deviation))
            elif deviation == 0:
                dev = '=' + str(0)

            print(f'mid: {self.midRank[idx]} \t\t fin: {self.finRank[idx]} \t dev: {dev}')

import random
import rankMod as rm

midScores = random.sample(range(50,100), 20)
finScores = random.sample(range(50,100), 20)

rd = rm.Deviation(midScores, finScores)
rd.setMidRank()
rd.setFinRank()
print(rd.getMidRank())
print(rd.getFinRank())
rd.printRankDeviation()

07_버블 정렬

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

nums = [10, 2, 7, 21, 0]
print(f'not sorted: {nums}')

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

        print(nums)
        

print(f'sorted: {nums}')

08_버블 정렬(실습)

20명의 키를 랜덤으로 정하고, 줄을 세워보자

# 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

import random
import sortMod as sm

stdList = []
for i in range(20):
    stdList.append(random.randrange(170, 186))

print(stdList)

sortedStdList = sm.bubblesort(stdList) #(stdList, deepCopy=False)하면 원본 데이터 이용
 
print(stdList)
print(sortedStdList)

깊은 복사 import copy / deepCopy=True / copy.copy() < 기억하기!
def 선언 후에 사용하기

09_삽입 정렬

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

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)