[알고리즘] 검색 알고리즘

선형검색 이란?

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

보초법

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

[연습문제]

리스트에서 가장 앞에 있는 숫자 ‘7’을 검색하고 위치(인덱스)를 출력하자.
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

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('찾으려는 숫자 입력: '))
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(f'찾으려는 {searchData}가(이) 없습니다.')
else:
    print(f'찾으려는 {searchData}의 위치(인덱스)는 {searchResultIdx}입니다.')

[연습문제]

리스트에서 숫자 ‘7’을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자.
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

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('찾으려는 숫자 입력: '))
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)}')

이진검색 이란?

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

[연습문제]

리스트를 오름차순으로 정렬한 후 ‘7’을 검색하고 위치(인덱스)를 출력하자.
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

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

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

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]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

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

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: [{searchResultIdx}]')

순위 란?

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

[연습문제]

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

• modual

import random

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