21.자료구조와 알고리즘-4

SOWA·2023년 3월 24일
0

🧷 알고리즘

🖇️선형 검색

선형으로 나열되어있는 데이터를 순차적으로 스캔하면서 원하는 값이 있는지 없는지 판단

🖇️보초법

마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화
내가 찾으려는 값을 선형 검색으로 찾다가 마지막에 찾으면 검색실패, 중간에 찾으면 검색 성공하는 판단법

data = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4] ##맨 끝에서 찾으려는 값을 찾았다면 찾은게 아님= 검색 실패/ 마지막 이전에 찾으려는 값을 찾으면= 검색 성공
print(f'data: {data}')
print(f'data length: {len(data)}')

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

data.append(searchData)

n = 0
while True:

    if data[n] == searchData:
        if n != len(data) -1:
            searchResultIdx = n
        break

    n += 1

print(f'data: {data}')
print(f'data length: {len(data)}')
print(f'SearchResultIdx: [{searchResultIdx}]')

#검색 성공
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
data length: 10
찾으려는 숫자 입력: 0
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 0]
data length: 11
SearchResultIdx: [6]
#검색실패
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
data length: 10
찾으려는 숫자 입력: 11
data: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 11]
data length: 11
SearchResultIdx: [-1]

🖇️ 이진검색

정렬되어있는 자료구조에서 중앙값과의 크고 작음을 이용하여 데이터 검색
자료가 정렬되어있지 않다면 자료를 먼저 정렬해야함

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

nums.sort()

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]

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

    elif searchData == midVal:
        searchResultIdx = mididx
        break

print(f'searchResultIdx: {searchResultIdx}')

찾으려는 숫자 입력: 7
searchResultIdx: 3


🖇️순위

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

  • 학급 학생(20명)들의 중간고사와 기말고사 성적을 이용하여 각각의 순위를 구하고, 중간고사 대비 기말고사 순위 변화(평차)출력(시험성적은 난수 이용)
##모듈
class RankDeviation:
    def __init__(self, mss, ess):
        self.midStuScores = mss
        self.endStuScores = ess
        self.midRank = [0 for i in range(len(mss))]
        self.endRank = [0 for i in range(len(mss))]
        self.rankDevi = [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.midStuScores, self.midRank)


    def setEndRank(self):
        self.setRank(self.endStuScores, self.endRank)

    def getMidRank(self):
        return self.midRank

    def setEndRank(self):
        self.setRank(self.endStuScores, self.endRank)

    def getEndRank(self):
        return self.endRank
    def printRankDeviation(self):

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

            if deviation > 0:
                deviation = '↑' + str(abs(deviation)) #abs()=절대값 함수

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

            else:
                deviation = '=' + str(abs(deviation))

            print(f'mid rank: {mRank} \t end rank: {self.endRank[idx]} \t deviation: {deviation}')
##실행
import rankkk as rk
import random

midStuScores = random.sample(range(50, 101), 20)
endStuScores = random.sample(range(50, 101), 20)

rd = rk.RankDeviation(midStuScores, endStuScores)
rd.setMidRank()
print(f'midStuScores: {midStuScores}')
print(f'mid rank: {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScores: {endStuScores}')
print(f'end rank: {rd.getEndRank()}')

rd.printRankDeviation()

midStuScores: [94, 99, 57, 62, 67, 61, 89, 93, 63, 92, 78, 55, 64, 73, 100, 79, 88, 71, 75, 95]
mid rank: [3, 1, 18, 16, 13, 17, 6, 4, 15, 5, 9, 19, 14, 11, 0, 8, 7, 12, 10, 2]
endStuScores: [59, 88, 83, 63, 60, 58, 86, 70, 73, 53, 80, 56, 79, 69, 50, 64, 75, 87, 90, 97]
end rank: [15, 2, 5, 13, 14, 16, 4, 10, 9, 18, 6, 17, 7, 11, 19, 12, 8, 3, 1, 0]
mid rank: 3 	 end rank: 15 	 deviation:12
mid rank: 1 	 end rank: 2 	 deviation:1
mid rank: 18 	 end rank: 5 	 deviation:13
mid rank: 16 	 end rank: 13 	 deviation:3
mid rank: 13 	 end rank: 14 	 deviation:1
mid rank: 17 	 end rank: 16 	 deviation:1
mid rank: 6 	 end rank: 4 	 deviation:2
mid rank: 4 	 end rank: 10 	 deviation:6
mid rank: 15 	 end rank: 9 	 deviation:6
mid rank: 5 	 end rank: 18 	 deviation:13
mid rank: 9 	 end rank: 6 	 deviation:3
mid rank: 19 	 end rank: 17 	 deviation:2
mid rank: 14 	 end rank: 7 	 deviation:7
mid rank: 11 	 end rank: 11 	 deviation: =0
mid rank: 0 	 end rank: 19 	 deviation:19
mid rank: 8 	 end rank: 12 	 deviation:4
mid rank: 7 	 end rank: 8 	 deviation:1
mid rank: 12 	 end rank: 3 	 deviation:9
mid rank: 10 	 end rank: 1 	 deviation:9
mid rank: 2 	 end rank: 0 	 deviation:2


🖇️ 버블 정렬

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

  • 새학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄을 세워보자. 키는 랜덤모듈을 이용하여 170~185사이로 생성.
##모듈
import copy
def bubbleSort(ns, deepCopy = True):

    if deepCopy:
        cns = copy.copy(ns) ##students를 몽땅 카피에서 새로운 students를 생성
    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  bubble as bb
import random as rd

students = []

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

print(f'students: {students}')

sortedStudents = bb.bubbleSort(students,  deepCopy=True)

print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')

students: [175, 171, 179, 185, 174, 183, 178, 172, 179, 176, 170, 178, 181, 174, 180, 178, 182, 170, 179, 178]
students: [175, 171, 179, 185, 174, 183, 178, 172, 179, 176, 170, 178, 181, 174, 180, 178, 182, 170, 179, 178]
sortedStudents: [170, 170, 171, 172, 174, 174, 175, 176, 178, 178, 178, 178, 179, 179, 179, 180, 181, 182, 183, 185]


🖇️ 삽입정렬

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

  • 1부터 1000까지의 난수 100개 생성후 요구 사항을 만족하는 모듈 생성
    1)생성된 난수들을 오름차순 또는 내림차순으로 정렬하는 알고리즘구현
    2)생성된 난수중 최소값, 최대값을 반환하는 함수 구현
##모듈
class InsertArr:

    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 insertarrange as ir

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

#객체 생성

sn = ir.InsertArr(nums)

# 오름차순(ascending)

sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by asc: {sortedNumbers}')

##내림차순(descending)

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

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

not sorted numbers: [86, 687, 675, 735, 106, 859, 886, 891, 459, 558, 108, 927, 66, 666, 271, 937, 802, 566, 299, 996, 681, 847, 887, 105, 340, 779, 225, 637, 239, 457, 852, 966, 726, 28, 657, 123, 591, 441, 416, 532, 773, 957, 152, 391, 308, 529, 323, 458, 550, 117, 444, 827, 34, 863, 29, 432, 84, 396, 505, 200, 866, 740, 329, 236, 318, 183, 96, 216, 330, 809, 800, 613, 544, 175, 745, 161, 195, 536, 991, 974, 860, 636, 286, 651, 765, 737, 379, 851, 921, 250, 132, 51, 332, 569, 158, 571, 724, 512, 547, 764]
sortedNumbers by asc: [28, 29, 34, 51, 66, 84, 86, 96, 105, 106, 108, 117, 123, 132, 152, 158, 161, 175, 183, 195, 200, 216, 225, 236, 239, 250, 271, 286, 299, 308, 318, 323, 329, 330, 332, 340, 379, 391, 396, 416, 432, 441, 444, 457, 458, 459, 505, 512, 529, 532, 536, 544, 547, 550, 558, 566, 569, 571, 591, 613, 636, 637, 651, 657, 666, 675, 681, 687, 724, 726, 735, 737, 740, 745, 764, 765, 773, 779, 800, 802, 809, 827, 847, 851, 852, 859, 860, 863, 866, 886, 887, 891, 921, 927, 937, 957, 966, 974, 991, 996]
sortedNumbers by dsc: [996, 991, 974, 966, 957, 937, 927, 921, 891, 887, 886, 866, 863, 860, 859, 852, 851, 847, 827, 809, 802, 800, 779, 773, 765, 764, 745, 740, 737, 735, 726, 724, 687, 681, 675, 666, 657, 651, 637, 636, 613, 591, 571, 569, 566, 558, 550, 547, 544, 536, 532, 529, 512, 505, 459, 458, 457, 444, 441, 432, 416, 396, 391, 379, 340, 332, 330, 329, 323, 318, 308, 299, 286, 271, 250, 239, 236, 225, 216, 200, 195, 183, 175, 161, 158, 152, 132, 123, 117, 108, 106, 105, 96, 86, 84, 66, 51, 34, 29, 28]
min: 28
max: 996


🖇️선택정렬

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

nums = [4, 2, 5, 1, 3]

for i in range(len(nums)-1):
    minIdx = i
    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'nums: {nums}')

nums: [1, 2, 5, 4, 3]
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 3, 4, 5]
nums: [1, 2, 3, 4, 5]
nums: [1, 2, 3, 4, 5]

- 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈 제작. 시험점수는 50부터 100까지
#모듈
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
##실행
import random
import selectArr as sa

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

result = sa.sortNumber(scores)
print(f'result: {result}')

result = sa.sortNumber(scores, asc=False)
print(f'result: {result}')

Scores: [96, 84, 88, 51, 83, 95, 59, 62, 66, 72, 58, 99, 98, 80, 81, 71, 73, 55, 77, 78]
scores length: 20
result: [51, 55, 58, 59, 62, 66, 71, 72, 73, 77, 78, 80, 81, 83, 84, 88, 95, 96, 98, 99]
result: [99, 98, 96, 95, 88, 84, 83, 81, 80, 78, 77, 73, 72, 71, 66, 62, 59, 58, 55, 51]


🖇️ 최대값

자료구조에서 가장 큰 값

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

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

Max Num: 20


from.제로베이스 데이터 취업스쿨 강의

0개의 댓글