17. 알고리즘_1

• 선형검색

  • 선형검색: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값 찾음
  • 보초법: 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정

#선형검색 

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIndex = -1 

n = 0
while True:

    if n == len(datas):
      searchResultIndex = -1 
      break
    
    elif datas[n] == searchData:
         searchResultIndex = n
         break
    n += 1
    
print(f'searchResultIndex: [{searchResultIndex}]')
#결과값이 [-1]이면, 주어진 데이터 안에 찾는 데이터가 없다는 뜻

---

 #보초법     
 
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'data length: {len(datas)}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIndex = -1

datas.append(searchData)

n = 0
while True:

    if datas[n] == searchData:
       if n != len(datas) -1:
           searchResultIndex = n
           break
           
     n += 1

 print(f'datas: {datas}')
 print(f'datas length: {len(datas)}')
 print(f'searchResultIndex: [{searchResultIndex}]')

---

Q. 리스트에서 가장 앞에 있는 숫자 7을 검색하고 위치(인덱스) 출력 

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIndex = -1

nums.append(searchData)

n = 0
while True:

    if nums[n] == searchData:
        if n != len(nums) -1:
           searchResultIndex = n
           break
           
    n += 1
    
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIndex: [{searchResultIndex}]')

if searchResultIndex < 0:
     print('찾지 못함')  
     
else:
    print(f'searchIndex: [{searchResultIndex}]')  

---

Q. 리스트에서 숫자 7을 모두 검색하고 각가의 위치(인덱스)와 검색 개수 출력

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

def searchNumber(n):
    searchNumber = int(input('숫자 입력: '))

    searchResultIndex = []
    nums.append(searchNumber)
    
    n = 0
    while True:
        if nums[n] == searchNumber:
            if n != len(nums) -1:
                searchResultIndex.append(n)
            else:
                break
       n += 1
   return searchResultIndex

print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIndex: {searchNumber(searchNumber)}')
print(f'searchResultIndex length: {len(searchNumber(searchNumber))}')
            

---

• 이진검색

  • 이진검색: 정렬되어 있는 자료구조에서 중앙값과 크고 작음을 이용해서 데이터 검색
  • 이진검색을 사용할 경우 데이터가 미리 정렬되어 있어야 함

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('찾으려는 숫자: '))
searchResultIndex = -1

staIndex = 0
endIndex = len(datas) -1
midIndex = (staIndex + endIndex) // 2
midval = datas[midIndex]

print(f'midIndex: {midIndex}')
print(f'midval: {midval}')

while searchData <= datas[len(datas)-1] and searchData >= datas[0]:

     if searchData == datas[len(datas)-1]:
         searchResultIndex = len(datas)-1
         break
         
     if searchData > midval:
          staIndex = midIndex
          midIndex = (staIndex + endIndex) // 2
          midval = datas[midIndex]
          print(f'midIndex: {midIndex}')
          print(f'midval: {midval}')
          
     elif searchData < midval:
          endIndex = midIndex
          midIndex= (staIndex + endIndex) // 2
          midval = datas[midIndex]
          print(f'midIndex: {midIndex}')
          print(f'midval: {midval}')

     elif searchData == midval:
        searchResultIndex = midIndex
        break
        
print(f'searchResultIndex: {searchResultIndex}')        

---

• 순위
  • 순위: 수의 크고 작음을 이용해서 수의 순서를 정함

import random

nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]
print(f'ranks: {ranks}')

for idx, num1 in enumerate(nums):
    for num2 in nums:
        if num1 < num2:
            ranks[idx] += 1

print(f'nums: {nums}')
print(f'ranks: {ranks}')

for idx, num in enumerate(nums):
     print(f'num: {num} \t rank: {ranks[idx] +1}')

---

Q. 학습 학생(20명) 중간/기말 성적 이용해서 각가의 순위, 중간고사 대비 기말고사 순위변화(편차) 출력(시험 성적은 난수 이용) 

 <rankMod 모듈>
 
 class RankDeviation: 
  
    def__init__(self, mss, ess):
       self. midsStuScos = mss
       self.endStuScos = ess
       self.midRanks = [0 for i in range(len(mss))]
       self.endRanks = [0 for i in range(len(mss))]
       self.rankDeviation = [0 for i in range(len(mss))]

    def setRank(self, ss, rs):
        for idx, sco1 in enumerate(ss):
            for sco2 in ss:
                if sco1 < sco2:
                   rs[idx] += 1
                   
    def setMidRank(self):
        self.setRank(self.midsStuScos, self.midRanks)

    def setEndRank(self):
        self.setRank(self.endStuScos, self.endRanks)  
        
    def getMidRank(self):
        return self.midRanks    
        
    def getEndRank(self):
        return self.endRanks   
        
    def printRankDeviation(self):
    
        for idx, mRank in enumerate(self.midRanks):
            deviation = mRank - self.endRanks[idx]
            
            if deviation > 0:
               deviation = '↑' + str(abs(deviation))
            elif deviation < 0:
                 deviation = '↓' + str(abs(deviation))
            else:
                deviation = '=' + str(abs(deviation))

            print(f'mid_rank: {mRank} \t end_rank: {self.endRanks[idx]} \t Deviaiton: {deviation}')

<실행문>

import rankMod as rm
import random

midStuScos = random.sample(range(50, 101), 20)
endStuScos = random.sample(range(50,101), 20)

rd = rm.RankDeviation(midStuScos, endStuScos)
rd.setMidRank()
print(f'midStuScos: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')

rd.printRankDeviation()

---