알고리즘이란?
알고리즘, 또한 셈법이란, 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문자를 풀어맺기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다. 즉, 문제풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다.
선형검색이란?
선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
def linearSearch(nums):
print('선형검색 시작!')
n = 0
searchNum = int(input('찾으려는 숫자 입력: '))
searchNumIdx = -1
while True:
if n == len(nums):
searchNumIdx = -1
break
elif nums[n] == searchNum:
searchNumIdx = n
break
n += 1
return searchNumIdx예시
nums = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
searchNum = int(input('찾으려는 숫자 입력: '))
n = 0
searchNumIdx = -1
while True:
if n == len(nums):
searchNumIdx = -1
break
elif nums[n] == searchNum:
searchNumIdx = n
break
n += 1
print(searchNumIdx)
# 찾으려는 숫자 입력: 7
# 3
* 보초법
마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
def sentinelMethod(nums):
print('보초법 선형검색 시작!')
searchIdx = -1
searchNum = int(input('찾으려는 숫자 입력: '))
nums.append(searchNum)
n = 0
searchNumIdx = -1
while n < len(nums) - 1:
if searchNum == nums[n]:
if n != len(nums):
searchIdx = n
n += 1
return searchIdx
예시
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
ansArr = []
cnt = 0
searchNum = int(input('찾으려는 숫자 입력: '))
nums.append(searchNum)
n = 0
searchNumIdx = -1
while n < len(nums) - 1:
if searchNum == nums[n]:
if n != len(nums):
ansArr.append(n)
cnt += 1
n += 1
print(f'찾는 숫자의 갯수: {cnt}, 인덱스: {ansArr}')
# 찾으려는 숫자 입력: 7
# 찾는 숫자의 갯수: 3, 인덱스: [1, 5, 8]
이진검색이란?
정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
def binarySearch(datas):
print('이진 검색 시작!')
datas.sort()
print(f'정렬된 Array: {datas}')
searchValue = int(input('찾으려는 값 입력: '))
searchIdx = -1
staIndex = 0
endIndex = len(datas) - 1
midIndex = (staIndex + endIndex) // 2
midVal = datas[midIndex]
n = 1
while staIndex <= endIndex:
if searchValue > midVal:
staIndex = midIndex
midIndex = (staIndex + endIndex) // 2
midVal = datas[midIndex]
print(f'{n}회차, midIdx: {midIndex}, midVal: {midVal}')
n += 1
elif searchValue < midVal:
endIndex = midIndex
midIndex = (staIndex + endIndex) // 2
midVal = datas[midIndex]
print(f'{n}회차, midIdx: {midIndex}, midVal: {midVal}')
n += 1
elif searchValue == midVal:
searchIdx = midIndex
break
print(f'결과: {searchIdx}')
return searchIdx
순위란?
수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다.
def rank(nums):
print('순위 시작!')
ranks = [0 for i in range(len(nums))]
for idx, num1 in enumerate(nums):
for num2 in nums:
if num1 < num2:
ranks[idx] += 1
for idx, num in enumerate(nums):
print(f'num: {num} \t rank: {ranks[idx] + 1}')
예시
import random
nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]
for idx, num1 in enumerate(nums):
for num2 in nums:
if num1 < num2:
ranks[idx] += 1
for idx, num in enumerate(nums):
print(f'num: {num} \t rank: {ranks[idx] + 1}')
# num: 71 rank: 12
# num: 85 rank: 6
# num: 73 rank: 10
# num: 82 rank: 7
# num: 63 rank: 14
# num: 57 rank: 17
# num: 92 rank: 3
# num: 96 rank: 2
# num: 69 rank: 13
# num: 76 rank: 9
# num: 61 rank: 15
# num: 55 rank: 18
# num: 51 rank: 19
# num: 89 rank: 5
# num: 72 rank: 11
# num: 99 rank: 1
# num: 90 rank: 4
# num: 50 rank: 20
# num: 80 rank: 8
# num: 58 rank: 16
버블 정렬이란?
처음부터 끝까지, 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮긴다.
def bubbleSort(nums):
print('버블정렬 시작!')
for j in range(len(nums)):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
temp = nums[i]
nums[i] = nums[i + 1]
nums[i + 1] = temp
return nums예시
import random
students = [random.randint(170, 185) for i in range(20)]
def bubbleSort(nums):
for j in range(len(nums)):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
temp = nums[i]
nums[i] = nums[i + 1]
nums[i + 1] = temp
return nums
print(bubbleSort(students))
# [170, 170, 170, 172, 172, 172, 174, 174, 175, 176, 179, 179, 180, 181, 181, 183, 183, 185, 185, 185]
삽입 정렬이란?
정렬되어 있는 자료 배열과 비교하여, 정렬 위치를 찾는 것이다.
def insertionSort(nums):
print('삽입 정렬 시작!')
isAscOrDec = int(input('1: 오름차순, 2: 내림차순'))
if isAscOrDec == 1:
for i in range(1, len(nums)):
j = i - 1
cNum = nums[i]
while nums[j] > cNum and j >= 0:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = cNum
return nums
elif isAscOrDec == 2:
for i in range(1, len(nums)):
j = i - 1
cNum = nums[i]
while nums[j] < cNum and j >= 0:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = cNum
return nums
선택정렬이란?
주어진 리스트 중에 최솟값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
def selectionSort(nums):
print('선택정렬 시작!')
isAscOrDec = int(input('1: 오름차순, 2: 내림차순'))
if isAscOrDec == 1:
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
return nums
elif isAscOrDec == 2:
for i in range(len(nums) - 1):
maxIdx = i
for j in range(i + 1, len(nums)):
if nums[maxIdx] < nums[j]:
maxIdx = j
tempNum = nums[i]
nums[i] = nums[maxIdx]
nums[maxIdx] = tempNum
return nums
최댓값과 최솟값
def maxSearch(self, nums):
maxValue = 0
for i in range(len(nums)):
if nums[i] > maxValue:
maxValue = nums[i]
return maxValue
def minSearch(self, nums):
minValue = 0
for i in range(len(nums)):
if nums[i] < minValue:
minValue = nums[i]
return minValue
최빈값
def modeSearch(self, nums):
maxVal = 0
for i in range(len(nums)):
if maxVal < nums[i]:
maxVal = nums[i]
idxArr = [0 for _ in range(maxVal + 1)]
for num in nums:
idxArr[num] += 1
maxIdxVal = 0
maxIdx = -1
for i in range(len(idxArr)):
if maxIdxVal < idxArr[i]:
maxIdxVal = idxArr[i]
for i in range(len(idxArr)):
if idxArr[i] == maxIdxVal:
maxIdx = i
return maxIdx, idxArr
'자료구조와 알고리즘, 수학, 통계학' 카테고리의 다른 글
| 알고리즘 03. 지금까지 배운 알고리즘들 정리 (0) | 2024.03.02 |
|---|---|
| 알고리즘 02. 근삿값, 평균, 재귀, 하노이의탑, 병합정렬, 퀵정렬 (0) | 2024.03.02 |
| 자료구조와 알고리즘 기초 03. 딕셔너리 (0) | 2024.02.24 |
| 자료구조 기초 정리 02. 튜플의 활용 (0) | 2024.02.24 |
| 자료구조 기초 정리 01. 튜플/딕셔너리/세트의 정의, 리스트의 활용 (1) | 2024.02.24 |