알고리즘

1. 선형검색

일렬로 되어있는 데이터를 순차적으로 검색

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]

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

2. 이진검색

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

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('search data: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(datas) - 1
mididx = (staIdx + endIdx) // 2
midVal = datas[mididx]

print(f'midIdx: {mididx}')
print(f'midVal: {midVal}')

while searchData <= datas[len(datas)-1] and searchData >= datas[0]:

if searchData == datas[len(datas) - 1]:
    searchResultIdx = len(datas) - 1
    break

if searchData > midVal:
    staIdx = mididx
    mididx = (staIdx + endIdx) // 2
    midVal = datas[mididx]
    print(f'midIdx: {mididx}')
    print(f'midVal: {midVal}')

elif searchData < midVal:
    endIdx = mididx
    mididx = (staIdx + endIdx) // 2
    midVal = datas[mididx]
    print(f'midIdx: {mididx}')
    print(f'midVal: {midVal}')

elif searchData == midVal:
    searchResultIdx = mididx
    break
    

3. 순위

수의 크고 작음을 이용해서 수의 순서를 정하는 것

import random

nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]

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

for idx, num1 in enumerate(nums):
for num2 in nums:
if num1 < num2:
ranks[idx] += 1

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

for idx, num in enumerate(nums):
print(f'nums: {num} \t rank: {ranks[idx] + 1}')

4. 버블정렬

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

nums = [10, 2, 7, 21, 0]

print(f'not sorted nums: {nums} ')

length = len(nums) - 1

for i in range(length):
for j in range(length - i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
print(nums)
print()
print(nums)
print()

print(f'not sorted nums: {nums} ')

• 원본 데이터를 유지하면서 새로운 데이터를 받는다면 깊은 복사
• 원본 데이터로 작업한다면 얇은 복사

5. 삽입정렬

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

#오름 차순
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] # 처음 10과 5의 자리바꿈
    i2 -= 1

nums[i2 + 1] = cNum

print(f'nums: {nums}')

print('-' * 30)

#내림 차순
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}')

6. 선택정렬

주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식
nums = [4, 2, 5, 1, 3]
print(f'before nums: {nums}')

for i in range(len(nums) - 1): # 리스트의 마지막 원소 바로 전까지 반복
minIdx = i # 시작 인덱스를 최소값 인덱스로 초기화

for j in range(i+1, len(nums)):  # i+1에서 시작하여 리스트 끝까지
    if nums[minIdx] > nums[j]:  # 현재 최소값보다 작은 값을 찾으면
        minIdx = j  # 최소값의 위치를 업데이트
        # tempNum = nums[i]
        # nums[i] = nums[minIdx]
        # nums[minIdx] = tempNum

nums[i], nums[minIdx] = nums[minIdx], nums[i]  # 현재 위치와 최소값 위치를 교환
print(f'nums: {nums}')  # 각 단계의 리스트 출력

print(f'final nums: {nums}') # 최종 정렬된 리스트 출력

7. 최빈값

데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 함.

nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]

#처음에는 모든 값이 0인 자료구조를 만든다.
#처음값이 1이라면 인덱스 1번째에 +1을 해준다. 그다음 3이면 인덱스에서 3번째에 +1을 해준다. 이런식으로 진행함.
indexes:[0, 1, 0, 1, 0, 0, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]

8. 근사값

특정 값(참값)에 가장 가까운 값을 근삿값이라 한다.

import random

nums = random.sample(range(0, 50), 20)

print(f'nums: {nums}')

inputNum = int(input('input number: '))
print(f'inputNum: {inputNum}')

nearNum = 0
minNum = 50

for n in nums:
absNum = abs(n - inputNum)

# print(f'absNum: {absNum}')

if absNum < minNum:
    minNum = absNum
    nearNum = n

print(f'near: {nearNum}')

9. 평균

import random

nums = random.sample(range(0, 100), 10)
print(f'nums: {nums}')

total = 0
for n in nums:
total += n

avg = total / len(nums)
print(f'avg: {avg}')

50이상 90이하 수들의 평균
import random
nums = random.sample(range(0, 100), 30)
print(f'nums: {nums}')

total = 0
targetNums = []

for n in nums:
if n <= 50 and n <= 90:
total += n
targetNums.append(n)

avg = total / len(targetNums)
print(targetNums)
print(f'avg: {round(avg)}')

정수들의 평균
nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print(f'nums: {nums}')

targetNums = []
total = 0
for n in nums:
if n - int(n) == 0:
total += n
targetNums.append(n)

avg = total / len(targetNums)
print(f'targetNums: {targetNums}')
print(f'avg: {round(avg)}')

#실수들의 평균
nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print(f'nums: {nums}')

targetNums = []
total = 0
for n in nums:
if n - int(n) != 0:
total += n
targetNums.append(n)

avg = total / len(targetNums)
print(f'targetNums: {targetNums}')
print(f'avg: {round(avg, 2)}')

10. 재귀 알고리즘

나 자신을 다시 호출하는 것을 재귀라고 한다.

def recusion(num):

if num > 0:
    print('*' * num)
    return recusion(num-1)
else:
    return 1

recusion(10)

#10!: 10 9 8 7 6 5 4 3 2 * 1

def factorial(num):
if num > 0:
return num * factorial(num-1)
else:
return 1

factorial(10)
print(f'factorial: {factorial(10)}')

#재귀 알로리즘, 유클리드 호제법: n1, n2에 대하여(n1>n2) n1를 n2로 나눈 나머지를 r이라고 할 때, n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다.

#for문 최대공약수
def greatestCommonDevide(n1 ,n2):

maxNum = 0
for i in range(1, (n1+1)):
    if n1 % i == 0 and n2 % i == 0:
        maxNum = i

return maxNum

print(f'maxNum: {greatestCommonDevide(82, 32)}')
print(f'maxNum: {greatestCommonDevide(96, 40)}')

def gcd(n1, n2):

if n1 % n2 == 0:
    return n2
else:
    return gcd(n2, n1 % n2)

print(f'maxNum: {gcd(82, 32)}')
print(f'maxNum: {gcd(96, 40)}')

11. 하노이의 탑

퍼즐게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기는 게임
단, 한번에 한개의 원판만 옮길 수 있다, 큰 원판이 작은 우너판 위에 있어서는 안된다.

         원판개수, 출발기둥, 도착기둥, 경유기둥

def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')
else:

    # (discCnt-1) 개들을 경유 기둥으로 이동
    moveDisc(discCnt - 1, fromBar, viaBar, toBar)

    # discCnt를 목적 기둥으로 이동
    print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')

    # (discCnt-1)개들을 도착 기둥으로 이동
    moveDisc(discCnt - 1, viaBar,toBar, fromBar)

moveDisc(3, 1, 3, 2)

aux_point = {'A', 'B', 'C'}.difference({'A', 'B'}).pop()

print(aux_point)

def hanoi_sol(n, start_point, end_point):

# 보조 기둥 계산 (세 지점 중에서 시작점과 종료점을 제외한 지점)
aux_point = {'A', 'B', 'C'}.difference({start_point, end_point}).pop()

# 원반 n이 1이면, 바로 시작점에서 종료점으로 옮긴다
if n == 1:
    print(f"{start_point} -> {end_point}")
else:
    # n-1개의 원반을 보조 기둥으로 이동
    hanoi_sol(n - 1, start_point, aux_point)
    # 가장 큰 원반을 목적지로 이동
    print(f"{start_point} -> {end_point}")
    # n-1개의 원반을 목적지로 이동
    hanoi_sol(n - 1, aux_point, end_point)
    
    

12. 병합 정렬

def mSort(ns):

if len(ns) < 2:
    return ns

# 중간값
midIdx = len(ns) // 2

# 중간값 기준 왼쪽 분할
leftNums = mSort(ns[0:midIdx])

# 중간값 기준 오른쪽 분할
rightNums = mSort(ns[midIdx:len(ns)])

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

    # 자리바꿈 부분
    # leftNums vs rightNums
    if leftNums[leftIdx] < rightNums[rightIdx]:
        mergeNums.append(leftNums[leftIdx])
        leftIdx += 1

    # rightNums vs leftNums
    else:
        mergeNums.append(rightNums[rightIdx])
        rightIdx += 1

# 병합되고 남은 값 넣기
mergeNums = mergeNums + leftNums[leftIdx:]
mergeNums = mergeNums + rightNums[rightIdx:]

return mergeNums

nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mSort: {mSort(nums)}')

-> 추가 설명:
각 단계를 예제 데이터를 사용하여 자세히 설명해 보겠습니다. 이 예시에서 leftNums = [1, 4, 6]이고 rightNums = [2, 3, 5]라고 가정하겠습니다.

초기 상태:
leftNums: [1, 4, 6]
rightNums: [2, 3, 5]
mergeNums: []
1단계 (첫 번째 반복):
leftIdx = 0, rightIdx = 0
leftNums[leftIdx] = 1 vs. rightNums[rightIdx] = 2
조건 if leftNums[leftIdx] < rightNums[rightIdx]은 참이므로:
mergeNums에 1을 추가합니다.
leftIdx를 1 증가시킵니다.
결과: mergeNums = [1]
2단계 (두 번째 반복):
leftIdx = 1, rightIdx = 0
leftNums[leftIdx] = 4 vs. rightNums[rightIdx] = 2
이번에는 leftNums[leftIdx] > rightNums[rightIdx]이므로:
mergeNums에 2를 추가합니다.
rightIdx를 1 증가시킵니다.
결과: mergeNums = [1, 2]
3단계 (세 번째 반복):
leftIdx = 1, rightIdx = 1
leftNums[leftIdx] = 4 vs. rightNums[rightIdx] = 3
다시 leftNums[leftIdx] > rightNums[rightIdx]이므로:
mergeNums에 3을 추가합니다.
rightIdx를 1 증가시킵니다.
결과: mergeNums = [1, 2, 3]
4단계 (네 번째 반복):
leftIdx = 1, rightIdx = 2
leftNums[leftIdx] = 4 vs. rightNums[rightIdx] = 5
여전히 leftNums[leftIdx] < rightNums[rightIdx]이므로:
mergeNums에 4를 추가합니다.
leftIdx를 1 증가시킵니다.
결과: mergeNums = [1, 2, 3, 4]
5단계 (다섯 번째 반복):
leftIdx = 2, rightIdx = 2
leftNums[leftIdx] = 6 vs. rightNums[rightIdx] = 5
다시 leftNums[leftIdx] > rightNums[rightIdx]이므로:
mergeNums에 5를 추가합니다.
rightIdx를 1 증가시킵니다.
결과: mergeNums = [1, 2, 3, 4, 5]
추가 단계 (while 루프 종료 후):
leftIdx = 2, rightIdx = 3
rightNums의 모든 요소가 병합되었으므로, leftNums의 나머지 요소 6을 mergeNums에 추가합니다.
최종 결과: mergeNums = [1, 2, 3, 4, 5, 6]

13. 퀵 정렬

기준보다 작은 값과 큰 값을 분리한후, 다시 합친다.

def qSort(ns):

if len(ns) < 2:
    return ns

midIdx = len(ns) // 2
midVal = ns[midIdx]

smallNums = []; sameNums = []; bigNums = [];

for n in ns:
    if n < midVal:
        smallNums.append(n)
    elif n == midVal:
        sameNums.append(n)
    else:
        bigNums.append(n)

return qSort(smallNums) + sameNums + qSort(bigNums)

nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(f'qSort(nums): {qSort(nums)}')