[Zero-Base DS]스터디노트_알고리즘(03)

주요 학습내용

알고리즘 문제풀이 (01)

1. 검색 알고리즘

2. 순위 알고리즘

3. 정렬 알고리즘

I. 검색 알고리즘

1. 선형 검색 알고리즘

1) 모듈 생성(lineMod)

def searchNumberByLineAlgorithm(ns, sn):

    searchResultIdx = -1
    print(f'Numbers: {ns}')
    print(f'Search Numbers: {sn}')

    n = 0
    while True:
        if n == len(ns):  # 끝까지 검색한 경우
            print(f'Search FAIL')
            break
        if ns[n] == sn:
            searchResultIdx = n
            print(f'Search SUCCESS')
            print(f'Search result INDEX: {searchResultIdx}')
            break
        n += 1

    return searchResultIdx

2) 문제풀이

import lineMod
import random  
# 난수 생성을 위해 random함수 import
nums = random.sample(range(1, 20), 10)

if __name__ == '__main__':
    nums = random.sample(range(1, 20), 10)
    searchNum = int(input('찾으려는 숫자 입력: '))

    resultIdx = lineMod.searchNumberByLineAlgorithm(nums, searchNum)
    if resultIdx == -1:
        print('No result found')
        print(f'search result index: {resultIdx}')
    else:
        print('>>> Search Results <<<')
        print(f'search result index: {resultIdx}')
        print(f'search result number: {searchNum}')

출력 결과 :

2. 이진검색 알고리즘

1) 모듈 생성(binaryMod)

def searchNumByBinaryAlgorithm(ns, sn):

    searchNumIdx = -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]:  # 소소한 최적화, 보통 바이너리 함수 구할 때는 구현 x
            searchNumIdx = len(ns)-1
            break
        if staIdx + 1 == endIdx:
            if ns[staIdx] != sn and ns[endIdx] != sn:
                break
        if 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:
            # 값 재정의
            staIdx = midIdx
            midIdx = (staIdx + endIdx) // 2
            midVal = ns[midIdx]
            print(f'+ staIdx: {staIdx}, endIdx: {endIdx}')
            print(f'+ midIdx: {midIdx}, midVal: {midVal}')
        elif sn == midVal:
            searchNumIdx = midIdx
            break

    return searchNumIdx

2) 문제풀이

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(f'input search number: '))

    resultIdx = bm.searchNumByBinaryAlgorithm(nums, searchNum)
    print(f'nums: {nums}')

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

출력 결과 :

II. 순위 알고리즘

1. 순위 알고리즘

1) 모듈 생성(rankMod2)

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

    # 순서대로 출력
    sortedNums = [0 for n in range(len(ns))]

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

    return sortedNums

2) 문제풀이

import random
import rankMod2 as rm
if __name__ == '__main__':

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

출력 결과 :

2. 순위 알고리즘(아스키코드)

1) 문제풀이

datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
print(f'data: {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 r in range(len(asciiDatas))]
print(f'ranks before: {ranks}')

# 중첩 for문 생성
for idx, num1 in enumerate(asciiDatas):
    for num2 in asciiDatas:
        if num1 < num2:
            ranks[idx] += 1

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

for i, n in enumerate(datas):
    print(f'data: {n:>2} \trank: {ranks[i]+1}')  # :>2(오른쪽 2번째 자리로 정렬)

출력 결과 :

III. 정렬 알고리즘

1. 버블정렬 알고리즘

1) 모듈 생성(bubbleMod)

import copy
# 깊은 복사 사용
def sortByBubbleAlgorithm(ns, asc = True):

    c_ns = copy.copy(ns)  # 원본은 그대로 두고, 새로운 copy생성
    length = len(c_ns) - 1

    for i in range(len(c_ns)-1):
        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
# length-i:
# 처음엔 0부터 length까지 반복
# 그 다음엔 0부터 length-1까지 반복
# 그 다음엔 0부터 length-2까지 반복 (계속 하나씩 덜 반복)

2) 문제풀이

import bubbleMod
import random

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

출력 결과(정렬 전) :

출력 결과(오름차순 정렬 후) :

정렬 과정

출력 결과(내림차순 정렬 후) :

정렬 과정

2. 삽입정렬 알고리즘

1) 모듈 생성(insertMod)

import copy

def sortByInsertAlgorithm(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:  # 오름차순/ascending
            while c_ns[i2] > cNum and i2 >= 0:
                c_ns[i2 + 1] = c_ns[i2]
                i2 -= 1

        else:  # 내림차순/descending
            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

2) 문제풀이

import random
import insertMod

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

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

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

출력 결과 :

3. 선택정렬 알고리즘

1) 모듈생성(selectMod)

import copy
def sortBySelectAlgorithm(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[minIdx], c_ns[i] = c_ns[i], c_ns[minIdx]  # for문 빠져나와서 지정
        print(f'c_ns: {c_ns}')

    return c_ns

2) 문제풀이

import selectMod as sm
import random

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

    result = sm.sortBySelectAlgorithm(nums)
    print(f'sorted nums by ASC: \n{result}')

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

출력 결과 :

4. 병합정렬 알고리즘

1) 모듈 생성(mergeMod)

import copy

def sortByMergeAlgorithm(ns, asc=True):

    c_ns = copy.copy(ns)

    if len(c_ns) < 2:
        return c_ns

    # 분할
    midIdx = len(c_ns) // 2
    leftNums = sortByMergeAlgorithm(c_ns[0:midIdx], asc=asc)
    rightNums = sortByMergeAlgorithm(c_ns[midIdx:len(c_ns)], asc=asc)

    # 병합
    mergeNums = []
    leftIdx = 0; rightIdx = 0

    # 1) 범위 지정
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        # 하나씩 비교하면서 idx값 하나씩 +1
        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'mergeNum: {mergeNums}')
    return mergeNums

2) 문제풀이

import random
import mergeMod

if __name__ == '__main__':

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

    result = mergeMod.sortByMergeAlgorithm(nums)
    print(f'sorted nums by ASC:( {result}')

    result = mergeMod.sortByMergeAlgorithm(nums, asc=False)
    print(f'sorted nums by DESC: {result}')

출력 결과(정렬 전) :

출력 결과(오름차순 정렬 후) :

정렬 과정 :

출력 결과(내림차순 정렬 후) :

정렬 과정 :

[자료 출처: 제로베이스 데이터 스쿨]