알고리즘 02. 근삿값, 평균, 재귀, 하노이의탑, 병합정렬, 퀵정렬

근삿값이란?

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

    def nearestSearch(self, nums):
        print('근삿값 검색 시작!')
        searchValue = int(input('근삿값을 찾고 싶은 값 입력: '))
        tempArr = []
        ansArr = []
        for i in range(len(nums)):
            tempArr.append(abs(searchValue - nums[i]))
        tempMinValue = tempArr[0]
        tempIdx = -1
        for i in range(len(tempArr)):
            if tempMinValue > tempArr[i]:
                tempMinValue = tempArr[i]
                tempIdx = i
        ansArr.append([tempIdx, nums[tempIdx]])

        return ansArr

 

 

평균이란?

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

    def averageSearch(self, nums):
        total = 0
        for n in nums:
            total += n
        average = total / len(nums)

        return round(average, 2)

 

 

재귀 알고리즘이란?

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

  # 재귀함수의 사례 1: 팩토리얼
  def factorial(self, num):
        if num > 1:
            return num * self.factorial(num - 1)
        else:
            return 1


  # 재귀함수의 사례 2: 피보나치 수열
    def fibonacci(self, num):
        if num>0:
            if num == 1:
                return 1
            elif num == 2:
                return 1
            else:
                return self.fibonacci(num - 1) + self.fibonacci(num - 2)
                
  # 재귀함수의 사례 3: 역으로 별 찍기
    def reverseStar(self, num):
        if num > 0:
            if num == 1:
                print("*")
            else:
                print("*" * num)
                self.reverseStar(num - 1)
                
                
  # 재귀함수의 사례 4: 유클리디안 알고리즘으로 최대공약수 찾기
      def uclideanAlgorithm(self, num1, num2):
        if num1 % num2 == 0:
            return num2
        else:
            return self.uclideanAlgorithm(num2, num1 % num2)

 

 

하노이의 탑이란?

퍼즐게임의 일종으로, 세 개의 기둥 가운데 한 기둥에만 채워진 원판을 다른 빈 기둥으로 옮기는 최소의 횟수이다.

제약 조건은 다음과 같다.

한 번에 한 개의 원판만 옮길 수 있다.
큰 원판이 작은 원판 위에 있어서는 안 된다.

 

    def towerOfHanoi(self, discCnt, fromBar, toBar, viaBar):
        if discCnt == 1:
            print(f'{discCnt}disc: {fromBar}에서 {toBar}로 이동')
        else:
            # (discCnt - 1)개들을 viaBar로 이동
            self.towerOfHanoi(discCnt-1, fromBar, toBar, viaBar)
            # (discCnt)를 toBar로 이동
            print(f'{discCnt}disc: {fromBar}에서 {toBar}로 이동')
            # (discCnt - 1)개들을 toBar로 이동
            self.towerOfHanoi(discCnt-1, viaBar, fromBar, toBar)

 

 

병합정렬이란?

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

자료구조를 먼저 분할한 후

정렬하면서 병합한다.

    def mergeSortAsc(self, nums):
        if len(nums) < 2:
            return nums
        midIdx = len(nums) // 2
        leftNums = self.mergeSortAsc(nums[:midIdx])
        rightNums = self.mergeSortAsc(nums[midIdx:len(nums)])

        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 mergeSortDsc(self, nums):
        if len(nums) < 2:
            return nums
        midIdx = len(nums) // 2
        leftNums = self.mergeSortDsc(nums[:midIdx])
        rightNums = self.mergeSortDsc(nums[midIdx:len(nums)])

        mergeNums = []
        leftIdx = 0
        rightIdx = 0
        while leftIdx < len(leftNums) and rightIdx < len(rightNums):
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1
            else:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

        mergeNums = mergeNums + leftNums[leftIdx:]
        mergeNums = mergeNums + rightNums[rightIdx:]

        return mergeNums

 

 

퀵 정렬이란?

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

    def quickSortAsc(self, nums):
        if len(nums) < 2:
            return nums
        midIdx = len(nums) // 2
        midVal = nums[midIdx]
        smallNums = []
        sameNums = []
        bigNums = []

        for num in nums:
            if num < midVal:
                smallNums.append(num)
            elif num == midVal:
                sameNums.append(num)
            elif num > midVal:
                bigNums.append(num)

        return self.quickSortAsc(smallNums) + sameNums + self.quickSortAsc(bigNums)

    def quickSortDsc(self, nums):
        if len(nums) < 2:
            return nums
        midIdx = len(nums) // 2
        midVal = nums[midIdx]
        smallNums = []
        sameNums = []
        bigNums = []

        for num in nums:
            if num < midVal:
                smallNums.append(num)
            elif num == midVal:
                sameNums.append(num)
            elif num > midVal:
                bigNums.append(num)

        return self.quickSortDsc(bigNums) + sameNums + self.quickSortDsc(smallNums)