[데이터스쿨] 알고리즘 학습노트

학습범위: 알고리즘

선형 검색, 이진 검색, 순위, 버블 정렬, 삽입 정렬, 선택 정렬, 최댓값, 최솟값, 최빈값, 근삿값, 평균, 재귀, 하노이의 탑, 병합 정렬, 퀵 정렬

선형검색

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

보초법

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

[ 실습 ]

1. 리스트에서 가장 앞에 있는 숫자 '7'을 검색하고 위치(인덱스)를 출력하자.

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
#print(f'nums: {nums}')
#print(f'length: {len(nums)}')

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

# 보초법 사용
nums.append(searchData)

n = 0

while True:
    if nums[n] == searchData:
        if n != len(nums) - 1:
        #보초법으로 맨 마지막에 추가한 데이터(searchData)가 아니어야 함
        #인덱스 순번n은 0부터 시작하므로 전체 길이에서도 -1을 해줘야 같은 위치임
            searchResultIdx = n
        break

    n += 1

print(f'nums: {nums}')
print(f'length: {len(nums)}')

if searchResultIdx == -77:
    print('not search index')
else:
    print(f'search index: {searchResultIdx}')

search number: 7
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
length: 12
search index: 1

search number: 11
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 11]
length: 12
not search index

2. 리스트에서 숫자'7'을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자.

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

searchData = int(input('search number: '))
searchResultIdx = []

# 보초법 사용
nums.append(searchData)

n = 0

while True:
    if nums[n] == searchData:
        if n != len(nums) - 1:
            searchResultIdx.append(n)
        else:
            break

    n += 1

print(f'nums: {nums}')
print(f'searchResultIdx: {searchResultIdx}')
print(f'cnt: {len(searchResultIdx)}')

search number: 7
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
searchResultIdx: [1, 5, 8]
cnt: 3

search number: 11
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 11]
searchResultIdx: []
cnt: 0

---

이진 검색

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

[ 실습 ]

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: '))
searchIdx = -77

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]:
        searchData = 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:
        searchIdx = midIdx
        break

print(f'searchIdx: {searchIdx}')

nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
search number: 7
searchIdx: 3

nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
search number: 100
searchIdx: -77

---

순위

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

[ 실습 ]

1. 학급 학생 7명의 시험 성적을 이용해서 순위를 구하는 프로그램을 만들어 보자. (단, 시험 성적은 난수를 사용한다.)

import random

scores = random.sample(range(80, 101), 7)
ranks = [0 for i in range(7)]

for idx, sco1 in enumerate(scores):
    for sco2 in scores:
        if sco1 < sco2:
            ranks[idx] += 1

print(scores)
print(ranks)

for i, s in enumerate(scores):
    print(f'score:{s} \t rank:{ranks[i] + 1}')

[97, 85, 93, 95, 86, 98, 94]
[1, 6, 4, 2, 5, 0, 3]
score:97 	 rank:2
score:85 	 rank:7
score:93 	 rank:5
score:95 	 rank:3
score:86 	 rank:6
score:98 	 rank:1
score:94 	 rank:4