알고리즘
알고리즘이란 ?
어떠한 문제를 풀어내기 위한 일련의 절차나 방법을 공식화 한것.
알고리즘_검색
1. 선형검색
선형으로 나열되어있는 데이터를 순차적(인덱스0부터)으로 스캔하면서 원하는 값을 검색
데이터[idx]값이 search_num과 동일 할 때,
idx값으로 데이터 위치를 알 수 있다.
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas : {datas}')
print(f'datas length : {len(datas)}')
# datas : [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
# datas length : 10
search_data = int(input('찾으려는 숫자입력 : '))
search_idx = -1 #존재하지않는 임의의idx번호 부여
n = 0
while True :
if n == len(datas) :
search_idx = -1
break
elif datas[n] == search_data :
search_idx = n
break
n += 1
print(f'{search_data}의 idx번호 : {search_idx}')➕보초법
마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas : {datas}')
print(f'datas length : {len(datas)}')
# datas : [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
# datas length : 10
search_data = int(input('찾으려는 숫자입력 : '))
search_idx = -1 #존재하지않는 임의의idx번호 부여
datas.append(search_data) #마지막에 추가
n = 0
while True :
if datas[n] == search_data : #데이터값이 찾는 데이터와 동일하고
if n != len(datas) -1 : #그 데이터가 임의로 집어넣은 값이 아니라면
search_idx = n #idx번호는n
break
n+=1
print(f'{search_data}의 idx번호 : {search_idx}')📁 실습
리스트에서 입력한 숫자를 모두 검색하고 각각의 위치와 검색갯수를 출력
nums = [4,7,10,2,4,7,0,2,7,3,9]
search_num = int(input('찾으려는 숫자 입력 : '))
nums.append(search_num)
search_idx_list = []
n = 0
while True :
if search_num == nums[n] :
if n != len(nums)-1 :
search_idx_list.append(n)
else :
break
n += 1
if search_idx < 0 :
print('not search index')
else :
print(f'search_idx : {idx_list}')
print(f'idx 개수는 총 : {idx_sum}')위 내용을 함수화 시킨다면,
def search_idx_function(list):
search_num = int(input('input search number : '))
list.append(search_num)
n = 0
idx_list = []
while True :
if list[n] == search_num :
if n != len(list)-1 :
idx_list.append(n)
else :
break
n += 1
return idx_list
result = search_idx_function(nums)
print(f'search idx list : {result}')2. 이진검색
정렬되어있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색
datas = [1,2,3,4,5,6,7,8,9,10,11]
search_num = int(input('찾으려는 숫자 입력 : '))
search_idx = -1
start_idx = 0
end_idx = len(datas) - 1
mid_idx = (start_idx + end_idx) // 2
mid_value = datas[mid_idx]
while search_num >= datas[0] and search_num <= datas[len(datas)-1]:
#정렬되어있으므로 위처럼 코딩 시 인덱스범위내에서만 while문이 돌아간다.
if search_num > mid_value :
start_idx = mid_idx
mid_idx = (start_idx+end_idx) // 2
mid_value = datas[mid_idx]
elif search_num < mid_value :
end_idx = mid_value
mid_idx = (start_idx+end_idx) // 2
mid_value = datas[mid_idx]
elif search_num == mid_value :
search_idx = mid_idx
break
print(f'{search_num}의 idx값 : {search_idx}')
📁 실습
리스트를 오름차순으로 정렬한 후 입력한 수의 위치를 출력하자
nums = [4,10,22,5,0,17,7,11,9,61,88]
#오름차순정렬
nums.sort()
#찾을 수 input
search_num = int(input('찾으려는 숫자 입력 : '))
start_idx = 0
end_idx = len(nums) -1
mid_idx = (start_idx + end_idx) // 2
mid_value = nums[mid_idx]
search_idx = -1
while search_num in nums :
if search_num < mid_value :
end_idx = mid_idx
mid_idx = (start_idx + end_idx) // 2
mid_value = nums[mid_idx]
elif search_num > mid_value :
start_idx = mid_idx
mid_idx = (start_idx + end_idx) // 2
mid_value = nums[mid_idx]
elif search_num == mid_value :
search_idx = mid_idx
break
print(f'찾으려는 숫자 : {search_num}')
if search_idx < 0 :
print('not search idx')
else :
print(f'찾으려는 숫자의 idx : {search_idx}')위 내용을 함수화 시킨다면,
def search_num(list) :
list.sort()
print(f'list 정렬 : {list}')
print(f'list length : {len(list)}')
search_num = int(input('찾으려는 숫자입력 : '))
search_idx = -1
start_idx = 0
end_idx = len(list) -1
mid_idx = (start_idx+end_idx)//2
mid_val = list[mid_idx]
while search_num in list :
if search_num > mid_val :
start_idx = mid_idx
mid_idx = (start_idx + end_idx) // 2
mid_val = list[mid_idx]
elif search_num < mid_val :
end_idx = mid_idx
mid_idx = (start_idx + end_idx) // 2
mid_val = list[mid_idx]
elif search_num == mid_val :
search_idx = mid_idx
break
if search_idx < 0 :
return 'not search idx'
else :
return search_idx
nums = [4,10,22,5,0,17,7,11,9,61,88]
idx = search_num(nums)
print(idx)알고리즘_순위
수의 크고작음을 이용해서 수의 순서를 정하는 것
import random
nums = random.sample(range(50,101),20) #50부터 100까지 중 20개의 수 랜덤 샘플링
ranks = [0 for i in range(20)] #0 20개 반복 (nums의 idx수와 ranks의 idx수 동일)
print(nums)
print(ranks)
for idx, num in enumerate(nums):
for i in nums:
if num < i : #큰값부터 0 ~
ranks[idx] += 1 #num이 i보다 작다면 ranks의 동일idx위치에 +1
print(nums)
print(ranks)
for idx,num in enumerate(nums) :
print(f'num : {num}\t rank : {ranks[idx]+1}') #idx는 0부터 시작하고 순위는 1부터이므로 +1📁 실습
학급학생(20명)들의 중간고사와 기말고사 성적을 이용해서 각각의 순위를 구하고,
중간고사 대비 기말고사 순위 변화를 출력하는 프로그램을 만들어보자
import random
mid_scores = random.sample(range(0,101),20) #20개의 중간고사 점수 샘플링
end_scores = random.sample(range(0,101),20) #20개의 기말고사 점수 샘플링
mid_rank = [0 for i in range(20)]
end_rank = [0 for i in range(20)]
diviation = [0 for i in range(20)]
#중간고사 rank
for idx, score in enumerate(mid_scores) :
for i in mid_scores :
if score < i :
mid_rank[idx] += 1
print(f'mid score : {mid_scores}')
print(f'mid rank : {mid_rank}')
#기말고사 rank
for idx, score in enumerate(end_scores) :
for i in end_scores :
if score < i :
end_rank[idx] += 1
print(f'end score : {end_scores}')
print(f'end rank : {end_rank}')
for idx in range(20) :
diviation[idx] = mid_rank[idx] - end_rank[idx]
if diviation[idx] > 0:
diviation[idx] = '↑' + str(abs(diviation[idx]))
elif diviation[idx] < 0:
diviation[idx] = '↓' + str(abs(diviation[idx]))
elif diviation[idx] == 0:
diviation[idx] = '=' + str(abs(diviation[idx]))
print(f'mid rank : {mid_rank[idx]}\tend rank : {end_rank[idx]}\t deviation : {diviation[idx]}')위 내용을 함수화 시킨다면,
import random
def exam_div(mids,ends) :
mid_rank = [0 for i in range(len(mids))]
end_rank = [0 for i in range(len(ends))]
#중간고사rank
for idx, score1 in enumerate(mids):
for score2 in mids :
if score1 < score2 : #큰 점수가 0 작은점수가 +=1
mid_rank[idx] += 1
# print(f'mid_score : {mid_scores}')
# print(f'mid_rank : {mid_rank}')
#기말고사 rank
for idx, score1 in enumerate(ends):
for score2 in ends :
if score1 < score2 : #큰 점수가 0 작은점수가 +=1
end_rank[idx] += 1
# print(f'end_scores : {end_scores}')
# print(f'end_rank : {end_rank}')
dev = [0 for i in range(len(mids))]
for i in range(20) :
dev[i] = mid_rank[i] - end_rank[i]
if dev[i] > 0 :
deviation = '↑'+str(abs(dev[i]))
elif dev[i] < 0 :
deviation = '↓'+str(abs(dev[i]))
elif dev[i] == 0 :
deviation = '=0'
print(f'mid_rank : {mid_rank[i]}\tend_rand : {end_rank[i]}\tDeviation : {deviation}')
mid_scores = random.sample(range(0,101),20)
end_scores = random.sample(range(0,101),20)
exam_div(mid_scores,end_scores)클래스화 시킨다면
class Rank_Deviation:
def __init__(self,mid_list,end_list):
self.mid_score = mid_list
self.end_score = end_list
self.mid_rank = [0 for i in range(len(mid_list))]
self.end_rank = [0 for i in range(len(end_list))]
self.deviation = [0 for i in range(len(mid_list))]
def set_rank(self,list,ranks):
for idx, sco1 in enumerate(list):
for sco2 in list :
if sco1 < sco2 :
ranks[idx] += 1
def set_mid_rank(self):
self.set_rank(self.mid_score,self.mid_rank)
def get_mid_rank(self):
return self.set_mid_rank()
def set_end_rank(self):
self.set_rank(self.end_score,self.end_rank)
def get_end_rank(self):
return self.set_end_rank()
def print_deviation(self):
for idx in range(len(mid_scores)) :
self.deviation[idx] = self.mid_rank[idx] - self.end_rank[idx]
if self.deviation[idx] > 0:
self.deviation[idx] = '↑' + str(abs(self.deviation[idx]))
elif self.deviation[idx] < 0:
self.deviation[idx] = '↓' + str(abs(self.deviation[idx]))
elif self.deviation[idx] == 0:
self.deviation[idx] = '=0'
print(f'mid_rank : {self.mid_rank[idx]}\tend_rank : {self.end_rank[idx]}\tdeviation : {self.deviation[idx]}')
import random
mid_scores = random.sample(range(0,101),20)
end_scores = random.sample(range(0,101),20)
exam = Rank_Deviation(mid_scores,end_scores)
exam.get_mid_rank()
exam.get_end_rank()
print(f'mid_score : {exam.mid_score}')
print(f'mid_rank : {exam.mid_rank}')
print(f'end_score : {exam.end_score}')
print(f'end_rank : {exam.end_rank}')
exam.print_deviation()제로베이스 데이터취업스쿨
Daily Study Note
Study Log