알고리즘

알고리즘

1. 선형검색

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

datas  # 랜덤한 숫자가 나열된 데이터
searchNum # 찾고자 하는 숫자
searchResultIdx = -1
n = 0
while True:
    if n == len(datas):
        searchResultIdx = -1
        break

    elif datas[n] == searchNum: 
        searchResultIdx = n
        break
    n += 1

1-2 보초법

보초법 : 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.

datas  # 랜덤한 숫자가 나열된 데이터
searchNum # 찾고자 하는 숫자
searchResultIdx = -1
datas.append(searchNum)
n = 0
while True:

    if datas[n] == searchNum:
        if n != len(datas) -1 :
            searchResultIdx = n
        break

    n += 1

2. 이진검색

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

datas       # 랜덤한 숫자가 나열된 데이터
searchData  # 찾고자하는 데이터
searchResultIdx = -1

staIdx = 0                   # 처음 인덱스
endIdx = len(datas)-1        # 마지막 인덱스
midIdx = (staIdx+endIdx)//2  # 중간 인덱스
midVal = datas[midIdx]       

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]

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx+endIdx)//2
        midVal = datas[midIdx]

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

3. 순위

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

nums                           # 랜덤한 숫자가 나열된 데이터
ranks = [0 for i in range(20)] # 길이가 20이고 모든 값이 0인 리스트

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

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

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

nums  # 랜덤한 숫자가 나열된 데이터 
length = len(nums)-1

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

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

nums # 랜덤한 숫자가 나열된 데이터 

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

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

    nums[i2 +1] = cNums

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

nums # 랜덤한 숫자가 나열된 데이터

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

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

    temp = nums[i]
    nums[i] = nums[minIdx]
    nums[minIdx] = temp

7. 최댓값
   최댓값 : 자료구조에서 가장 큰 값을 찾는다

numbers # 랜덤한 숫자가 나열된 데이터
maxNum = numbers[0]

for n in numbers:
	if maxNum < n:
		maxNum = n

8. 최솟값
   최솟값 : 자료구조에서 가장 작은 값을 찾는다.

numbers # 랜덤한 숫자가 나열된 데이터
minNum = numbers[0]

for n in numbers:
	if minNum > n:
		minNum = n

9. 최빈값
   최빈값 : 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다

nums # 랜덤한 숫자가 나열된 데이터
maxNum = nums[0]
maxNumIdx = 0

for i, n in enumerate(nums):
	if maxNum < n:
	maxNum = n
	maxNumIdx = i

indexes = [0 for i in range(maxNum+1)]

for n in nums:
    indexes[n] = indexes[n]+1

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

nums      # 랜덤한 숫자가 나열된 데이터
inputNum  # 입력숫자
nearNum = 0
minNum = len(nums)

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

    if absNum < minNum:
        minNum = absNum
        nearNum = n

11. 평균
    평균 : 여러 수나 양의 중간값을 갖는 수를 평균이라고 한다

12. 재귀
    재귀 : 나 자신을 다시 호출하는 것

def recusion(num): # 재귀함수

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

12_2 하노이의 탑 구현하기

# (discCnt : 원판갯수, frombar : 출발기둥, toBar : 도착기둥, VaiBar: 경우기둥)
def moveDisc(discCnt, frombar, toBar, viaBar):
    if discCnt == 1:
        print(f'{discCnt}disc를 {frombar}에서 {toBar}으로 이동')

    else:
        moveDisc(discCnt-1 , frombar, viaBar, toBar) # discCnt-1개 원판을 경유기둥으로 옮김
        print(f'{discCnt}disc를 {frombar}에서 {toBar}으로 이동') # 제일큰 원판을 도착기둥으로 옮김
        moveDisc(discCnt - 1, viaBar, toBar, frombar) # discCnt-1개 원판을 도착기둥으로 옮김

13. 병합정렬
    병합정렬 : 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다

nums # 랜덤한 숫자가 나열된 데이터

def mSort(ns):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx])
    rigthNums = mSort(ns[midIdx:len(ns)])

    mergeNums = []
    leftIdx = 0; rigthIdx=0
    while leftIdx < len(leftNums) and rigthIdx < len(rigthNums):

        if leftNums[leftIdx] < rigthNums[rigthIdx]:
            mergeNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergeNums.append(rigthNums[rigthIdx])
            rigthIdx += 1

    mergeNums = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rigthNums[rigthIdx:]

    return mergeNums

14. 퀵정렬
    퀵정렬 : 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다

nums  # 랜덤한 숫자가 나열된 데이터

def qSort(ns, asc = True):

    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)
        elif n > midVal:
            bigNums.append(n)

    if asc:
        return qSort(smallNums) + sameNums + qSort(bigNums)
    else: # 재귀함수 쓸때는 내림차순 리턴 할때도 내림차순 판별 인자 다 넣어주기
        return qSort(bigNums,asc = asc)+ sameNums + qSort(smallNums,asc = asc)