Python 알고리즘 1

선형검색

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.

코드

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

n = 0
while True:
    
    if n == len(datas):
        searchResultIdx = -1
        break
    elif datas[n] == searchData:
        searchResultIdx = n
        break
        
    n += 1
    print(f'searchResultIdx :[{searchResultIdx}]')

---

보초법

• 마직막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.

코드

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

datas.append(searchData)

n = 0
while True:

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

---

이진검색

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.

코드

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

staInx = 0
endIdx = len(datas) - 1
midIdx = (staInx + endIdx) // 2
midVal = datas[midIdx]

if searchData > midVal:
    staInx = midIdx
    midIdx = (staInx + endIdx) // 2
    midVal = datas[midIdx]
    print(f'midIdx : {midIdx}')
    print(f'midVal : {midVal}')
    
elif searchData < midVal:
    endIdx = midIdx
    midIdx = (staInx + endIdx) // 2
    midVal = datas[midIdx]
    print(f'midIdx : {midIdx}')
    print(f'midVal : {midVal}')
    
elif searchData == midVal:
    searchResultIdx = midIdx

---

순위

• 수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다.

코드

import random

nums = random.sample(range(50,101),20)
ranks = [0 for i in range(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 ranks:  {ranks[idx]+1}')

---

버블정렬

• 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를
  가장 끝으로 옮기는 알고리즘이다.

코드

import copy

def bubbleSort(ns, deepCopy = True):
    
    if deepCopy:
        cns = copy.copy(ns)
    else:
        cns = ns
        
    length = len(cns) - 1
    for i in range(length):
        for j in range(length - i):
            if cns[j] > cns[j+1]:
                cns[j], cns[j+1] = cns[j+1], cns[j]
                
    return cns

삽입정렬

• 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.

코드

# ascending
nums = [5, 10, 2, 1, 0]

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

    while nums[i2] > cNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1

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

# descending
nums = [0, 5, 2, 10, 1]

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

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

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

---

선택정렬

• 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는방식으로 자료를 정렬하는 알고리즘이다.

코드

nums = [4, 2, 5, 1, 3]

for i in range(len(nums)-1):
    minIdx = i
    
    for j in range(i+1, len(nums)):
        if nums[minIdx] > nums[j]:
            minIdx = j
            
    tempNum = nums[i]
    nums[i] = nums[minIdx]
    nums[minIdx] = tempNum

---