▷ 오늘 학습 내용: 알고리즘 강의(1~3)
01_선형 검색
선형검색: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다 → 검색 성공 or 검색 실패
보초법: 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
- 리스트에서 숫자 '7'을 모두 검색하고 각각의 인덱스와 검색 개수 출력하기
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print('nums: {}'.format(nums))
print('length: {}'.format(len(nums)))
searchData = int(input('input searchNumber: '))
searchResultIdx = []
nums.append(searchData)
n = 0
while True:
if nums[n] == searchData:
if n != len(nums)-1:
searchResultIdx.append(n)
else:
break
n += 1
print('nums: {}'.format(nums))
print('length: {}'.format(len(nums)))
print('idx: {}'.format(searchResultIdx))
print('idxCnt: {}'.format(len(searchResultIdx)))02_이진 검색
이진 검색: 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
- 리스트를 오름차순으로 정렬한 후 검색할 숫자의 인덱스 출력하기
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums.sort()
searchData = int(input('search number: '))
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]
elif searchData < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
elif searchData == midVal:
searchResultIdx = midIdx
break
print('searchResultIdx: {}'.format(searchResultIdx))03_순위
수의 크고 작음을 이용해서 수의 순서를 정하는 것
- 50부터 100까지 정수 20개를 추출한 뒤 리스트에서 각 숫자의 순위 출력
import random
nums = random.sample(range(50,101),20)
ranks = [0 for i in range(20)] #초기 순위 모두 0으로 설정
for idx, num1 in enumerate(nums):
for num2 in nums:
if num1 < num2:
ranks[idx] += 1
print('nums: {}'.format(nums))
print('ranks: {}'.format(ranks))
# 숫자, 순위 보기 좋게 출력하기
for idx, num in enumerate(nums):
print(f'num: {num} \t rank: {ranks[idx] +1 }')04_버블 정렬
처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
nums = [10, 2, 7, 21, 0]
length = len(nums)-1 # length = 4
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]
# temp = nums[j]
# nums[j] = nums[j+1]
# nums[j+1] = temp
print(f'sorted nums: {nums}')- 키 순서로 줄 세우기(학생수는 20명, 키는 random 모듈을 이용하여 170~185사이로 생성)
- import copy → copy.deepcopy(a) → a라는 데이터 깊은 복사
05_삽입 정렬
정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
# 오름차순
nums = [5, 10, 2, 8, 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, 8, 0] → [2, 5, 10, 8, 0]
# → [2, 5, 8, 10, 0] → [0, 2, 5, 8, 10]
# 내림차순
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: [5, 0, 2, 10, 1] → [5, 2, 0, 10, 1]
# → [10, 5, 2, 0, 1] → [10, 5, 2, 1, 0]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}')
# [4, 2, 5, 1, 3] → [1, 2, 5, 4, 3] → [1, 2, 3, 4, 5]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('maxNum: {}'.format(maxNum))▷ 내일 학습 계획: 알고리즘 강의(4~7)
