Day47. 알고리즘 문풀 (1)

[연습문제] 검색 알고리즘(01)

• [연습문제]검색 알고리즘(1)

• 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자!
  
  

1. 검색 모듈은 선형 검색 알고리즘을 이용하자!
2. 리스트는 1부터 20까지의 정수 중에서 난수 10개를 이용하자!
3. 검색 과정을 로그로 출력하자!
4. 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없다면 -1을 출력하자!

<실행파일코드>

import module_linearsearch as ml
import random

if __name__ == '__main__':

    rNums = random.sample(range(1, 21), 10)
    searchNum = int(input('input search number : '))

    resultIdx = ml.searchNumberByLineAlgorithm(rNums, searchNum)
    if resultIdx == -1:
        print('No results found')
        print(f'search result index : {resultIdx}')

    else:
        print('>>> Search Results <<<')
        print(f'search result index : {resultIdx}')
        print(f'search result number : {rNums[resultIdx]}')

<모듈파일코드>

def searchNumberByLineAlgorithm(ns, sn):

    searchResultIdx = -1

    print(f'Numbers : {ns}')
    print(f'search Numbers : {sn}')

    n = 0
    while True:

        if n == len(ns):    # 검색해서 끝까지 간 경우
            print('Search FAIL!!')
            break

        if ns[n] == sn:
            searchResultIdx = n
            print('Search SUCCESS!!')
            print(f'Search result INDEX : {searchResultIdx}')
            break

        n += 1

    return searchResultIdx

[연습문제] 검색 알고리즘(02)

• [연습문제] 검색 알고리즘(2)

• 이진 검색
  
  
  숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자!

<실행파일코드>

import module_binarySearch as bs

if __name__ == '__main__':

    nums = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
    searchNum = int(input('input search number : '))

    resultIdx = bs.searchNumberBinaryAlgorithm(nums, searchNum)
    print(f'nums : {nums}')

    if resultIdx == -1: # 못 찾은 경우
        print(f'No results found.')
        print(f'Search result index : {resultIdx}')

    else:
        print('>>> Search Result <<<')
        print(f'search result index : {resultIdx}')
        print(f'search result number : {nums[resultIdx]}')

<모듈파일코드>

def searchNumberBinaryAlgorithm(ns, sn):

    searchResultIdx = -1    # 찾으려는 숫자의 인덱스 초기값 -1로 설정!

    startIdx = 0
    endIdx = len(ns) - 1
    midIdx = (startIdx + endIdx) // 2
    midVal = ns[midIdx]

    print(f'startIdx : {startIdx}, endIdx : {endIdx}')
    print(f'midIdx : {midIdx}, midVal : {midVal}')

    while sn >= ns[0] and ns[len(ns) - 1]:  # ns범위 안에 !

        if sn == ns[len(ns) - 1]:   # 맨 마지막이 같아서 바로 찾은 경우!
            searchResultIdx = len(ns) - 1
            break

        if startIdx + 1 == endIdx:  # 무한루프를 방지하기 위한 코드! ★★★★★
            if ns[startIdx] != sn and ns[endIdx] != sn: # 무한반복하지말고 그만하라는 조건!
                break


        if sn > midVal:
            startIdx = midIdx
            midIdx = (startIdx + endIdx) // 2
            midVal = ns[midIdx]
            print(f'+startIdx : {startIdx}, endIdx : {endIdx}')
            print(f'+midIdx : {midIdx}, midVal : {midVal}')

        elif sn < midVal:
            endIdx = midIdx
            midIdx = (startIdx + endIdx) // 2
            midVal = ns[midIdx]
            print(f'-startIdx : {startIdx}, endIdx : {endIdx}')
            print(f'-midIdx : {midIdx}, midVal : {midVal}')

        elif sn == midVal:
            searchResultIdx = midIdx
            break

    return searchResultIdx

[연습문제] 순위 알고리즘(01)

• [연습문제] 순위 알고리즘(1)

• 숫자로 이루어진 리스트에서 아이템의 순위를 출력하고, 순위에 따라 아이템을 정렬하는 모듈을 만들어보자!
  리스트는 50부터 100까지의 난수 20개를 이용하자!

<실행파일코드>

import random as rd
import module_rankAlgorithm as mr

if __name__ == '__main__':

    nums = rd.sample(range(50, 101), 20)
    sNums = mr.rankAlgorithm(nums)
    print(f'sNums : {sNums}')

<모듈파일코드>

def rankAlgorithm(ns):

    ranks = [0 for i in range(len(ns))] # ns의 길이만큼의 0을 갖는 리스트 생성!

    for idx, n1 in enumerate(ns):
        for n2 in ns:
            if n1 < n2:
                ranks[idx] += 1

    print(f'nums : {ns}')
    print(f'ranks : {ranks}')

    # 구한 순위에 따라 재정렬하는 코드

    for i, n in enumerate(ns):
        print(f'nums : {n} \t rank : {ranks[i + 1]}')   # i + 1 인 이유는 안하면 0부터 나오기 때문!

    sortedNums = [0 for n in range (len(ns))]

    for idx, rank in enumerate(ranks):
        sortedNums[rank] = ns[idx]

    return sortedNums

랭크가 제대로 나오지 않음 다시 해봐야함!

[연습문제] 순위 알고리즘(02)

• [연습문제] 순위 알고리즘(2)

• 알파벳 문자들과 정수들에 대한 순위를 정하는 프로그램을 순위 알고리즘을 이용해서 만들어 보자!
  단, 알파벳은 아스키코드 값을 이용한다!
  
  
  [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']

datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
print(f'datas : {datas}')

asciiDatas = []

for data in datas:
    if str(data).isalpha():  # isalpha는 영어인지 아닌지 확인 해준다!    data를 str로 안바꿔주면 오류가 발생!
        asciiDatas.append(ord(data))
        continue

    asciiDatas.append(data) # 숫자가 아닌경우는 그냥 넣어준다!

print(f'asciiDatas : {asciiDatas}')

ranks = [0 for i in range(len(asciiDatas))]
print(f'ranks before : {ranks}')

for idx, data1 in enumerate(asciiDatas):
    for data2 in asciiDatas:
        if data1 < data2:
            ranks[idx] += 1

print(f'ranks after : {ranks}')

for i, d in enumerate(datas):
    print(f'data : {d:>2} \t rank : {ranks[i] + 1}')    # d:>2 두자리 표현하는데 오른쪽 정렬하겠다!