✒️알고리즘 이란?
문제를 해결하기 위해 정해진 일련의 절차이다.
계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다.
✒️선형검색 이란?
선형의로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
n = int(input('찾으려는 숫자 입력 : '))
resultIndex = -1
liner = []
for i in range(len(datas)):
liner.append(datas[i])
print(f'{i + 1} : {liner}')
if datas[i] == n:
resultIndex = i
break
if resultIndex != -1:
print(f'resultIndex = {resultIndex}')
else:
print(f'{n} 데이터 찾기 실패')
💡result
찾으려는 숫자 입력 : 8
1 : [3]
2 : [3, 2]
3 : [3, 2, 5]
4 : [3, 2, 5, 7]
5 : [3, 2, 5, 7, 9]
6 : [3, 2, 5, 7, 9, 1]
7 : [3, 2, 5, 7, 9, 1, 0]
8 : [3, 2, 5, 7, 9, 1, 0, 8]
resultIndex = 7
보초법
마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
n = int(input('찾으려는 숫자 입력 : '))
resultIndex = -1
datas.append(n)
for i in range(len(datas)):
if datas[i] == n and i != len(datas) - 1:
resultIndex = i
break✍️실습
리스트에서 가장 앞에있는 숫자 '7'을 검색하고 위치 출력
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
index = -1
for idx, num in enumerate(nums):
if num == 7:
index = idx
break
if index != -1:
print(f'7의 위치 : {index}')
else:
print(f'리스트안에 7이 존재하지 않습니다.')
리스트에서 숫자 '7'을 모두 검색하고 각각의 위치 출력
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
index = []
for idx, num in enumerate(nums):
if num == 7:
index.append(idx)
if len(index) != 0:
print(f'7의 개수 : {len(index)}')
else:
print(f'리스트안에 7이 존재하지 않습니다.')
✒️이진검색 이란?
정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
searchData = int(input('찾으려는 숫자 입력 : '))
searchIndex = -1
staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
while True:
print(f'{datas[staIdx:endIdx + 1]}')
if searchData > midVal:
print(f'searchData > midVal')
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
elif searchData < midVal:
print(f'searchData < midVal')
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
else:
print(f'searchData == midVal')
searchIndex = midIdx
break
찾으려는 숫자 입력 : 9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
searchData > midVal
[6, 7, 8, 9, 10, 11]
searchData > midVal
[8, 9, 10, 11]
searchData == midVal
✍️실습
리스트를 오름차순으로 정렬한 후 '7'을 검색하고 위치를 출력하자
while True if searchData in nums else print(f'{searchData}는 리스트에 존재하지 않는 값입니다.'):
print(f'{nums[staIdx:endIdx + 1]}')
if searchData < midValue:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midValue = nums[midIdx]
elif searchData > midValue:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midValue = nums[midIdx]
else:
print(f'searchData == midVal')
print(f'midIdx = {midIdx}')
searchIndex = midIdx
break
리스트 원본 : [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
리스트 정렬: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
찾으려는 숫자 입력 : 17
[0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
[10, 11, 17, 22, 61, 88]
searchData == midVal
midIdx = 7
------------------------------------------------------------
리스트 원본 : [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
리스트 정렬: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
찾으려는 숫자 입력 : 99
99는 리스트에 존재하지 않는 값입니다.✒️ 순위 란?
수의 크고 작음을 이용해서 수의 순서를 정하는것을 순위라고 한다.
import random
nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]
print(nums)
print(ranks)
for idx, num1 in enumerate(nums):
for num2 in nums:
if num1 < num2:
ranks[idx] += 1
print(nums)
print(ranks)
for idx, num in enumerate(ranks):
print(f'num {nums[idx]} : {num+1} 위')
[78, 65, 56, 86, 79, 83, 91, 95, 90, 66, 80, 89, 77, 71, 98, 51, 84, 74, 63, 100]
[11, 16, 18, 6, 10, 8, 3, 2, 4, 15, 9, 5, 12, 14, 1, 19, 7, 13, 17, 0]
num 78 : 12 위
num 65 : 17 위
num 56 : 19 위
num 86 : 7 위
num 79 : 11 위
num 83 : 9 위
num 91 : 4 위
num 95 : 3 위
num 90 : 5 위
num 66 : 16 위
num 80 : 10 위
num 89 : 6 위
num 77 : 13 위
num 71 : 15 위
num 98 : 2 위
num 51 : 20 위
num 84 : 8 위
num 74 : 14 위
num 63 : 18 위
num 100 : 1 위
✍️실습
학급학생(20명)중간고사와 기말고사 성적을 이용해서 각각의 수위를 구하고, 중간고사 대비 기말고사 순의 변화(편차)를 출력하는 프로그램(시험성적은 난수이용)
# 학급학생(20명)중간고사와 기말고사 성적을 이용해서 각각의 수위를 구하고,
# 중간고사 대비 기말고사 순의 변화(편차)를 출력하는 프로그램(시험성적은 난수이용)
import random
midScores = random.sample(range(50, 101), 20)
endScores = random.sample(range(50, 101), 20)
midRanks = [0 for i in range(20)]
endRanks = [0 for j in range(20)]
for idx, score1 in enumerate(midScores):
for score2 in midScores:
if score1 < score2:
midRanks[idx] += 1
for idx, score1 in enumerate(endScores):
for score2 in endScores:
if score1 < score2:
endRanks[idx] += 1
for i in range(20):
deviation = midRanks[i] - endRanks[i]
if deviation > 0:
dev = f'🔼{deviation}'
elif deviation < 0:
dev = f'🔽{deviation * -1}'
else:
dev = f'️⏹️️️{deviation}'
print(f'Score - mid : {midScores[i]} , end : {endScores[i]} -> RANK - mid : {midRanks[i]}, end : {endRanks[i]}, \tDeviation : {dev}')
Score - mid : 68 , end : 68 -> RANK - mid : 12, end : 12, Deviation : ️⏹️️️0
Score - mid : 97 , end : 95 -> RANK - mid : 1, end : 1, Deviation : ️⏹️️️0
Score - mid : 60 , end : 80 -> RANK - mid : 16, end : 9, Deviation : 🔼7
Score - mid : 93 , end : 50 -> RANK - mid : 2, end : 19, Deviation : 🔽17
Score - mid : 72 , end : 85 -> RANK - mid : 10, end : 6, Deviation : 🔼4
Score - mid : 55 , end : 86 -> RANK - mid : 17, end : 5, Deviation : 🔼12
Score - mid : 90 , end : 73 -> RANK - mid : 3, end : 10, Deviation : 🔽7
Score - mid : 62 , end : 91 -> RANK - mid : 14, end : 3, Deviation : 🔼11
Score - mid : 61 , end : 65 -> RANK - mid : 15, end : 14, Deviation : 🔼1
Score - mid : 100 , end : 96 -> RANK - mid : 0, end : 0, Deviation : ️⏹️️️0
Score - mid : 52 , end : 72 -> RANK - mid : 19, end : 11, Deviation : 🔼8
Score - mid : 88 , end : 84 -> RANK - mid : 5, end : 7, Deviation : 🔽2
Score - mid : 54 , end : 60 -> RANK - mid : 18, end : 16, Deviation : 🔼2
Score - mid : 63 , end : 93 -> RANK - mid : 13, end : 2, Deviation : 🔼11
Score - mid : 89 , end : 67 -> RANK - mid : 4, end : 13, Deviation : 🔽9
Score - mid : 73 , end : 55 -> RANK - mid : 9, end : 17, Deviation : 🔽8
Score - mid : 77 , end : 81 -> RANK - mid : 7, end : 8, Deviation : 🔽1
Score - mid : 86 , end : 63 -> RANK - mid : 6, end : 15, Deviation : 🔽9
Score - mid : 74 , end : 54 -> RANK - mid : 8, end : 18, Deviation : 🔽10
Score - mid : 70 , end : 90 -> RANK - mid : 11, end : 4, Deviation : 🔼7
개발하고싶은사람