3.3 파이썬 알고리즘 실습 스터디노트1

알고리즘 개념 스터디노트

선형 검색
: (1) 리스트에서 가장 앞에 있는 숫자 7을 검색하고 인텍스를 출력하라
(2) 모든 7을 검색하고 인덱스를 출력해라

( 내 풀이 )

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

searchNum = int(input('숫자를 입력하세요 : '))

#(1) 풀이
for idk, n in enumerate(nums):
    if searchNum == n:
        print(f'{idk}번쨰 인덱스 의 값 {n}')
        break

#(2) 풀이
print('-'*30)
for idk, n in enumerate(nums):
    if searchNum == n:
        print(f'{idk}번쨰 인덱스 의 값 {n}')

🤔 이렇게 되면 값이 없을 때 아무것도 나오지 않게 됨

( 영상 속 풀이 : 보초법 사용 )

• 보초법 : 마지막 인덱스에 찾으려는 값을 추가해서, 찾는 가정을 간략화 한다. 검색에 성공할 경우 맨 마지막 인덱스보다 앞에서 검색이 되고, 없다면 맨 마지막에 검색된다.

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

searchNum = int(input('숫자를 입력하세요 : '))
searchIdx = -1

nums.append(searchNum) #보초법 사용하는 법

#(1) 풀이
n = 0
while True:
    if nums[n] == searchNum:
        if n != len(nums) - 1:
            searchIdx = n
       break

    n += 1


if searchIdx < 0:
    print('not search Index')

else :
    print(f'searchIdx : {searchIdx}')

이진 검색 : 가운데 데이터를 이용한다.

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
#이진 검색에서는 값이 정렬되어있어야 함

searchNum = int(input('숫자를 입력하세요 : '))
searchIdx = -1

staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx : {midIdx}')
print(f'midVal : {midVal}')

while searchNums < = datas[lens(datas) -1] and searchNums >= datas[0]:

	if searchNums == datas[lens(datas) -1] #마지막 값이랑 같다면
    	 searchIdx = len(datas) - 1
         break
	if searchNums > midVal:
    	staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx : {midIdx}')
		print(f'midVal : {midVal}')
        
    elif searchNums < midVal:
    	endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx : {midIdx}')
		print(f'midVal : {midVal}')
        
    elif searchNums == midVal:
    	searchIdx = midIdx
        break
 
 print(f'searchIdx : {searchIdx}')

• 실습 영상

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

nums.sort()
print(nums)
searchNums = int(input('찾으려는 숫자 입력 : '))
searchIdx = -1

staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(midIdx, midVal)

while searchNums <= nums[len(nums)-1] and searchNums >= nums[0]:
    if searchNums == nums[len(nums) - 1]:
        searchIdx = len(nums) - 1
        break

    elif searchNums > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')

    elif searchNums < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx : {midIdx}')
        print(f'midVal : {midVal}')

    elif searchNums == midVal:
        searchIdx = midIdx
        break

print(f'searchIdx : {searchIdx}')

🤔만약 88 아래 숫자를 넣으면 무한루프에 갇히는 데 그걸 중간에 없앨 수 있는 게 필요하지 않을까?

순위

import random

nums = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)] #0이 20개 있는 리스트 생성

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

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

[Output]

버블 정렬

20명의 학생들을 키 순서 대로 줄 새워보자. 학생 키는 random 모듈을 이용해 170 ~ 185 사이로 생성한다.

모듈

import copy

def bubbleSort(ns, deepCopy = True):
	if deepCopy:
    	cns = copy.copy(ns)
    else:
    	cns = ns
        
    length = len(cns) - 1
    for i in range(length):
    	for j in range(length - 1):
        	if cns[j] > cns [j + 1]:
            	cns[j], cns[j +1] = cns[j+1], cns[j]
    
    return cns

실행

import random as rd
import sortMod as sm

students = []

for i in range(20):
	students.append(rd.randint(170, 185))
    
print(f'students : {students}')

sortedStudents = sm.bubbleSort(students, deepCopy=False)

print(f'students: {students}')
print(f'sortedStudents {sortedStudents}')

✏️ 원본 데이터를 수정할 것인지, 유지할 것인지를 잘 파악하고 copy를 이용할 것

삽입 정렬 : 앞에서 부터 정렬하면서 정렬 위치를 찾는다.

1과 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들자

 	요구사항1) 생성 난수를 오름차순 또는 내림차순으로 정렬하는 알고리즘 수현
    요구사항2) 생성 난수 중 최솟값, 최댓값을 반환하는 함수 구현
    

모듈

class SortNumbers:
	def __init__(self, ns, asc = True): #생성자
    	self.nums = ns
    	self.isAsc = asc
    
    def isAscending(self, flag):
    	self.isAsc = flag
        
    def setSort(self):
    	for i1 in range(1, len(self.nums)):
        	i2 = i1 - 1
            cNum = self.nums[i1] #현재 넘버
            
            if self.isAsc: #오름차순이면
            	while self.nums[i2] > cNum and i2 >= 0:
                	self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1
                    
            else: #내림차순이면
            	while self.nums[i2] < cNum and i2 >= 0:
                	self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1
                    
            self.nums[i2 + 1] = cNum
     
     def getSortedNumbers(self): #값을 가져갈 수 있게끔
     	return self.nums
        
     def getMinNumber(self):
     	if self.isAsc:
        	return self.nums[0]
        else:
        	return self.nums[len(self.nums) - 1]
            
     def getMaxNumber(self):
     	if self.isAsc:
        	return self.nums[len(self.nums) - 1]        	
        else:
            return self.nums[0]

실행

import random
import sortMod as sm

nums = random.sample(range(1, 1000), 100)
print(f'not sorted numbers : {nums}')

#객체 생성
sn = sm.SortNumbers(nums)

#오름차순
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by ASC : {sortedNumbers}')

#내림차순
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by DESC : {sortedNumbers}')

#min&max
print(f'min : {sn.getMinNumber()}')
print(f'max : {sn.getMinNumber()}')