해당 글은 제로베이스데이터스쿨 학습자료를 참고하여 작성되었습니다
📌알고리즘
- 어떤 문제를 해결하기 위한 절차나 방법을 공식화한 것
📌선형검색
- 선형으로 나열된 데이터를 스캔하면서 원하는 값을 찾는 것
(출처:제로베이스데이터스쿨)
📝입력
import random
datas = random.sample(range(10), 10)
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
try:
searchData = int(input('찾으려는 숫자 입력: '))
except:
print('1~9 사이의 정수를 입력하세요')
else:
searchResultIdx = -1
n = 0
while True:
if searchData == datas[n]:
searchResultIdx = n
print(f'searchResultIdx: {searchResultIdx}')
break
else:
n += 1
if n == len(datas):
print('대상을 찾을 수 없습니다')
break🧾출력
datas: [1, 8, 7, 2, 0, 9, 3, 6, 5, 4]
datas length: 10
찾으려는 숫자 입력: 3
searchResultIdx: 6
----------------------------------------
datas: [3, 2, 0, 6, 9, 5, 8, 1, 4, 7]
datas length: 10
찾으려는 숫자 입력: 23
대상을 찾을 수 없습니다보초법
- 마지막 인덱스에 찾으려는 값을 추가하여 종료과정을 간략화
(출처:제로베이스데이터스쿨)
📝입력
import random
datas = random.sample(range(10), 10)
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
datas.append(searchData)
n = 0
while True:
if searchData == datas[n]:
if n != len(datas) - 1:
searchResultIdx = n
break
n += 1
print(f'searchResultIdx: {searchResultIdx}')🧾출력
datas: [3, 1, 0, 8, 7, 2, 5, 9, 4, 6]
datas length: 10
찾으려는 숫자 입력: 9
searchResultIdx: 7
---
datas: [6, 1, 4, 3, 8, 5, 2, 9, 7, 0]
datas length: 10
찾으려는 숫자 입력: 23
searchResultIdx: -1📌이진검색
- 정렬되어 있는 자료구조에서 중앙값과의 비교로 데이터를 검색한다
(출처:제로베이스데이터스쿨)
📝입력
import random
nums = sorted(random.sample(range(0, 20), 10))
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
searchNum = int(input('input search num : '))
if searchNum not in nums:
print('"searchNum" does not exist in "nums"')
else:
searchResultIdx = -1
staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
while True:
if searchNum > midVal:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'midxIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchNum < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'midxIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchNum == midVal:
searchResultIdx = midIdx
break
print(f'searchResultIdx: {searchResultIdx}')🧾출력
nums: [1, 4, 5, 7, 10, 14, 15, 17, 18, 19]
nums length: 10
input search num : 3
"searchNum" does not exist in "nums"
---
nums: [0, 2, 3, 5, 7, 8, 13, 17, 18, 19]
nums length: 10
input search num : 13
midxIdx: 6
midVal: 13
searchResultIdx: 6📌순위
- 값의 크고 작음을 기준으로 우열을 결정하는 것
(출처:제로베이스데이터스쿨)
📝입력
import random
nums = random.sample(range(50, 101), 5)
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
ranks = [0 for i in range(5)]
for idx, n1 in enumerate(nums):
for n2 in nums:
if n2 > n1:
ranks[idx] += 1
for score, rank in zip(nums, ranks):
print(f'Score: {score}\t Rank: {rank}')🧾출력
nums: [76, 55, 88, 72, 57]
nums length: 5
Score: 76 Rank: 1
Score: 55 Rank: 4
Score: 88 Rank: 0
Score: 72 Rank: 2
Score: 57 Rank: 3```📌버블정렬
- 처음부터 끝까지 인접한 데이터끼리 비교하여 옮기면서 정렬하는 것
(출처:제로베이스데이터스쿨)
📝bubble_sort.py
import copy
class bubbleSort:
def __init__(self, nums, reverse=False):
self.nums = copy.deepcopy(nums)
self.reverse = reverse
def sorted(self):
if self.reverse == False:
length = len(self.nums) - 1
for i in range(length):
for j in range(length - i):
if self.nums[j] > self.nums[j+1]:
self.nums[j], self.nums[j+1] = self.nums[j+1], self.nums[j]
elif self.reverse == True:
length = len(self.nums) - 1
for i in range(length):
for j in range(length - i):
if self.nums[j] < self.nums[j + 1]:
self.nums[j], self.nums[j + 1] = self.nums[j + 1], self.nums[j]
return self.nums📝입력
import bubble_sort as bs
import random
nums = random.sample(range(5, 20), 10)
print(f'nums: {nums}')
datas = bs.bubbleSort(nums, reverse=True)
print(f'sort: {datas.sorted()}')
datas = bs.bubbleSort(nums)
print(f'sort: {datas.sorted()}')🧾출력
nums: [7, 8, 18, 6, 5, 13, 19, 12, 14, 16]
sort: [19, 18, 16, 14, 13, 12, 8, 7, 6, 5]
sort: [5, 6, 7, 8, 12, 13, 14, 16, 18, 19]📌삽입정렬
- 정렬되어 있는 자료구조에 다음 데이터의 위치를 찾아서 추가한다
(출처:제로베이스데이터스쿨)
📝입력
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: [5, 10, 2, 1, 0]
nums: [2, 5, 10, 1, 0]
nums: [1, 2, 5, 10, 0]
nums: [0, 1, 2, 5, 10]📌선택정렬
- 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘
(출처:제로베이스데이터스쿨)
📝입력
import random
nums = random.sample(range(10), 5)
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
nums[i], nums[minIdx] = nums[minIdx], nums[i]
print(f'nums: {nums}')
print(f'final nums: {nums}')🧾출력
nums: [8, 7, 0, 6, 9]
nums: [0, 7, 8, 6, 9]
nums: [0, 6, 8, 7, 9]
nums: [0, 6, 7, 8, 9]
nums: [0, 6, 7, 8, 9]
final nums: [0, 6, 7, 8, 9]📌최댓값, 최솟값
- 자료구조에서 가장 큰 / 작은 값을 찾는다
(출처:제로베이스데이터스쿨)
📝입력
class MaxMinAlgorithm:
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
def getNums(self):
return self.nums
def getMaxNum(self):
self.maxNum = self.nums[0]
for n in self.nums:
if self.maxNum < n:
self.maxNum = n
return self.maxNum
def getMinNum(self):
self.minNum = self.nums[0]
for n in self.nums:
if self.minNum > n:
self.minNum = n
return self.minNum
import random
nums = random.sample(range(10), 5)
ma = MaxMinAlgorithm(nums)
maxNum = ma.getMaxNum()
minNum = ma.getMinNum()
print(f'nums: {ma.getNums()}')
print(f'maxNum: {maxNum}')
print(f'minNum: {minNum}')🧾출력
nums: [1, 2, 4, 8, 0]
maxNum: 8
minNum: 0