알고리즘 03. 지금까지 배운 알고리즘들 정리

지금까지 공부한 알고리즘들을 재사용하기 위해 모듈화하였다. 언제든 사용할 수 있도록, 추가로 발전시킬 수 있도록 코드와 파일을 남겨 둔다.

basic_algorithms.zip

0.01MB

 

class Algorithm:
    def __init__(self):
        pass

    def linearSearch(self, nums):
        print('선형검색 시작!')
        n = 0
        searchNum = int(input('찾으려는 숫자 입력: '))
        searchNumIdx = -1
        while True:
            if n == len(nums):
                searchNumIdx = -1
                break
            elif nums[n] == searchNum:
                searchNumIdx = n
                break
            n += 1
        return searchNumIdx

    def sentinelMethod(self, nums):
        print('보초법 선형검색 시작!')
        searchIdx = -1
        searchNum = int(input('찾으려는 숫자 입력: '))
        nums.append(searchNum)
        n = 0
        searchNumIdx = -1
        while n < len(nums) - 1:
            if searchNum == nums[n]:
                if n != len(nums):
                    searchIdx = n
            n += 1
        return searchIdx

    def rank(self, nums):
        print('순위 시작!')
        ranks = [0 for i in range(len(nums))]

        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} \t rank: {ranks[idx] + 1}')

    def binarySearch(self, nums):
        print('이진 검색 시작!')
        nums.sort()
        print(f'정렬된 Array: {nums}')

        searchValue = int(input('찾으려는 값 입력: '))
        searchIdx = -1

        staIndex = 0
        endIndex = len(nums) - 1
        midIndex = (staIndex + endIndex) // 2
        midVal = nums[midIndex]
        n = 1
        while staIndex <= endIndex:
            if searchValue > midVal:
                staIndex = midIndex
                midIndex = (staIndex + endIndex) // 2
                midVal = nums[midIndex]
                print(f'{n}회차, midIdx: {midIndex}, midVal: {midVal}')
                n += 1
            elif searchValue < midVal:
                endIndex = midIndex
                midIndex = (staIndex + endIndex) // 2
                midVal = nums[midIndex]
                print(f'{n}회차, midIdx: {midIndex}, midVal: {midVal}')
                n += 1
            elif searchValue == midVal:
                searchIdx = midIndex
                break

        print(f'결과: {searchIdx}')
        return searchIdx

    def bubbleSort(self, nums):
        print('버블정렬 시작!')
        for j in range(len(nums)):
            for i in range(len(nums) - 1):
                if nums[i] > nums[i + 1]:
                    temp = nums[i]
                    nums[i] = nums[i + 1]
                    nums[i + 1] = temp
        return nums

    def insertionSort(self, nums):
        print('삽입 정렬 시작!')
        isAscOrDec = int(input('1: 오름차순, 2: 내림차순'))
        if isAscOrDec == 1:
            for i in range(1, len(nums)):
                j = i - 1
                cNum = nums[i]

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

                nums[j + 1] = cNum

            return nums
        elif isAscOrDec == 2:
            for i in range(1, len(nums)):
                j = i - 1
                cNum = nums[i]

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

                nums[j + 1] = cNum

            return nums

    def selectionSort(self, nums):
        print('선택정렬 시작!')
        isAscOrDec = int(input('1: 오름차순, 2: 내림차순'))
        if isAscOrDec == 1:
            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

            return nums
        elif isAscOrDec == 2:
            for i in range(len(nums) - 1):
                maxIdx = i

                for j in range(i + 1, len(nums)):
                    if nums[maxIdx] < nums[j]:
                        maxIdx = j
                tempNum = nums[i]
                nums[i] = nums[maxIdx]
                nums[maxIdx] = tempNum

            return nums

    def maxSearch(self, nums):
        maxValue = 0
        for i in range(len(nums)):
            if nums[i] > maxValue:
                maxValue = nums[i]
        return maxValue

    def minSearch(self, nums):
        minValue = 0
        for i in range(len(nums)):
            if nums[i] < minValue:
                minValue = nums[i]
        return minValue

    def modeSearch(self, nums):
        print('최빈값 검색 시작!')
        maxVal = 0
        for i in range(len(nums)):
            if maxVal < nums[i]:
                maxVal = nums[i]
        idxArr = [0 for _ in range(maxVal + 1)]
        for num in nums:
            idxArr[num] += 1

        maxIdxVal = 0
        maxIdx = -1
        for i in range(len(idxArr)):
            if maxIdxVal < idxArr[i]:
                maxIdxVal = idxArr[i]
        for i in range(len(idxArr)):
            if idxArr[i] == maxIdxVal:
                maxIdx = i
        return maxIdx, idxArr

    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)

    def factorial(self, num):
        if num > 1:
            return num * self.factorial(num - 1)
        else:
            return 1

    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)

    def reverseStar(self, num):
        if num > 0:
            if num == 1:
                print("*")
            else:
                print("*" * num)
                self.reverseStar(num - 1)

    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)