검색 알고리즘
선형검색 문제
숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어보라.
1. 검색 모듈은 선형 검색 알고리즘을 사용
2. 리스트는 1부터 20까지의 정수 중에서 난수 10개 이용
3. 검색 과정은 로그로 출력
4. 검색에 성공하면 해당 정수의 인덱스를 출력하고 검색 결과가 없다면 -1 출력<내 풀이>
mport random
thelist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
numbers = random.sample(thelist, 10)
#randint로 하면 어떻게 하나? 반복문을 돌리면 중복된 값이 나오잖아. 영상에서는 어떻게 풀려나
resultIdx = -1
target = int(input('찾으려는 숫자 입력 : '))
print('리스트 값 : {}'.format(numbers))
#검색과정을 로그로 출력 : 로그를 남기는 이유는 디버깅을 위해, 모든 소스 코드의 오류 또는 버그를 찾아서 수정하는 과정
if target in numbers:
#resultIdx = #인덱스로 값을 찾는 방법은 알겠는데, 값으로 인덱스를 찾는 방법은 모르겠네
print(f'Search Number : {target}')
print('Search SUCEESS!')
#print('Search result INDEX : {}'.format(pass))
else:
print(resultIdx)
-- result
찾으려는 숫자 입력 : 3
리스트 값 : [7, 20, 10, 12, 16, 11, 8, 6, 3, 15]
Search Number : 3
Search SUCEESS!
❓값으로 인덱스 위치를 찾는 방법을 풀지 못함
<영상 풀이>
모듈 lineMod
def searchNumberByLineAl(ns, sn): #ns : 받을 숫자 ,sn : 찾으려는 숫자
searchResultIdx = -1
print(f'Numbers : {ns}')
print(f'Search Numbers : {sn}')
n = 0
while True:
if n == len(ns):
print('Search Fail')
break
if ns(n) == sn:
searchResultIdx = n
print('Search Suceess')
print(f'Search result Index : {searchResultIdx}')
break
n+=1
return searchResultIdx
✏️ in/not in 을 쓰려고 하니까 인덱스 값을 불러올 수 없었던 것, 하나하나 비교할 수 있게 while 문을 돌려서 대조해보는 것이 인덱스를 구할 수 있는 방법!
실행
import lineMod
import random
if __name__ = '__init__':
rNums = random.sample(range(1,21), 10) #내가 고민했던 지점을 한번에 풀어냄
searchNums = int(input('input search number : '))
resultIdx = searchNumberByLineAl(rNums, searchNum)
if resultIdx == -1:
print('No result found')
print(f'search result Index : {resultIdx}')
else:
print('>>> Search Result <<<')
print(f'search result index : {resultIdx}')
print(f'search result number : {rNums[resultIdx]}')✏️ random에서 sample을 써야할 지, randint를 써야할 지 고민했는데, range(1,21)을 하면 굳이 리스트에 숫자를 다 넣을 필요없이 sample로 해결할 수 있다:)
이진검색 문제
숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어라
1. 검색 모듈은 이진 검색 알고리즘을 이용
2. 리스트는 [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28] 를 이용
3. 검색 과정을 로그로 출력
4. 검색에 성공하면 해당 정수의 인덱스를 출력하고 검색 결과가 없다면 -1 출력<내 풀이>
모듈
def SearchAl(thelist, target):
searchResultIdx = -1
print(f'Numbers : {thelist}')
print(f'Search Numbers : {target}')
lowIdx = 0; highIdx = len(thelist)
while True:
midIdx = int((lowIdx + highIdx) / 2)
midNums = thelist[midIdx]
print(f'startIdx : {lowIdx}, endIdx : {highIdx}')
print(f'midIdx : {midIdx}, midVal : {midNums}')
if target == midNums:
searchResultIdx = midIdx
print('>>Search Success')
break
if target < midNums:
highIdx = midIdx
print(f'-startIdx : {lowIdx}, endIdx : {highIdx}')
continue
if target > midNums:
lowIdx = midIdx
print(f'+startIdx : {lowIdx}, endIdx : {highIdx}')
continue
return searchResultIdx
실행
import module1009 as md
if __name__ == '__main__':
thelist = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
target = int(input('input search number : '))
resultIdx = md.SearchAl(thelist, target)
if resultIdx == -1:
print('No result Found')
else:
print('Search Success')
❓결과 값이 출력되지 않음 >> __init__를 __main__으로 변경하니 풀림
-- result
input search number : 27
Numbers : [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
Search Numbers : 27
startIdx : 0, endIdx : 18
midIdx : 9, midVal : 15
+startIdx : 9, endIdx : 18
startIdx : 9, endIdx : 18
midIdx : 13, midVal : 21
+startIdx : 13, endIdx : 18
startIdx : 13, endIdx : 18
midIdx : 15, midVal : 24
+startIdx : 15, endIdx : 18
startIdx : 15, endIdx : 18
midIdx : 16, midVal : 27
>>Search Success
Search Success
<영상 풀이>
모듈
def SearchAl(ns, sn):
searchResultIdx = -1
print(f'Numbers : {ns}')
print(f'Search Numbers : {sn}')
lowIdx = 0; highIdx = len(ns) - 1 # 하나 뺴줘야 한다.
midIdx = int((lowIdx + highIdx) // 2) # 몫으로 구해야 함
midNums = ns[midIdx]
print(f'staIdx : {lowIdx}, endIdx : {highIdx}')
print(f'midIdx : {midIdx}, midVal : {midNums}')
while sn >= ns[0] and sn <= ns[len(ns) - 1]: #이 밖의 값이면 필요가 없으니까!
if sn == ns[len(ns) -1 ]: #맨 마지막 값이 동일한 경우
searchResultIdx = len(ns) - 1
print('>>Search Success')
break
if lowIdx + 1 == highIdx: #무한 반복을 막기 위해 추가한 내용!
if ns[lowIdx] != sn and ns[highIdx] !=sn:
break
if sn < midNums:
highIdx = midIdx
midIdx = (lowIdx + highIdx) // 2
midNums = ns[midIdx]
print(f'-staIdx : {lowIdx}, endIdx : {highIdx}')
print(f'-midIdx : {midIdx}, midVal : {midNums}')
continue
elif sn > midNums:
lowIdx = midIdx
midIdx = (lowIdx + highIdx) // 2 #나는 조건문 안에 넣어서 계속 되풀이해서 적지 않게 했다
midNums = ns[midIdx]
print(f'+staIdx : {lowIdx}, endIdx : {highIdx}')
print(f'+midIdx : {midIdx}, midVal : {midNums}')
continue
elif sn == midNums:
searchResultIdx = midIdx
break
return searchResultIdx
실행
import module1009 as md
if __name__ == '__main__':
thelist = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
target = int(input('input search number : '))
resultIdx = md.SearchAl(thelist, target)
if resultIdx == -1:
print('No result Found')
else:
print('Search Success')
--result
input search number : 24
Numbers : [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
Search Numbers : 24
staIdx : 0, endIdx : 17
midIdx : 8, midVal : 13
+staIdx : 8, endIdx : 17
+midIdx : 12, midVal : 20
+staIdx : 12, endIdx : 17
+midIdx : 14, midVal : 23
+staIdx : 14, endIdx : 17
+midIdx : 15, midVal : 24
Search Success
🤔 디테일한 부분에서 놓친 게 있음
1) 나눗셈이 아닌 몫을 구해야 함
2) len 에서 -1 을 해줘야 맨 마지막 인덱스가 나온다구
3) while True가 아니라 밖의 숫자를 입력할 경우 제한할 수 있도록 조건문을 만들어줘야 하고, 사잇값을 넣었을 때 무한반복되지 않는 장치를 추가해야함
잘한 부분 >> 이진검색을 사용하는 매커니즘은 이해하고 생각해 냄
순위 알고리즘
숫자로 이루어진 리스트에서 아이템의 순위를 출력하고, 순위에 따라 아이템을 정렬하는 모듈을 만들어보자, 리스트는 50부터 100까지의 난수 20개를 이용하자.
<내 시도>
class rankAlgorithm:
def __init__(self): #생성자
self.thelist = lt
#lt가 주어지지 않았는데 어떻게 생성자에서 자동으로 불러오지? class에 매개변수를 넣어도 되나?
self.ranks = [0 for i in range(len(lt))]#list comprehension 이게 맞는 코드인가?
def itemRank(self,lt):
#숫자를 서로 비교해서 더 작은 숫자이면 ranks 리스트 값을 플러스하는 것
for idx, val in enumerate(lt):
if lt[idx] >
def sortedRank(self, lt):
pass
🤔 매개변수를 받아야 하니까 def로 진행
모듈
#순위 출력
def rankAlgorithm(ns):
ranks = [0 for i in range(len(ns))] #내가 쓴 것과 일치함
for idx, n1 in enumerate(ns):
for n2 in ns: #이렇게 쉽게 생각할 수 있군~
if n1 < n2:
ranks[idx] +=1 #다 돌아가면서 하니까 자기 차례일 때만 +1 진행
print(f'nums: {ns}')
print(f'ranks: {ranks}')
#정렬 파트
for i, n in enumerate(ns):
print(f'num: {n} \t rank : {ranks[i] + 1}')
sortedNums = [0 for i in range(len(ns))] #새 리스트를 만들고
for idx, rank in enumerate(ranks):
sortedNums[rank] = ns[idx] #값을 씌워서 새로운 리스트 만들기, rank 값이 1이면 sortedNums의 idx 1번 자리에 rank 1위인 값의 위치를 idx로 알수 있고 그에 따라 원 list의 idx로 자리 지정~
return sortredNums실행
import random
import module1009 as md
if __name__ = '__main__':
nums = random.sample(range(50, 101), 20)
sNums = md.rankAlgorithm(nums)
print(f'sNums : {sNums}')순위 알고리즘2
알파벳 문자들과 정수들에 대한 순위를 정하는 프로그램을 순위 알고리즘을 이용해 만들어보자, 단 알파벳은 아스키 코드값을 이용한다
[32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
🤔 아스키 코드 생소해,,,
아스키 코드 숫자로 모두 바꾼 후 -> 순위를 매기는 방식으로 진행
ord() : 아스키코드 값으로 바꾸는 함수
<영상 풀이>
#아스키 코드로 변환
datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
print(f'datas : {datas}')
ascIIDatas = []
for data in datas:
if str(data).isalpha(): #문자면 True, 아스키코드로 변환하게, 숫자도 있어서 str()를 씌움
ascIIdatas.append(ord(data))
continue
ascIIDatas.append(data)
print(f'ascIIDatas:{ascIIDatas}')
#순위 매기기
ranks = [0 for i in range(len(ascIIDatas))]
print(f'ranks before : {ranks}')
for idx, data1 in enumerate(ascIIDatas):
for data2 in ascIIDatas:
if data1 < data2:
ranks[idx] += 1
print(f'ranks after : {ranks}')
for i, d in enumerate(datas):
print(f'data : {d} \t rank : {ranks[i] + 1}')🤔 어렵게 생각하지 않기!
데이터로 경로를 탐색합니다.