python 알고리즘 01

알고리즘

알고리즘은, 특정한 문제를 해결하기 위한 일련의 절차나 방법을 의미합니다. 이러한 알고리즘은 컴퓨터 프로그래밍을 비롯한 다양한 분야에서 활용되며, 입력값을 받아 일련의 처리 과정을 거친 후 원하는 출력값을 얻을 수 있도록 합니다.

알고리즘은 다양한 문제를 해결하기 위한 다양한 방식으로 구현될 수 있습니다. 이러한 방식은 보통 프로그래밍 언어나 수학적 표현 등으로 표현되며, 각각의 방식은 특정한 문제에 대해 최적의 성능을 보장하기 위해 고안되었습니다.

좋은 알고리즘은 입력값의 크기가 커져도 효율적으로 동작할 수 있는 것이 중요합니다. 이를 위해 알고리즘의 시간 복잡도나 공간 복잡도 등을 고려하여 구현합니다. 또한, 알고리즘은 정확성을 보장해야 하므로, 각각의 단계에서 적절한 조건문이나 반복문 등을 사용하여 적절한 처리가 이루어지도록 합니다.

선형 검색

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

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas: {len(datas)}')

searchDatas = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1

n = 0
while True:

    if n == len(datas):
        searchResultIdx = -1
        break

    elif datas[n] == searchDatas:
        searchResultIdx = n
        break

    n += 1

print(f'searchResultIdx: {searchResultIdx}')

보초법

• 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다
• 검색성공: 마지막 이전에 '값'이 검색된 경우
• 검색실패: 마지막에 '값'이 검색된 경우

실습

• 리스트에서 가장 앞에 있는 숫자 '7'을 검색하고 위치(인덱스)를 출력하자
  nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

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

searchData = int(input('input search number: '))
searchDataIdx = -1

nums.append(searchData) #보초법

n = 0
while True:

    if nums[n] == searchData:
        if n != len(nums) - 1:
            searchDataIdx = n
        break

    n += 1
print(f'nums: {nums}')
print(f'nums: {len(nums)}')
print(f'searchDataIdx: {searchDataIdx}')

if searchDataIdx < 0:
    print('not search index')

else:
    print(f'search index: {searchDataIdx}')

• 리스트에서 숫자 '7'을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력하자
  nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

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

searchData = int(input('input search number: '))
searchDataIdxs = []

nums.append(searchData) #보초법

n = 0
while True:

    if nums[n] == searchData:
        if n != len(nums) - 1:
            searchDataIdxs.append(n)
        else:
            break

    n += 1

print(f'nums: {nums}')
print(f'nums: {len(nums)}')
print(f'searchDataIdxs: {searchDataIdxs}')
print(f'searchDataCnt: {len(searchDataIdxs)}')

이진 검색

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

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

print(f'searchResultIdx: {searchResultIdx} ')

리스트를 오름차순으로 정렬한 후 '7' 검색하고 위치 찾기

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums.sort()

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

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

staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]

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

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

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

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

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: {searchResultIdx} ')

순위

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

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

결과

nums: 71 	 rank: 11
nums: 64 	 rank: 14
nums: 99 	 rank: 1
nums: 56 	 rank: 17
nums: 98 	 rank: 2
nums: 60 	 rank: 15
nums: 73 	 rank: 10
nums: 80 	 rank: 7
nums: 53 	 rank: 19
nums: 70 	 rank: 12
nums: 58 	 rank: 16
nums: 84 	 rank: 6
nums: 77 	 rank: 8
nums: 74 	 rank: 9
nums: 92 	 rank: 4
nums: 65 	 rank: 13
nums: 54 	 rank: 18
nums: 89 	 rank: 5
nums: 50 	 rank: 20
nums: 95 	 rank: 3

Process finished with exit code 0

순위(실습)

• 학급 학생(20명) 중간고사/기말고사 성적을 이용 각각 순위를 구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력하는 프로그램(성적은 난수 이용)

class 정의

class RankDeviation:

    def __init__(self, mss, ess):
        self.midStuScores = mss
        self.endStuScores = ess
        self.midRanks = [0 for i in range(len(mss))]
        self.endRanks = [0 for i in range(len(mss))]
        self.rankDeviation = [0 for i in range(len(mss))]

    def setRank(self, ss, rs):
        for idx, score1 in enumerate(ss):
            for score2 in ss:
                if score1 < score2:
                    rs[idx] += 1


    def setMidRank(self):
        self.setRank(self.midStuScores, self.midRanks)

    def getMidRank(self):
        return self.midRanks

    def setEndRank(self):
        self.setRank(self.endStuScores, self.endRanks)

    def getEndRank(self):
        return self.endRanks

    def printRankDeviation(self):
        for idx, mRank in enumerate(self.midRanks):

            deviation = mRank - self.endRanks[idx]

            if deviation > 0:
                deviation = '↑' + str(abs(deviation))
            elif deviation < 0:
                deviation = '↓' + str(abs(deviation))
            else:
                deviation = '=' + str(abs(deviation))

            print(f'mid_rank: {mRank} \t end_rank: {self.endRanks[idx]} \t Deviation: {deviation}')

실행

import rank as rm

import random

midStuScores = random.sample(range(50, 101), 20)
endStuScores = random.sample(range(50, 101), 20)

rd = rm.RankDeviation(midStuScores, endStuScores)
rd.setMidRank()
print(f'midStuScores: {midStuScores}')
print(f'mid_rank: {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScores: {endStuScores}')
print(f'end_rank: {rd.getEndRank()}')

rd.printRankDeviation()

버블 정렬

• 이웃한 두 원소를 비교하여 정렬하는 알고리즘
• 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘

nums = [10, 2, 7, 21, 0]
print(f'not sored nums: {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

            nums[j], nums[j + 1] = nums[j + 1], nums[j] # 간략하게 사용하는 방법

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

결과

not sored nums: [10, 2, 7, 21, 0]
sorted nums: [0, 2, 7, 10, 21]

mod

# 깊은 복사 활용

import copy


def bubbleSort(ns, deepCopy = True):

   if deepCopy:
       cns = copy.copy(ns)
       # students 를 완전히 copy해서 새로운 자료구조 생성됨
   else:
       cns = ns
   length = len(cns) - 1
   for i in range(length):
       for j in range(length - i):
           if cns[j] > cns[j + 1]:
               cns[j], cns[j + 1] = cns[j + 1], cns[j]

   return cns

실행

import random as rd
import sortMod as sm

students = []

for i in range(20):
    students.append(rd.randint(170, 185))

print(f'students: {students}')


sortedStudents = sm.bubbleSort(students)
print(f'studnets: {students}')
print(f'sortedStudents: {sortedStudents}')

삽입 정렬

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

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]
        i2 -= 1

    nums[i2 + 1] = cNum

print(f'nums: {nums}')

결과

nums: [0, 1, 2, 5, 10]

파이썬에서 버블 정렬과 삽입 정렬은 정렬 알고리즘 중 가장 간단한 알고리즘 중 하나입니다.

버블 정렬은 인접한 두 원소를 비교하면서 작은 원소를 앞으로 이동시키고, 큰 원소는 뒤로 이동시켜 정렬하는 방식입니다. 따라서 버블 정렬은 시간 복잡도가 O(n^2)로, 원소의 개수가 많아질수록 처리 시간이 길어지는 단점이 있습니다.

반면에, 삽입 정렬은 리스트를 두 부분으로 나누고, 앞 부분은 정렬된 상태로 유지하며, 뒷 부분의 원소를 앞 부분에서 적절한 위치에 삽입해가면서 정렬하는 방식입니다. 따라서 삽입 정렬은 시간 복잡도가 O(n^2)이지만, 버블 정렬보다 평균적으로 더 빠르게 처리됩니다. 또한, 리스트가 이미 거의 정렬된 경우 삽입 정렬은 빠른 속도로 처리할 수 있습니다.

따라서, 버블 정렬은 단순하면서 구현하기 쉽지만 처리 시간이 더 걸리고, 삽입 정렬은 평균적으로 더 빠르지만 알고리즘이 조금 더 복잡합니다.

선택 정렬

• 가장 작은 데이터를 찾아 자리 바꿈
• 주어진 리스트 중 최소값을 찾고, 그 값을 맨 앞에 위치한 갑소가 교체하는 방식으로 자료 정렬하는 알고리즘

nums = [4, 2, 5, 1, 3]
print(f'nums: {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


    tempNum = nums[i]
    nums[i] = nums[minIdx]
    nums[minIdx] = tempNum

print(f'nums: {nums}')

결과

nums: [4, 2, 5, 1, 3]
nums: [1, 2, 3, 4, 5]

최대값

• 자료구조에서 가장 큰 값을 찾는다

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0

    def getMaxNum(self):

        self.maxNum = self.nums[0]

        for n in self.nums:
            if self.maxNum < n:
                self.maxNum = n

        return self.maxNum


ma = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])

maxNum = ma.getMaxNum()
print(f'maxNum: {maxNum}')

최소값

• 자료구조에서 가장 작은 값을 찾는다

class MinAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.minNum = 0

    def getMinNum(self):

        self.minNum = self.nums[0]

        for n in self.nums:
            if self.minNum > n:
                self.minNum = n

        return self.minNum


ma = MinAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])

minNum = ma.getMinNum()
print(f'minNum: {minNum}')

최빈값

• 빈도수가 가장 높은 데이터를 찾는다

# 최빈값 구하려면 최대값을 먼저 구해야함

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumIdx = 0 # 인덱스 추가

    def setMaxIdxAndNum(self):
        self.maxNum = self.nums[0]
        self.maxNumIdx = 0

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

    # 추가
    def getMaxNum(self):
        return self.maxNum

    def getMaxNumIdx(self):
        return self.maxNumIdx

nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlo = MaxAlgorithm(nums)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()

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

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

print(f'indexes: {indexes}')


maxAlo = MaxAlgorithm(indexes)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()

print(f'maxNum: {maxNum}')
print(f'maxNumIdx: {maxNumIdx}')

print(f' 즉, {maxNumIdx}의 빈도수가 {maxNum}로 가장 높다')

결과

indexes: [0, 1, 0, 1, 0, 0, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
maxNum: 4
maxNumIdx: 7
 즉, 7의 빈도수가 4로 가장 높다

근삿값

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

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) #abs 사용하면 절대값을 찾음

    if absNum < minNum:
        minNum = absNum
        nearNum = n

print(f'nearNum: {nearNum}')