스터디 노트 (알고리즘 1-18)_0724

📌 선형검색?

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

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): #만약 n의 값이 datas의 길이의 값과 같아질 경우
        searchResultIdx = -1 #못찾았으므로 -1 출력
        break #바로 break

    elif datas[n] == searchData: #datas n의 값이 찾으려는 data값과 같다면
        searchResultIdx = n # 찾으려는 data값의 idx는 n의 값이다
        break #바로 break

    n+=1 #못찾을 때 무한루프에 빠지지 않도록 n을 1씩 더해준다

print(f'searchResultIdx = {searchResultIdx}')

>>>>
datas : [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
datas length : 10
찾으려는 숫자 입력 : 10
searchResultIdx = -1

📌 보초법

• 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화 한다.

출처 : 제로베이스 데이터 스쿨

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 #기본으로 idx를 지정한다

datas.append(searchData) #기본적으로 입력받은 숫자를 datas에 append한다.

n = 0

while True:

    if datas[n] == searchData: #만약 datas[n]의 데이터값이 입력받은 숫자와 같고
        if n != len(datas) - 1: #datas의 길이가 n의 값과 같지않다면
            searchResultIdx = n #입력받은 숫자의 idx는 n이다
        break
    n+=1 #무한루프에 빠지지 않도록 n을 계속 더해준다
print(f'datas : {datas}')
print(f'datas length : {len(datas)}')
print(f'searchResultIdx : {searchResultIdx}')
>>>>
datas : [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
datas length : 10
찾으려는 숫자 입력 : 10
datas : [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 10]
datas length : 11
searchResultIdx : -1

📌 이진검색

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

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

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

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

endIdx = len(datas) - 1 # index = 10
midIdx = (staIdx + endIdx) // 2 # 0 + 10 // 2 -> 5
midVal = datas[midIdx] # data[5]의 값

print(f'midIdx : {midIdx}')
print(f'midVal : {midVal}')
n = 0

while searchData <= datas[len(datas) - 1] and searchData >= datas[0]:
# 입력받은 데이터 <= datas의 마지막 노드 and 입력받은 데이터 >= datas의 첫번째 노드
# 즉 데이터가 datas 값의 사이에 있을 때

    if searchData == datas[len(datas) - 1]: #입력받은 데이터가 datas의 마지막 노드값과 같을 때
        searchResultIdx = len(datas) - 1 #데이터의 Idx는 datas의 마지막 노드의 idx와 같다
        break #무한루프에 빠지지 않도록 break

    if searchData > midVal: #입력받은 데이터가 중간값보다 클 때
        staIdx = midIdx #시작은 중간의 idx값
        midIdx = (staIdx + endIdx) // 2 #중간은 시작과 끝 idx를 더하고 2로 나눈 몫
        midVal = datas[midIdx] #중간의 밸류는 datas에 구한 midIdx를 넣은 값이된다
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')

    elif searchData < midVal: #입력받은 데이터가 중간값보다 작을 때
        endIdx = midIdx #끝의 값은 중간값이 된다
        midIdx = (staIdx + endIdx) // 2 #시작값과 끝의 값의 idx를 더하고 2로 나눈 몫
        midVal = datas[midIdx] # 중간의 밸류는 datas에 구한 midIdx를 넣은 값이다.
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')

    elif searchData == midVal: #입력받은 데이터와 중간값이 같을 때
        searchResultIdx = midIdx #데이터의 Idx는 중간값의 Idx와 같다
        break

print(f'searchResultIdx : {searchResultIdx}')
>>>>
datas : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length : 11
search data : 4
midIdx : 5
midVal : 6

midIdx : 2
midVal : 3

midIdx : 3
midVal : 4
searchResultIdx : 3

📌 순위

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

출처 : 제로베이스 데이터 스쿨

import random

nums = random.sample(range(50, 101), 20) # 50~100 사이의 난수 20개를 뽑아냄
ranks = [0 for i in range (20)] #길이가 20이고 데이터의 값은 0인 리스트가 만들어짐
print(f'nums : {nums}')
print(f'ranks : {ranks}')

for idx, num1 in enumerate(nums): #random nums의 idx, num1을 뽑아온다.
    for num2 in nums: #중첩 반복문을 사용하여 num2를 뽑아온다. (기준이되는 숫자와 비교하기 위함)
        if num1 < num2: #num2가 num1보다 크다면 (기준이 되는 num1보다 num2가 크다면)
            ranks[idx] += 1 #rank안에 있는 해당 idx 숫자에 1씩 계속해서 더한다

print(f'nums : {nums}')
print(f'ranks : {ranks}')

for idx, num in enumerate(nums): #for문을 통해 idx, num을 추출하고
    print(f'num : {num} \t rank : {ranks[idx] + 1}') #각각의 순위와 숫자를 나열해준다

>>>>
nums : [59, 71, 98, 67, 85, 69, 91, 72, 77, 57, 97, 99, 74, 53, 86, 66, 58, 89, 78, 51]
ranks : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
nums : [59, 71, 98, 67, 85, 69, 91, 72, 77, 57, 97, 99, 74, 53, 86, 66, 58, 89, 78, 51]
ranks : [15, 11, 1, 13, 6, 12, 3, 10, 8, 17, 2, 0, 9, 18, 5, 14, 16, 4, 7, 19]
num : 59 	 rank : 16
num : 71 	 rank : 12
num : 98 	 rank : 2
num : 67 	 rank : 14
num : 85 	 rank : 7
num : 69 	 rank : 13
num : 91 	 rank : 4
num : 72 	 rank : 11
num : 77 	 rank : 9
num : 57 	 rank : 18
num : 97 	 rank : 3
num : 99 	 rank : 1
num : 74 	 rank : 10
num : 53 	 rank : 19
num : 86 	 rank : 6
num : 66 	 rank : 15
num : 58 	 rank : 17
num : 89 	 rank : 5
num : 78 	 rank : 8
num : 51 	 rank : 20

📌 순위 편차

#모듈코드
class RankDeviation:

    def __init__(self, mss, ess): #중간고사, 기말고사 score를 받는다
        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): #중간고사 성적 랭크를 setRank에 던진다
        self.setRank(self.midStuScos, self.midRanks)

    def getMidRank(self):
        return self.midRanks

    def setEndRank(self): #기말고사 성적 랭크를 setRank에 던진다
        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}')

#실행코드
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'midRank : {rd.getMidRank()}')

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

rd.printRankDeviation()
>>>>
midStuScos : [86, 67, 59, 84, 76, 51, 62, 74, 66, 70, 77, 75, 95, 60, 69, 53, 61, 78, 94, 97]
midRank : [3, 12, 17, 4, 7, 19, 14, 9, 13, 10, 6, 8, 1, 16, 11, 18, 15, 5, 2, 0]
endStuScos : [99, 92, 96, 50, 57, 78, 77, 79, 80, 52, 87, 70, 65, 95, 60, 55, 88, 81, 94, 56]
endRank : [0, 4, 1, 19, 15, 10, 11, 9, 8, 18, 6, 12, 13, 2, 14, 17, 5, 7, 3, 16]
mid_rank : 3 	 end_rank : 0 	 Deviation : ↑3
mid_rank : 12 	 end_rank : 4 	 Deviation : ↑8
mid_rank : 17 	 end_rank : 1 	 Deviation : ↑16
mid_rank : 4 	 end_rank : 19 	 Deviation : ↓15
mid_rank : 7 	 end_rank : 15 	 Deviation : ↓8
mid_rank : 19 	 end_rank : 10 	 Deviation : ↑9
mid_rank : 14 	 end_rank : 11 	 Deviation : ↑3
mid_rank : 9 	 end_rank : 9 	 Deviation : =0
mid_rank : 13 	 end_rank : 8 	 Deviation : ↑5
mid_rank : 10 	 end_rank : 18 	 Deviation : ↓8
mid_rank : 6 	 end_rank : 6 	 Deviation : =0
mid_rank : 8 	 end_rank : 12 	 Deviation : ↓4
mid_rank : 1 	 end_rank : 13 	 Deviation : ↓12
mid_rank : 16 	 end_rank : 2 	 Deviation : ↑14
mid_rank : 11 	 end_rank : 14 	 Deviation : ↓3
mid_rank : 18 	 end_rank : 17 	 Deviation : ↑1
mid_rank : 15 	 end_rank : 5 	 Deviation : ↑10
mid_rank : 5 	 end_rank : 7 	 Deviation : ↓2
mid_rank : 2 	 end_rank : 3 	 Deviation : ↓1
mid_rank : 0 	 end_rank : 16 	 Deviation : ↓16

📌 버블정렬

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

출처 : 제로베이스 데이터 스쿨

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

length = len(nums) - 1

for i in range (length):
#범주 내의 숫자 안에서 (마지막 노드는 선택x)
    for j in range (length - i):
    #이미 교환된 노드는 맨 뒤 쪽으로 배치가 되어있기 때문에
        if nums[j] > nums[j+1]:
        #J인덱스에 있는 값이 j+1 인덱스 값보다 크다면
            # temp = nums[j]
            # nums[j] = nums[j+1]
            # nums[j + 1] = temp
            nums[j], nums[j+1] = nums[j+1], nums[j]
            #숫자를 서로 교환한다 (바꾼다)

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

[2, 7, 10, 0, 21]
[2, 7, 10, 0, 21]
[2, 7, 0, 10, 21]

[2, 7, 0, 10, 21]
[2, 0, 7, 10, 21]

[0, 2, 7, 10, 21]

sorted nums : [0, 2, 7, 10, 21]

📌 버블정렬 (실습)

• 키 순으로 정렬해보기

#모듈코드
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 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'students: {students}')
print(f'sortedStudents: {sortedStudents}')
>>>>
students: [176, 173, 176, 173, 181, 182, 172, 178, 182, 184, 177, 179, 180, 171, 179, 181, 175, 176, 174, 179]
students: [176, 173, 176, 173, 181, 182, 172, 178, 182, 184, 177, 179, 180, 171, 179, 181, 175, 176, 174, 179]
sortedStudents: [171, 172, 173, 173, 174, 175, 176, 176, 176, 177, 178, 179, 179, 179, 180, 181, 181, 182, 182, 184]

📌 삽입정렬

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

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

#ascending
for i1 in range(1, len(nums)):
    i2 = i1 - 1
    cNum = nums[i1]

    while nums[i2] > cNum and i2 >= 0: #i2의 값이 이전에 정렬되어있는 숫자보다 크다면
        nums[i2 + 1] = nums[i2] #두개의 값을 치환
        i2 -= 1

    nums[i2 + 1] = cNum

    print(f'nums:{nums}')

print()
#descending
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(f'nums:{nums}')
>>>>
nums:[5, 10, 2, 1, 0]
nums:[2, 5, 10, 1, 0]
nums:[1, 2, 5, 10, 0]
nums:[0, 1, 2, 5, 10]

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

📌 삽입정렬 (실습)

출처 : 제로베이스 데이터 스쿨

#모듈코드
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]

#실행코드
import random
import sortMod as sm

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

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

# 오름차순(ascending)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(sortedNumbers)

# 내림차순(descending)
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(sortedNumbers)

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

📌 선택정렬

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

출처 : 제로베이스 데이터 스쿨

nums = [4, 2, 5, 1, 3]
print(f'nums : {nums}')
for i in range (len(nums) - 1):
    minIdx = i #최소값이 들어있는 index 설정
    for j in range (i+1, len(nums)):
        if nums[minIdx] > nums[j]:
            minIdx = j
    # tempNum = nums[i]
    # nums[i] = nums[minIdx]
    # nums[minIdx] = tempNum

    nums[i], nums[minIdx] = nums[minIdx], nums[i]
    print(f'nums : {nums}')
print(f'final nums : {nums}')
>>>>
nums : [4, 2, 5, 1, 3]
nums : [1, 2, 5, 4, 3]
nums : [1, 2, 5, 4, 3]
nums : [1, 2, 3, 4, 5]
nums : [1, 2, 3, 4, 5]
final nums : [1, 2, 3, 4, 5]

📌 최댓값

출처 : 제로베이스 데이터 스쿨

class MaxAlgorithm:

    def __init__(self, ns): #객체 초기화
        self.nums = ns
        self.maxNum = 0

    def getMaxNum(self):

        self.maxNum = self.nums[0]

        for n in self.nums:
            if self.maxNum < n:
                self.maxNum = n

        return self.maxNum

max = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
print(f'max Num : {max.getMaxNum()}')

class MaxAlgorithm:

    def __init__(self, cs):
        self.chars = cs
        self.maxChar = 0

    def getMaxchar(self):

        self.maxChar = self.chars[0]

        for c in self.chars:

            if ord(self.maxChar) < ord(c):
                self.maxChar = c

        return self.maxChar


chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = MaxAlgorithm(chars)
maxChar = mc.getMaxchar()
print(f'maxChar : {maxChar}')

📌 최솟값

class MinAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.minNum = 0

    def getMinnum(self):
        self.minNum = self.nums[0]

        for n in self.nums:
            if self.minNum > n:
                self.minNum = n

        return self.minNum

nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]

mn = MinAlgorithm(nums)
minNum = mn.getMinnum()
print(f'minNum : {minNum}')

#아스키 코드 값 최소
class MinAlgorithm:

    def __init__(self, cs):
        self.chars = cs
        self.minChar = 0

    def getMinChar(self):
        self.minChar = self.chars[0]

        for c in self.chars:
            if ord(self.minChar) > ord(c):
                self.minChar = c

        return self.minChar

chars = (['c', 'x', 'Q', 'A', 'e', 'P', 'p'])
mc = MinAlgorithm(chars)
minChar = mc.getMinChar()

print(f'minChar : {minChar}')

📌 최빈값

• 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다.

출처 : 제로베이스 데이터 스쿨

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumIdx = 0

    def setMaxIdxAndNum(self):
        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]
mn = MaxAlgorithm(nums)
mn.setMaxIdxAndNum()
maxNumIdx = mn.getMaxNumIdx()
maxNum = mn.getMaxNum()

print(f'maxNum Idx : {maxNumIdx}')
print(f'maxNum : {maxNum}')

indexes = [0 for i in range(maxNum + 1)]
print(f'indexes : {indexes}')
print(f'indexes length : {len(indexes)}')

for n in nums:
    indexes[n] = indexes[n] + 1 #해당되는 indexes의 인덱스에 +1

print(f'indexes : {indexes}')

maxAgo = MaxAlgorithm(indexes)
maxAgo.setMaxIdxAndNum()
maxNum = maxAgo.getMaxNum()
maxNumIdx = maxAgo.getMaxNumIdx()
print(f'{maxNum}')
print(f'{maxNumIdx}')
>>>>
maxNum Idx : 9
maxNum : 17
indexes : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
indexes length : 18
indexes : [0, 1, 0, 1, 0, 0, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
4
7