Day40. 알고리즘 (1)

선형 검색 - 이론

• 선형검색 이란?

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다!
  
  
  [0][1] [2][3] [4][5] [6][7] [8][9]
  3 2 5 7 9 1 0 8 6 4
  
  
  -----------인덱스 0부터 9까지 순차적으로 검색한다.----->

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    # 존재하지 않는 인덱스 -1을 일단 초기값으로 준다!

n = 0
while True:

    if n == len(datas): # n이 끝까지 갔다 = 찾는 수가 없다!
        searchResultIdx = -1    # -1 = 없다
        break

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

    n += 1

print(f'searchResultIdx : {searchResultIdx}')

• 보초법
  
  
  마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다!
  
  
  [0][1] [2][3] [4][5] [6][7] [8][9] [10]
  3 2 5 7 9 1 0 8 6 4 9
  -----------인덱스 0부터 10까지 순차적으로 검색한다.----->
  
  
  검색 성공 : 마지막 이전에 '9'가 검색된 경우
  검색 실패 : 마지막에 '9'가 검색된 경우

보초법을 사용한 코드

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    # 존재하지 않는 인덱스 -1을 일단 초기값으로 준다!

datas.append(searchData)    # 보초법으로 찾으려는 데이터를 맨뒤에 넣는다!

n = 0
while True:

##### 보초법에서는 해당 코드가 필요없다 #####

    # if n == len(datas): # n이 끝까지 갔다 = 찾는 수가 없다!
    #     searchResultIdx = -1    # -1 = 없다
    #     break
########################################

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

    n += 1

print(f'datas : {datas}')
print(f'datas length : {len(datas)}')
print(f'searchResultIdx : {searchResultIdx}')

선형 검색 - 실습

• 실습1
  리스트에서 가장 앞에 있는 숫자 '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('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]

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

def searchNum(tempNums):    # 함수로 만들기!
    tempNums = int(input('input search number : '))
    searchResultIdx = []

    nums.append(tempNums)

    n = 0

    while True:

        if nums[n] == tempNums:
            if n != len(nums) -1:
                searchResultIdx.append(n)
            else:
                break
        n += 1

    return searchResultIdx

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

searchNum(nums)

이진 검색 - 이론

• 이진검색 이란?

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다!
  
  
  [0][1] [2][3] [4][5] [6][7] [8]
  1 2 3 4 5 6 7 8 9
  
  
  검색대상 : 2
  
  
  중앙값인 5로 똭 나눠서 2는 5보다 작으므로 2 < 5
  [0][1] [2][3] [4]
  1 2 3 4 5
  
  
  다시 또 중앙값 3으로 내가 찾으려는 데이터와 비교해본다
  2<3!
  
  
  그 다음 중앙값을 찾아보니 내가찾는 2!
  
  
  검색 데이터의 범위를 좁혀 나가면서 검색하는 것이 이진검색!

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

startIdx = 0
endIdx = len(datas) - 1
middleIdx = (startIdx + endIdx) // 2    # 중앙 인덱스
middleValue = datas[middleIdx]  # 중앙 값!

if searchData > middleValue:    # 찾으려는 데이터가 중앙값보다 크다면 중앙값보다 작은 수들은 의미가 없다!
    startIdx = middleIdx    # 중앙값을 시작값으로 해서 검색 다시 시작!
    middleIdx = (startIdx + endIdx) // 2
    middleValue = datas[middleIdx]
    print(f'middleIdx : {middleIdx}')
    print(f'middleValue : {len(middleValue)}')

elif searchData < middleValue:
    endIdx = middleIdx  # 중앙값을 시작값으로 해서 검색 다시 시작!
    middleIdx = (startIdx + endIdx) // 2
    middleValue = datas[middleIdx]
    print(f'middleIdx : {middleIdx}')
    print(f'middleValue : {len(middleValue)}')

elif searchData == middleValue:
    searchResultIdx = middleIdx
    break

print(f'searchResultIdx : {searchResultIdx}')

while 사용!

##### while 사용! #####

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

searchData = int(input('찾으려는 숫자 입력 : '))
searchResultIdx = -1

startIdx = 0
endIdx = len(datas) - 1
middleIdx = (startIdx + endIdx) // 2    # 중앙 인덱스
middleValue = datas[middleIdx]  # 중앙 값!

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

while searchData <= datas[len(datas) -1] and searchData >= datas[0]:    # 사용자가 찾으려는 숫자가 데이터의 끝보다 작거나 같고, 데이터의 시작보다 크면 반복!

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

    if searchData > middleValue:  # 찾으려는 데이터가 중앙값보다 크다면 중앙값보다 작은 수들은 의미가 없다!
        startIdx = middleIdx  # 중앙값을 시작값으로 해서 검색 다시 시작!
        middleIdx = (startIdx + endIdx) // 2
        middleValue = datas[middleIdx]
        print(f'middleIdx : {middleIdx}')
        print(f'middleValue : {middleValue}')

    elif searchData < middleValue:
        endIdx = middleIdx  # 중앙값을 시작값으로 해서 검색 다시 시작!
        middleIdx = (startIdx + endIdx) // 2
        middleValue = datas[middleIdx]
        print(f'middleIdx : {middleIdx}')
        print(f'middleValue : {middleValue}')

    elif searchData == middleValue:
        searchResultIdx = middleIdx
        break

print(f'searchResultIdx : {searchResultIdx}')

이진 검색 - 실습

• 이진검색(실습)

• 가운데 데이터를 사용한다!

• 리스트를 오름차순으로 정렬한 후 '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() # 정렬하는 api 사용!
print(f'nums sort : {nums}')


searchData = int(input('찾으려는 숫자 입력 : '))
searchResultIdx = -1

strIdx = 0
endIdx = len(nums) - 1
midIdx = (strIdx + endIdx) // 2
midVal = nums[midIdx]


while searchData >= nums[0] and searchData <= nums[len(nums) -1]:  # 데이터 범위 안에 있으면 반복한다는 코드!    and로 할 것!

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

    if searchData > midVal:
        strIdx = midIdx
        midIdx = (strIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midVal이 searchData보다 큰 경우 로그 IDX : {midIdx}')
        print(f'midVal이 searchData보다 큰 경우 로그 VALUE : {midVal}')

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (strIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midVal이 searchData보다 작은 경우 로그 IDX : {midIdx}')
        print(f'midVal이 searchData보다 작은 경우 로그 VALUE : {midVal}')

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchData : {searchData}')
print(f'searchResultIdx : {searchResultIdx}')

# 없는 데이터를 검색할 경우 무한루프에 빠지는데 해결 해야한다!

없는 데이터를 검색할 경우 무한루프에 빠지는데 해결 해야한다!

순위 - 이론

• 순위 란?

• 수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다!
  
  
  [98, 67, 99, 52, 89, 78, 57, 65, 50, 74, 58, 71, 68, 96, 86, 85, 93, 94, 66, 97]
  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
  [1, 13, 0, 18, 6, 9, 17, 15, 19, 10, 16, 11, 12, 3, 7, 8, 5, 4, 14, 2]
  
  
  비교해서 내가 작을 때마다 +1 가장 작으면 비교 대상만큼 +!

import random

nums = random.sample(range(50, 101), 20)   # 50~100 까지 20개 !
ranks = [0 for i in range(20)]  # 값이 0이 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'nums : {num} \t rank : {ranks[idx] + 1}')

# 복습 꼭 필요!

복습 꼭 필요!