📌선형검색
선형검색: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
보초법: 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
dates = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'dates: {dates}')
print(f'dates length: {len(dates)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchDataIdx = -1
dates.append(searchData)
print(f'dates length: {len(dates)}')
n = 0
while True:
if dates[n] == searchData:
if n != len(dates) -1:
searchDataIdx = n
break
n += 1
print(f'dates: {dates}')
print(f'searchDataIdx: {searchDataIdx}')결과:
dates: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
dates length: 10찾으려는 숫자 입력: 55
dates length: 11
dates: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 55]
searchDataIdx: -1
📌이진검색
이진검색 : 정렬되어 있는 자료구조애서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
nums = [4,10,22,5,0,17,7,11,9,61,88]
nums.sort() #반드시 정렬
searchData = int(input('찾으려는 숫자 입력: '))
searchDataIdx = -1
staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print('nums = {}' .format(nums))
while searchData <= nums[len(nums)-1] and searchData >= nums[0]:
if searchData == nums[len(nums)-1]:
searchDataIdx = len(nums) - 1
break
elif searchData > midVal:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
elif searchData < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
elif searchData == midVal:
searchDataIdx = midIdx
break
print('seachDataIdx: {}' .format(searchDataIdx))결과:
찾으려는 숫자 입력: 22
nums = [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
seachDataIdx: 8
📌순위
import random
nums = random.sample(range(50, 101), 10)
ranks = [0 for i in range(10)]
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}')
결과:
nums: [92, 74, 67, 90, 61, 52, 78, 82, 100, 79]
ranks: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
nums: [92, 74, 67, 90, 61, 52, 78, 82, 100, 79]
ranks: [1, 6, 7, 2, 8, 9, 5, 3, 0, 4]
📌버블정렬
버블정렬 : 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰숫자를 가장 끝으로 옮기는 알고리즘이다.
nums = [10, 2, 7, 21, 0]
print(f'not sorted nums: {nums}')
length = len(nums) - 1
for i in range(length):
for j in range(length -i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
print(nums)
print()
print(f'sorted nums: {nums}')결과:
[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]
📌삽입정렬
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}')
#descending_내림차순
nums = [0, 5, 2, 10, 1]
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]
nums: [10, 5, 2, 1, 0]
📌선택정렬
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
nums[i], nums[minIdx] = nums[minIdx], nums[i]
print(nums)
print()
print(nums)결과:
[1, 2, 5, 4, 3] \
[1, 2, 5, 4, 3] \
[1, 2, 3, 4, 5] \
[1, 2, 3, 4, 5][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'maxNums: {maxNum}')결과:
maxNums: 20
📌최솟값
class minAlgo:
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 = minAlgo([-2, -4, 5, 7 ,10, 0, 8 , 20, -11])
minNum = ma.getMinNum()
print(f'minNum: {minNum}')결과:
minNum: -11
