19_알고리즘(2)

ryu·2023년 5월 25일
0

선택정렬

선택정렬이란?

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

    nums = [4, 2, 5, 1, 3]
    
    for i in range(len(nums)-1):
      	minIdx = 1
        
        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

최댓값

  • 자료구조에서 가장 큰 값을 찾음
  • 순차적으로 조회하면서 최대값을 갱신하는 방법
  • max()

최소값

  • 최대값과 같은 방식
  • min()

최빈값

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

근삿값

  • 특정 값(참값)에 가장 가까운 값을 근삿값이라고 함

평균

  • 여러 수의 양의 중간값을 갖는 수

재귀

  • 자기 자신을 다시 호출하는 것

하노이의 탑

  • 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되는 게임
  • 한 번에 한 개의 원 판만 옮길 수 있으며, 큰 원 판이 작은 원판 위에 있어서는 안된다는 제약조건이 있음

병합정렬

병합정렬이란?

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

    def msSort(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):
          
          	if leftNums[leftIdx] < rightNums[rightIdx]:
              	mergeNums.append(leftNums[leftIdx])
                leftIdx += 1
                
            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1
                
        mergeNums = mergeNums + leftNums[leftIdx:]
        mergeNums = mergeNums + rightNums[rightIdx:]
        
        return mergeNums

퀵 정렬

퀵정렬이란?

  • 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합침

구현

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)

0개의 댓글