알고리즘 : 일련의 절차나 방법을 공식화한 형태로 표현한 것
01. 선형검색
선형검색
- 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1 # 존재하지 않는 index -1로 초기화
n = 0
while True:
if n == len(datas):
searchResultIdx = -1
break
elif datas[n] == searchData:
searchResultIdx = n
break
n += 1
print(f'searchResultIdx: [{searchResultIdx}]')보초법
-
보초법 : 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
- 검색 성공 : 마지막 인덱스 이전에 원하는 값이 검색된 경우
- 검색 실패 : 마지막 인덱스에 원하는 값이 검색된 경우
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
datas.append(searchData)
n = 0
while True:
# if n == len(datas):
# searchResultIdx = -1
# break
if datas[n] == searchData:
if n != len(datas) - 1:
searchResultIdx = n
break
n += 1
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
print(f'searchResultIdx: [{searchResultIdx}]')# 리스트에서 숫자'7'을 모두 검색하고 각각의 위치(인덱스)와 검색 개수를 출력
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('찾으려는 숫자 입력: '))
searchResultIdxs = []
nums.append(searchData)
n = 0
while True:
if nums[n] == searchData:
if n != len(nums) - 1:
searchResultIdxs.append(n)
else:
break
n += 1
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdxs: {searchResultIdxs}')
print(f'searchResultCnts: {len(searchResultIdxs)}')찾으려는 숫자 입력: 7
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
nums length: 12
searchResultIdxs: [1, 5, 8]
searchResultCnts: 3
02. 이진 검색
- 이진 검색 : 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
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('찾으려는 숫자 입력: '))
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}]')03. 순위
- 순위 : 수의 크고 작음을 이용해서 수의 순서를 정하는 것
import random
scores = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]
# 20번 반복해서 아이템이 0인 리스트
# 연속된 두 수의 크기를 비교해서 인덱스의 값 1씩 추가
for idx, sco1 in enumerate(scores):
for sco2 in scores:
if sco1 < sco2:
ranks[idx] += 1
print(scores)
print(ranks)
for i, s in enumerate(scores):
print(f'score:{s} \t rank:{ranks[i] + 1}')04. 버블정렬
- 버블정렬 : 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘이다.
nums = [10, 2, 7, 21, 0]
print(f'not sorted nums: {nums}')
length = len(nums) - 1
for i in range(length):
# 맨 끝까지 돌 필요가 없으므로 length-i까지만 비교
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(nums)
print()
print(f'sorted nums: {nums}')not sorted nums: [10, 2, 7, 21, 0][2, 10, 7, 21, 0]
[2, 7, 10, 21, 0][2, 7, 10, 21, 0]
[2, 7, 10, 0, 21][2, 7, 10, 0, 21]
[2, 7, 10, 0, 21][2, 7, 0, 10, 21]
[2, 7, 0, 10, 21][2, 0, 7, 10, 21]
[0, 2, 7, 10, 21]
sorted nums: [0, 2, 7, 10, 21]
05. 삽입정렬
- 삽입정렬 : 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
# insert.py
import sortMod as sm
nums = [5, 10, 2, 1, 0]
# ascending 오름차순
# 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, 5, 2, 10, 1]
# descending 내림차순
# 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}')
# sortMod 모듈
result = sm.sortNumber(nums, asc=False)
print(f'result: {result}')
# sortMod.py
def sortNumber(ns, asc=True):
if asc:
for i1 in range(1, len(ns)):
i2 = i1 - 1
cNum = ns[i1]
while ns[i2] > cNum and i2 >= 0:
ns[i2 + 1] = ns[i2]
i2 -= 1
ns[i2+1] = cNum
else:
for i1 in range(1, len(ns)):
i2 = i1 - 1
cNum = ns[i1]
while ns[i2] < cNum and i2 >= 0:
ns[i2 + 1] = ns[i2]
i2 -= 1
ns[i2 + 1] = cNum
return ns
# def sortNumber(ns, asc=True):
#
# for i1 in range(1, len(ns)):
# i2 = i1 - 1
# cNum = ns[i1]
#
# if asc:
# while ns[i2] > cNum and i2 >= 0:
# ns[i2 + 1] = ns[i2]
# i2 -= 1
# else:
# while ns[i2] < cNum and i2 >= 0:
# ns[i2 + 1] = ns[i2]
# i2 -= 1
#
# ns[i2+1] = cNum
#
# return ns
06. 선택정렬
- 선택정렬 : 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
nums = [4, 2, 5, 1, 3]
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
# nums[i], nums[minIdx] = nums[minIdx], nums[i]
print(f'nums: {nums}')07. 최댓값
- 최댓값 : 자료구조에서 가장 큰 값을 찾는다.
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 MaxAlgorithm:
def __init__(self, cs):
self.chars = cs
self.maxChar = 0
def getMaxChar(self):
self.maxChar = self.chars[0]
for c in self.chars:
# ord() : 문자열을 아스키코드로 변환해 주는 함수
if ord(self.maxChar) < ord(c):
self.maxChar = c
return self.maxChar
ma = MaxAlgorithm(['c', 'x', 'Q', 'A', 'e', 'P', 'p'])
maxChar = ma.getMaxChar()
print(f'maxChar: {maxChar}')08. 최솟값
- 최솟값 : 자료구조에서 가장 작은 값을 찾는다
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}')09. 최빈값
- 최빈값 : 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다.
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()
print(f'maxNum: {maxNum}')
indexes = [0 for i in range(maxNum + 1)]
print(f'indexes: {indexes}')
print(f'indexes length: {len(indexes)}')
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}로 가장 높다.')maxNum: 17
indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
indexes length: 18
indexes: [0, 1, 0, 1, 0, 0, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
maxNum: 4
maxNumIdx: 7
10. 근삿값
- 근삿값 : 특정 값(참값)에 가장 가까운 값을 근삿값이라고 한다.
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:
# abs() : 절대값 함수
absNum = abs(n - inputNum)
# print(f'absNum: {absNum}')
if absNum < minNum:
minNum = absNum
nearNum = n
print(f'nearNum: {nearNum}')nums: [19, 46, 4, 6, 8, 26, 25, 44, 24, 28, 23, 2, 43, 9, 18, 0, 40, 29, 13, 5]
input number: 34
inputNum: 34
nearNum: 29
11. 평균
- 평균 : 여러 수나 양의 중간값을 갖는 수
12. 재귀알고리즘
- 재귀 알고리즘 : 나 자신을 다시 호출하는 것
def recusion(num):
if num > 0:
print('*' * num)
return recusion(num - 1)
else:
return 1
recusion(10)
def factorial(num):
if num > 0:
return num * factorial(num - 1)
else:
return 1
print(f'factorial(10): {factorial(10)}')
13. 하노이의 탑
- 하노이의 탑 : 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다
- 한번에 한 개의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안 된다.
# 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')
else:
# (discNo-1)개들을 경유 기둥으로 이동
moveDisc(discCnt-1, fromBar, viaBar, toBar)
# discNo를 목적 기둥으로 이동
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')
# (discNo-1)개들을 도착 기둥으로 이동
moveDisc(discCnt-1, viaBar, toBar, fromBar)
moveDisc(3, 1, 3, 2)1disc: 1에서 3(으)로 이동!
2disc: 1에서 2(으)로 이동!
1disc: 3에서 2(으)로 이동!
3disc: 1에서 3(으)로 이동!
1disc: 2에서 1(으)로 이동!
2disc: 2에서 3(으)로 이동!
1disc: 1에서 3(으)로 이동!
14. 병합 정렬
- 병합정렬 : 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
def mSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx])
rightNums = mSort(ns[midIdx:len(ns)])
mergedNums = []
leftIdx = 0; rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
if leftNums[leftIdx] < rightNums[rightIdx]:
mergedNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergedNums.append(rightNums[rightIdx])
rightIdx += 1
mergedNums = mergedNums + leftNums[leftIdx:]
mergedNums = mergedNums + rightNums[rightIdx:]
print(f'mergedNums: {mergedNums}')
return mergedNums
nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mergedNums: {mSort(nums)}')mergedNums: [1, 8]
mergedNums: [3, 4]
mergedNums: [1, 3, 4, 8]
mergedNums: [2, 5]
mergedNums: [6, 10]
mergedNums: [2, 5, 6, 10]
mergedNums: [1, 2, 3, 4, 5, 6, 8, 10]
mergedNums: [1, 2, 3, 4, 5, 6, 8, 10]
15. 퀵정렬
- 퀵정렬 : 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
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)
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums))
데이터분석가