Ch4 알고리즘 문제풀이 31-38 (알고문풀1-2)

1. 선형 검색 알고리즘

• 선형 검색 모듈

def searchNumberByLineAlgorithm(ns, sn):

    searchResultIdx = -1

    print(f'Numbers: {ns}')
    print(f'Search Number: {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

• 실행파일

import lineMod
import random

if __name__ == '__main__':

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

    resultIdx = lineMod.searchNumberByLineAlgorithm(rNums, searchNum)

    if resultIdx == -1:
        print('No result found')
        print(f'search result index: {resultIdx}')
    else:
        print('>>> Search Result <<<')
        print(f'search result index: {resultIdx}')
        print(f'search result number: {rNums[resultIdx]}')

• 실행결과

input search number: 7
Numbers: [15, 16, 8, 20, 9, 14, 1, 12, 2, 4]
Search Number: 7
Search FAIL!!
No result found
search result index: -1

input search number: 8
Numbers: [3, 10, 5, 18, 14, 6, 20, 12, 8, 19]
Search Number: 8
Search SUCCESS!!
Search result INDEX: 8
>>> Search Result <<<
search result index: 8
search result number: 8

2. 이진 검색 알고리즘
   -> 정렬되어 있는 데이터에서 찾는것

def searchNumberByBinaryAlgorithm(ns, sn):

    searchResultIdx = -1

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

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

    while sn >= ns[0] and sn <= ns[len(ns)-1]:

        if sn == ns[len(ns)-1]:
            searchResultIdx = len(ns) - 1
            break

        if staIdx + 1 == endIdx:        # 찾는값이 없을경우 무한루프에 빠지는것을 방지 
            if ns[staIdx] != sn and ns[endIdx] != sn:
                break

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

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

        elif sn == midVal:
            searchResultIdx = midIdx
            break

    return searchResultIdx

• 실행파일

import binaryMod as bm

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 = bm.searchNumberByBinaryAlgorithm(nums, searchNum)
    print(f'nums: {nums}')

    if resultIdx == -1:
        print(f'No result found')
        print(f'search result index: {resultIdx}')

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

3. 순위 알고리즘

• 난수 20개 리스트에서 순위를 구하고, 순위에 따라 정렬하는 모듈 만들기

def rankAlgorithm(ns):

    ranks = [0 for i in range(len(ns))]

    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'num: {n} \t rank: {ranks[i]+1}')

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

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

    return sortedNums

import random
import rankMod

if __name__ == '__main__':

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

• 숫자와 알파벳(아스키코드값) 순위 매기기

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():
        ascIIDatas.append(ord(data))
        continue

    ascIIDatas.append(data)

print(f'ascIIDatas: {ascIIDatas}')

ranks = [0 for i in range(len(ascIIDatas))]
print(f'ranks: {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}')     # ':>2' -> 오른쪽정렬 (기본값 왼쪽정렬)

4. 버블 정렬 알고리즘 (인접한 두 숫자끼리 비교하여 정렬)

• 버블정렬로 오름차순, 내림차순 정렬하기
• 모듈 만들어 사용

import copy

def sortByBubbleAlgorithm(ns, asc=True):

    c_ns = copy.copy(ns)       # 깊은복사로 원본 데이터 유지

    length = len(c_ns) - 1

    for i in range(length):
        for j in range(length - i):

            if asc:
                if c_ns[j] > c_ns[j + 1]:
                    c_ns[j], c_ns[j + 1] = c_ns[j + 1], c_ns[j]

            else:
                if c_ns[j] < c_ns[j + 1]:
                    c_ns[j], c_ns[j + 1] = c_ns[j + 1], c_ns[j]
            print(f'c_ns: {c_ns}')
        print()
    return c_ns

• 실행파일

import random
import bubbleMod

if __name__ == '__main__':

    nums = random.sample(range(1, 21), 10)
    print(f'not sorted nums: {nums}')

    result = bubbleMod.sortByBubbleAlgorithm(nums)
    print(f'sorted nums by ASC: {result}')
    result = bubbleMod.sortByBubbleAlgorithm(nums, asc=False)
    print(f'sorted nums by DESC: {result}')

5. 삽입 정렬 알고리즘 (정렬된 앞 데이터들 사이에 뒷 숫자를 삽입하여 정렬)

• 삽입정렬로 오름차순, 내림차순 정렬하기
• 모듈 만들어 사용

import copy

def sortInsertAlgorithm(ns, asc=True):

    c_ns = copy.copy(ns)

    for i1 in range(1, len(c_ns)):
        i2 = i1 - 1
        cNum = c_ns[i1]

        if asc:
            while c_ns[i2] > cNum and i2 >= 0:
                c_ns[i2+1] = c_ns[i2]
                i2 -= 1

        else:
            while c_ns[i2] < cNum and i2 >= 0:
                c_ns[i2+1] = c_ns[i2]
                i2 -= 1

        c_ns[i2+1] = cNum
        print(f'c_ns: {c_ns}')

    return c_ns

• 실행파일

import random
import insertMod

if __name__ == '__main__':
    nums = random.sample(range(1, 21), 10)

    print(f'not sorted nums:\n {nums}')
    result = insertMod.sortInsertAlgorithm(nums)
    print(f'sorted nums by ASC:\n {result}')

    print(f'not sorted nums:\n {nums}')
    result = insertMod.sortInsertAlgorithm(nums, asc=False)
    print(f'sorted nums by DESC:\n {result}')

6. 선택 정렬 알고리즘

• 키값+=1 하면서 키값과 뒤 숫자들 중 최솟값을 비교하여 최솟값이 더 작다면 최솟값을 키값과 자리바꿔감 (내림차순은 최댓값과 비교)
• 선택정렬로 오름차순, 내림차순 정렬하기
• 모듈 만들어 사용

import copy

def sortSelectAlgorithm(ns, asc=True):
    c_ns = copy.copy(ns)


    for i in range(len(c_ns) - 1):
        minIdx = i

        for j in range(i+1, len(c_ns)):

            if asc:
                if c_ns[minIdx] > c_ns[j]:
                    minIdx = j
            else:
                if c_ns[minIdx] < c_ns[j]:
                    minIdx = j

        c_ns[i], c_ns[minIdx] = c_ns[minIdx], c_ns[i]
        print(f'nums: {c_ns}')

    return c_ns

• 실행파일

import random
import selectMod

if __name__ == '__main__':

    nums = random.sample(range(1, 21), 10)

    print(f'not sorted nums: \t {nums}')
    result = selectMod.sortSelectAlgorithm(nums)
    print(f'sorted nums by ASC: {result}')

    print(f'not sorted nums: \t {nums}')
    result = selectMod.sortSelectAlgorithm(nums, asc=False)
    print(f'sorted nums by DESC: {result}')

7. 병합 정렬 알고리즘

• 중간값을 구해서 반씩 나눠가고, 비교해가며 병합하며 정렬 -> 재귀함수 이용
• 병합정렬로 오름차순, 내림차순 정렬하기
• 모듈 만들어 사용

def mSort(ns, asc=True):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc=asc)
    rightNums = mSort(ns[midIdx:len(ns)], asc=asc)

    mergeNums = []
    leftIdx = 0; rightIdx = 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergeNums += leftNums[leftIdx:]
    mergeNums += rightNums[rightIdx:]

    print(f'mergeNums: {mergeNums}')
    return mergeNums

• 실행파일

import random
import mergeAlgorithm

nums = random.sample(range(1, 101), 20)
print(f'not sorted nums: {nums}')

print(f'{mergeAlgorithm.mSort(nums)}')
print(f'{mergeAlgorithm.mSort(nums, asc=False)}')

<제로베이스 데이터 취업 스쿨>