제로베이스 데이터 스쿨/일일 스터디 노트
16일차 스터디노트 / 파이썬 알고리즘(선형검색, 이진검색, 순위, 버블정렬, 삽입정렬, 선택정렬, 재귀, 하노이의 탑, 병합정렬, 퀵정렬)
김뎀뎀
2023. 1. 22. 11:39
※제로베이스 데이터 취업스쿨 11기 수강 중
📗 16일차 공부 내용 요약
[ 알고리즘과 파이썬 ]
파이썬을 활용한 다양한 알고리즘의 코드들을 작성해보았다.
1. 선형검색
2. 이진검색
3. 순위
4. 버블정렬
5. 삽입정렬
6. 선택정렬
7. 최댓값
8. 최솟값
9. 최빈값
10. 근삿값
11. 평균
12. 재귀
13. 하노이의 탑
14. 병합정렬
15. 퀵정렬
📖 16일차 공부 내용 자세히
1. 선형검색
선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다
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
n = 0
while True:
if n == len(datas): #데이터 끝까지 검색했을 때 종료
searchResultIdx = -1 #이 코드가 필할까
break
elif datas[n] == searchData:
searchResultIdx = n
break
n += 1
print(f'searchResultIdx: [{searchResultIdx}]')
2. 이진검색
정렬되어 있는 자료구조에서 중앙값의 크고 작음을 이용해서 데이터를 검색한다
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}]')3. 순위
수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다
nums = random.sample(range(50,101),20)
ranks = [ 0 for i in range(20) ] #길이가 20인 순위를 저장할 리스트 생성, 모든 요소 0으로 초기화
print(f'nums : {nums}')
print(f'ranks : {ranks}')
for idx, num1 in enumerate(nums):
for num2 in nums :
if num1 < num2 :
ranks[idx] += 1
print(f'nums : {nums}')
print(f'ranks : {ranks}')
for n in range(20):
print(f'num : {nums[n]}, randk {ranks[n]+1}')
4. 버블정렬
처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
#맨 끝부터 그 앞까지 차근차근 밀어내는 것
nums = [10, 2, 7, 21, 0]
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(nums)
print()
print(f'sorted nums: {nums}')
5. 삽입정렬
정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다
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: #지금값보다 앞의 값이 크고, 앞의 값의 인덱스가 0보다 보다 크거나 같다면
nums[i2 + 1] = nums[i2] #지금 값의 위치에 앞의 값을 할당, 지금값을 넣기 위해 앞의 자리를 비워두는 것이다
i2 -= 1 #앞의 앞으로 이동
nums[i2+1] = cNum #위 반복문에서 i2가 한번 줄어든 후 끝나기 때문에, i2를 다시 복구시킨후 지금값을 그 위치에 넣어준다
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}')
6. 선택정렬
주어진 리스트 중 최솟값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 정렬하는 알고리즘
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}')
7. 최댓값
자료구조에서 가장 큰 값을 찾는다
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}')8. 최솟값
자료구조에서 가장 작은 값을 찾는다
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}')
9. 최빈값
데이터에서 빈도수가 가장 많은 데이터를 찾는다
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}로 가장 높다.')
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:
absNum = abs(n - inputNum)
# print(f'absNum: {absNum}')
if absNum < minNum:
minNum = absNum
nearNum = n
print(f'nearNum: {nearNum}')
11. 평균
여러 수나 양의 중간값을 갖는 수를 평균이라고 한다
import random
nums = random.sample(range(0, 100), 30)
print(f'nums: {nums}')
total = 0
for n in nums:
total += n
average = total / len(nums)
print(f'average: {round(average, 2)}')
# 50이상 90이하 수들의 평균
import random
nums = random.sample(range(0, 100), 30)
print(f'nums: {nums}')
targetNums = []
total = 0
for n in nums:
if n >= 50 and n <= 90:
total += n
targetNums.append(n)
print(f'targetNums: {targetNums}')
average = total / len(targetNums)
print(f'average: {round(average, 2)}')
# 정수들의 평균
nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print(f'nums: {nums}')
targetNums = []
total = 0
for n in nums:
if n - int(n) == 0:
total += n
targetNums.append(n)
print(f'targetNums: {targetNums}')
average = total / len(targetNums)
print(f'average: {round(average, 2)}')
# 실수(소수)들의 평균
nums = [4, 5.12, 0, 5, 7.34, 9.1, 9, 3, 3.159, 1, 11, 12.789]
print(f'nums: {nums}')
targetNums = []
total = 0
for n in nums:
if n - int(n) != 0:
total += n
targetNums.append(n)
print(f'targetNums: {targetNums}')
average = total / len(targetNums)
print(f'average: {round(average, 2)}')
12. 재귀
나 자신을 다시 호출하는 것을 재귀라고 한다
def recursion(num):
if num > 0:
print('*' * num)
return recursion(num-1)
else:
return 1 #recursion(0)이 되는 순간, 재귀없이 1을 반환
recursion(10)
13. 하노이의 탑
퍼즐 게임의 일종으로, 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기되, 한 번에 한 개의 원판만 옮길 수 있으며 큰 원판이 작은 원판 위에 있어서는 안된다
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt} disc : {fromBar}에서 {toBar}로 이동')
else:
#마지막 원판 빼고 모두 경유지로 이동
moveDisc(discCnt-1, fromBar, viaBar,toBar)
#남은 원판 도착지로 이동
print(f'{discCnt} disc : {fromBar}에서 {toBar}로 이동')
#경유지에 있는 것들을 도착지로 이동
moveDisc(discCnt-1, viaBar, toBar,fromBar)
moveDisc(3,1,3,2)
14. 병합정렬
자료구조를 분할하고 각각의 분할된 자료 구조를 정렬한 후 다시 병합하여 정렬한다
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt} disc : {fromBar}에서 {toBar}로 이동')
else:
#마지막 원판 빼고 모두 경유지로 이동
moveDisc(discCnt-1, fromBar, viaBar,toBar)
#남은 원판 도착지로 이동
print(f'{discCnt} disc : {fromBar}에서 {toBar}로 이동')
#경유지에 있는 것들을 도착지로 이동
moveDisc(discCnt-1, viaBar, toBar,fromBar)
moveDisc(3,1,3,2)
15. 퀵정렬
기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다
def qSort(ns):
if len(ns)<2:
return ns
midIdx = len(ns) // 2
midVal = ns[midIdx]
smallNum =[]
sameNum = []
bigNum = []
for n in ns:
if n < midVal:
smallNum.append(n)
elif n == midVal:
sameNum.append(n)
else:
bigNum.append(n)
return qSort(smallNum) + sameNum + qSort(bigNum)
nums = [8, 3, 6, 1, 2, 9, 10, 4, 2, 4]
print(qSort(nums))
➰ 16일차 후기
버블정렬부터 시작해 정렬 파트에서 머리가 띵했다, 아 이제가 고비구나 싶은...
강의를 듣고서는 바로 이해가 안되서 코드를 계속 뜯어서보고 뜯어서 보고 했다.
그러고 나서는 그래도 이해하고 작성했는데 또 뒷부분을 학습하고 나니 가물가물하다.
게다가 이제 재귀를 활용하는 하노이탑과 병합정렬이 나오니까 정말 ... 혼돈 그자체^^
이해가 잘 안되서, 유튜브에 검색해서 영상들을 보는데 댓글로도 어려운 부분이라고 하는 분들이 많아서 그래도,, 나만 어려운 거 아니구나..라고 안심하면서 몇번의 좌절(?)을 거치고 그나마 이해를,, 했다.
'알고리즘'이라는 이름에 겁을 먹었는데, 겁 먹어도 됬었다^^
16일차 노트로 합쳐 썼지만, 3일정도 쪼개서 공부했다,, 도저히 하루 다 하다가는 머리에 과부하가 올것만 같았음,,,
※본 내용은 제로베이스 데이터 취업 스쿨에서 제공하는 학습 내용에 기반합니다.