⬇️ [알고리즘] 검색, 순위 이론
선형검색
📖 문제
숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음요건에 따라 만들어보자
- 검색모듈은 선형검색 알고리즘을 이용하자
- 리스트는 1부터 20까지의 정수중에서 난수 10개를 이용하자
- 검색과정을 로그로 출력하자
- 검색에 성공하면 해당정수의 인덱스를 출력하고, 검색결과가 없다면 -1을 출력하자.
#모듈명 : linemod
def search(list,search_num) :
print(f'list : [{list}]')
print(f'search_num : {search_num}')
search_idx = -1
n = 0
while True :
if n == len(list) :
print('Search Fail')
break
if list[n] == search_num :
search_idx = n
print('Search Success!')
print(f'search_idx : {search_idx}')
break
n += 1
return search_idx#실행파일
import linemod
import random
if __name__ == '__main__' :
list = random.sample(range(1, 21), 10)
search_num = int(input('search num input : '))
result_idx = linemod.search(list,search_num)
if result_idx == -1 :
print('search num is not in list')
else :
print('>>> Search Results <<<')
print(f'search result index : {result_idx}')
print(f'search result num : {search_num}')📁 풀이기록
보초법을 사용하지 않고
while문으로 n(=idx)을 1씩 더하면서 순차적으로 검색하는 이진검색 모듈을 생성한 후
실행파일에서 idx가 -1이 아닐 경우 result를 출력하게끔 하였다.
아직 모듈에 print구문이 어디까지 들어가야하는지 애매한데,
실제 사용하는 모듈이라면 모듈 내 print 구문이 아예 없는것이 실용적일것 같다.
다만, 이 문제의 경우 로그를 출력하라고 하였으므로
모듈 내 print 코드를 넣어두었다.
이진검색
📖 문제
숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음요건에 따라 만들어보자
- 검색모듈은 이진검색 알고리즘을 이용하자
- 리스트는 [1,2,4,6,7,8,10,11,13,15,16,17,20,21,23,24,27,28]를 이용하자
- 검색과정을 로그로 출력하자
- 검색에 성공하면 해당정수의 인덱스를 출력하고 검색결과가 없다면 -1을 출력하자
#모듈명 : binarymod
def search_binarymod(list, search_num) :
search_idx = -1
start_idx = 0
end_idx = len(list) -1
mid_idx = (start_idx+end_idx) // 2
mid_value = list[mid_idx]
# log
print(f'start idx : {start_idx},\tend_idx : {end_idx}')
print(f'mid_idx ; {mid_idx},\tmid_value : {mid_value}')
while search_num in list :
if search_num < mid_value :
end_idx = mid_idx
mid_idx = (start_idx + end_idx) // 2
mid_value = list[mid_idx]
#log
print(f'-start idx : {start_idx},\tend_idx : {end_idx}')
print(f'-mid_idx ; {mid_idx},\tmid_value : {mid_value}')
elif search_num > mid_value :
start_idx = mid_idx
mid_idx = (start_idx + end_idx) // 2
mid_value = list[mid_idx]
# log
print(f'+start idx : +{start_idx},\tend_idx : {end_idx}')
print(f'+mid_idx ; +{mid_idx},\tmid_value : {mid_value}')
elif search_num == mid_value :
search_idx = mid_idx
break
return search_idx#실행파일
import binarymod
list = [1,2,4,6,7,8,10,11,13,15,16,17,20,21,23,24,27,28]
if __name__ == '__main__' :
search_num = int(input('input search num : '))
result_idx = binarymod.search_binarymod(list,search_num)
if result_idx == -1 :
print('Search Fail')
print(f'idx : {result_idx}')
print(f'search num : {search_num}')
else :
print('>>> Search Results <<<')
print(f'search result index : {result_idx}')
print(f'search result num : {search_num}')
📁 풀이기록
중앙값을 이용한 이진검색을
binarymod 모듈 내 search_binarymod 함수에 넣어주고
idx값을 return해주었다.
만약 리스트가 정렬되어있지 않다면
모듈에 list.sort()를 추가해주어야 한다.
순위
📖 문제_1
숫자로 이루어진 리스트에서 아이템 순위를 출력하고,
순위에 따라 아이템을 정렬하는 모듈을 만들어보자.
리스트는 50부터 100까지의 난수를 20개 이용하자.
#rank모듈
def sorted_rank(list) :
ranks = [0 for i in range(len(list))]
sorted_list = [0 for i in range(len(list))]
for idx, nums in enumerate(list):
for nums2 in list:
if nums < nums2 :
ranks[idx] += 1
for idx, rank in enumerate(ranks):
sorted_list[rank] = list[idx]
return ranks, sorted_list#실행파일
import random
nums = random.sample(range(50,101),20)
print(f'nums : {nums}')
import rank
ranks, sorted_list = rank.sorted_rank(nums)
print(f'rank : {ranks}')
print(f'sorted_list : {sorted_list}')📁 풀이기록
list를 넣으면 rank와 정렬된 리스트가 출력되는
sorted_rank 모듈을 만들었다.
sorted_list의 경우,
rank에서 idx와 value를 추출했을 때
sorted_list[rank]에 list[idx]를 넣으면 정렬된 리스트를 추출 할 수 있다.
📖 문제_2
알파벳 문자들과 정수들에 대한 순위를 정하는 프로그램을 순위알고리즘을 이용해 만들어보자.
단, 알파벳은 아스키코드 값을 이용한다.
#rank모듈
def rank_num_alpabet(list) :
ranks = [0 for i in range(len(list))]
ascii_list = [0 for i in range(len(list))]
for idx, value in enumerate(list) :
if isinstance(value,str):
ascii_list[idx] = ord(value)
else :
ascii_list[idx] = value
for idx, value in enumerate(ascii_list):
for value2 in ascii_list :
if value < value2 :
ranks[idx] += 1
print(f'datas : {list}')
print(f'ascii_datas : {ascii_list}')
print(f'ranks : {ranks}')
n = 0
while True:
if n > len(list)-1 :
break
print(f'data : {list[n]}\trank : {ranks[n]+1}')
n += 1
#실행파일
list = [32,'a','z',45,'G',39,50,'T','t',22,31,55,'s',63,59,'E']
import rank
rank.rank_num_alpabet(list)📁 풀이기록
rank_num_alpabet 모듈에 list를 넣으면
list의 idx과 value를 뽑아,
isinstance 함수를 활용해 value가 str이면 ord()로 숫자로 변경하여 ascii_list의 idx자리에 넣어주고,
int면 그대로 집어넣어 list의 알파벳을 숫자로 바꿔주는 ascii_list를 만든 후 rank를 생성해준다.
자료구조만 잘 이해했다면 크게 어려운 문제는 아니었다.
Zero Base 데이터분석 스쿨
Daily Study Note
