[알고리즘] 문제풀이 (1)

1. 선형 검색

(lineMod.py)
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

(ex.py)
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 results found')
        print(f'search result index: {resultIdx}')

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

2. 이진 검색

(binaryMod.py)
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

(ex.py)
import binaryMod

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

    resulrIdx = binaryMod.searchNumberByBinaryAlgorithm(nums, searchNum)
    print(f'nums: {nums}')

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

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

3. 순위(1)

(rank.py)
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 enumarate(ranks):
        sortedNums[rank] = ns[idx]

    return sortedNums

(ex.py)
import random
import rank

if __name__=='__main__':

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

4. 순위(2)

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

5. 정렬(1) 버블정렬

(bubbleMod.py)
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'ns: {c_ns}')
        print()
    return c_ns

(ex.py)
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}')

6. 정렬(2) 삽입정렬

(insertMod.py)
import copy

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

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

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

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

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

(ex.py)
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}')

7. 정렬(3) 선택 정렬

(selectMod.py)
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

(ex.py)
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}')

8. 정렬(4) 병합정렬

(mergeAlgorithm.py)
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)

    mergedNums = []
    leftIdx = 0
    rightIdx = 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergedNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergedNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergedNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergedNums.append(rightNums[rightIdx])
                rightIdx += 1

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

    return mergedNums

(ex.py)
import random
import mergeAlgorithm

rNums = random.sample(range(1,101),20)
print(f'rNums: {rNums}')
print(f'mergeAlgorithm.mSort(rNums): {mergeAlgorithm.mSort(rNums, asc=True)}')
print(f'mergeAlgorithm.mSort(rNums, asc=False): {mergeAlgorithm.mSort(rNums, asc=False)}')