[3주차] 알고리즘 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

n = 0
while True:

    if n == len(datas):
        searchResultIdx = -1
        break

    elif datas[n] == searchData:
        searchResultIdx = n
        break

    n += 1

print(f'searchResultIdx: {searchResultIdx}')

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

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 datas[n] == searchData:
        if n != len(datas) -1:
            searchResultIdx = n
        break

    n += 1

print(f'searchResultIdx: {searchResultIdx}')

• 선형검색 실습 1)
  -> 리스트에서 가장 앞에 있는 숫자 '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('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(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdx: {searchResultIdx}')

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

• 실습 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('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(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdxs: {searchResultIdxs}')
print(f'searchResultCnts: {(len(searchResultIdxs))}')

[이진검색]

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

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

startIdx = 0
endIdx = len(datas) -1
midIdx = (startIdx + endIdx) // 2
midval = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midval: {midval}')

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

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

    if searchData > midval:     # 검색 범위 재조정
        startIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midval = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midval: {midval}')

    elif searchData < midval:
        endIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midval = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midval: {midval}')

    elif searchData == midval:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: {searchResultIdx}')

• 이진검색 실습 1)
  -> 리스트를 오름차순으로 정렬하고 '7'을 검색하고 위치(인덱스)를 출력하자.

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

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

startIdx = 0
endIdx = len(nums) -1
midIdx = (startIdx + 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:
        startIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midval = nums[midIdx]

    elif searchData < midval:
        endIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midval = nums[midIdx]

    elif searchData == midval:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: {searchResultIdx}')

[순위]

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

import random

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

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

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

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

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

• 순위 실습)
  -> 학급 학생(20명)들의 중간고사와 기말고사 성적을 이용해 각각의 순위를 구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력하자.
  -> 모듈: rankMod

모듈: 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(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'mid_rank: {rd.getMidRank()}')

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

rd.printRankDeviation()