[파이썬 기초] 알고리즘 - 검색,순위

🔍  알고리즘이란?

- 문제를 풀기 위한 일련의 절차나 방법

---

 

🗝 선형 검색

- 선형(일렬)으로 나열되어 있는 데이터를 순차적으로 스캔하며 원하는 값을 찾는다.

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

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 = [1,3,6,7,8,4,9,11,5]

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}')

---

 

🗝 이진검색

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

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

searchData = int(input('숫자 입력:'))
searchResultIdx = -1

staIdx = 0
endIdx = len(datas)-1
midIdx = (staIdx + endIdx) // 2

midVal = datas[midIdx]

while searchData <= datas[endIdx] and searchData >= datas[staIdx]:

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

    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]


    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchDataIdx: {searchResultIdx}')

---

 

🗝 순위

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

import random

nums = random.sample(range(50, 101),20)
ranks = [0 for i in range(20)]  # 각 값에 0 할당

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}')

[순위] 중간, 기말 점수 격차 확인