[제로베이스] CH3. 알고리즘 - 선형탐색, 이진탐색, 순위

선형 탐색

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

datas = [3,2,5,7,9,1,0,8,6,4]
length = len(datas)
print(f'datas : {datas}')
print(f'datas length : {length}')

searchData = int(input('찾으려는 데이터 입력 : '))
searchDataIdx = -1


n = 0
while (True) :
    
    if	n == length:
    	break
        
    if datas[n] == searchData :
        searchDataIdx = n
        break
    n += 1
    
if searchDataIdx == -1:
    print(f'No data!')
else:
    print(f'Data index is : {searchDataIdx}')

보초법

마직막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화하는 방법이다. 종료 조건중 검색 실패 조건을 제거하여 판단 횟수를 줄이는 방법입니다.

마지막 인덱스에 찾으려는 값을 추가하면, 종료 조건을 반복문에 안넣어도 된다. 어차피 무조건 찾으니까... 찾는데 마지막 인덱스 번호냐, 그 전이냐 판단만 하면 된다.

datas = [3,2,5,7,9,1,0,8,6,4]
length = len(datas)
print(f'datas : {datas}')
print(f'datas length : {length}')

searchData = int(input('찾으려는 데이터 입력 : '))
searchDataIdx = -1
datas.append(searchData)
length = len(datas)

n = 0
while (True) :
    
    ## 반복문에서 n이 length와 같은지 판단 안해도 된다.##
    
    if datas[n] == searchData :
        searchDataIdx = n
        break
    n += 1
    
if searchDataIdx == length-1:
    print(f'No data!')
else:
    print(f'Data index is : {searchDataIdx}')    

이진 탐색

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

datas = [3,2,5,7,9,1,0,8,6,4]
length = len(datas)
print(f'datas : {datas}')
print(f'datas length : {length}')

datas.sort()

searchData = int(input('찾으려는 데이터 입력 : '))
searchDataIdx = -1

startIdx = 0
endIdx = len(datas)-1
midIdx = (startIdx+endIdx)//2
midValue = datas[midIdx]

while (startIdx >0 and endIdx < len(datas)-1):
    if searchData < midValue :
        #startIdx = 0
        endIdx = midIdx-1
        midIdx = (startIdx+endIdx)//2
        midValue = datas[midIdx]

    if searchData > midValue :
        startIdx = midIdx+1
        #endIdx = len(datas)-1
        midIdx = (startIdx+endIdx)//2
        midValue = datas[midIdx]
    
    elif searchData == midValue :
        searchDataIdx = midIdx
        break

if searchDataIdx == -1:
    print(f'No data!')
else:
    print(f'Data index is : {searchDataIdx}')

이진 탐색은 재귀함수로도 많이 구현한다.

datas = [3,2,5,7,9,1,0,8,6,4]
length = len(datas)
print(f'datas : {datas}')
print(f'datas length : {length}')

datas.sort()

searchData = int(input('찾으려는 데이터 입력 : '))
searchDataIdx = -1

def binarysearch(start, end, datas,searchData):
    if (start > len(datas)-1 or end < 0 ) :
        return -1
        
    midIdx = (start+end)//2
    midValue = datas[midIdx]
        
    if searchData < midValue :
        return binarysearch(start,midIdx-1,datas,searchData)

    if searchData > midValue :
        return binarysearch(midIdx+1,end,datas,searchData)
    
    elif searchData == midValue :
        return midIdx
    
result = binarysearch(0,len(datas)-1,datas,searchData)

if result == -1:
    print(f'No data!')
else:
    print(f'Data index is : {result}')

순위 알고리즘

순위 알고리즘(Ranking Algorithm)은 데이터셋에서 각 항목의 순위를 매기는 알고리즘이다. 일반적으로 순위 알고리즘은 대회에서의 성적이나 검색 엔진에서의 검색 결과 등에 사용된다.

scores = [26,100,50,70,60,90,55,35,80,99]
#rank = [len(scores)]*len(scores)

def ranking_algorithm(scores):
    n = len(scores)
    rank = [n]*n

    for i in range(n):
        rank[i] = n
        for j in range(n):
            if scores[j] < scores[i]:
                rank[i] -= 1
    return rank

print(f'score : {scores}')    
print(f'rank  : {ranking_algorithm(scores)}')

성적 등수 매기기 알고리즘 구현

import random

# 학생 수
studentsNums = 10

# 학생들의 중간고사 성적을 저장할 리스트
midScores = []

# 학생들의 성적을 랜덤하게 생성
for i in range(studentsNums):
    midScores.append(random.randint(0, 100))
    
# 중간고사 순위를 저장할 리스트
midRanks = [studentsNums] * studentsNums

# 순위를 매김
for i in range(studentsNums):
    for j in range(studentsNums):
        if midScores[j] < midScores[i]:
            midRanks[i] -= 1

# 결과 출력
print("중간고사 성적: ", midScores)
print("중간고사 순위: ", midRanks)