알고리즘에 대해 알아보자!
- 삽입정렬
- 선택정렬
- 최댓값
- 최솟값
- 최빈값
5. 삽입정렬
정렬되어 있는 자료 배열과 비교해서 정렬 위치를 찾는다
이미 정렬되어 있는 자료에 내가 어디에 들어갈지 자리를 찾는 정렬
- 오름차순
nums=[5,10,2,1,0]
for i1 in range(1, len(nums)): # [1]부터 시작해서 [0]과 비교
i2 = i1 -1 # i2=[0], i1-[1] 설정
cNum = nums[i1]
while nums[i2] > cNum and i2 >= 0: # 앞수가 뒤수 보다 크면 ⭐
nums[i2 + 1] = nums[i2] # 인덱스가 1자리 뒤로 밀리고
i2 -= 1 # 계속 진행되야 하기때문에 -1 씩 뺴준다..?
nums[i2 + 1] = cNum
print(f'nums : {nums}')
print('-'*20)
print(f'nums : {nums}')▼
nums : [5, 10, 2, 1, 0]
nums : [2, 5, 10, 1, 0]
nums : [1, 2, 5, 10, 0]
nums : [0, 1, 2, 5, 10]
--------------------
nums : [0, 1, 2, 5, 10]- 내림차순
nums=[0,5,2,10,1]
for i1 in range(1, len(nums)): # [1]부터 시작해서 [0]과 비교
i2 = i1 -1 # i2=[0], i1-[1] 설정
cNum = nums[i1]
while nums[i2] < cNum and i2 >= 0: # 앞수가 뒤수 보다 작으면 ⭐
nums[i2 + 1] = nums[i2] # 인덱스가 1자리 뒤로 밀리고
i2 -= 1 # 계속 진행되야 하기때문에 -1 씩 뺴준다..?
nums[i2 + 1] = cNum
print(f'nums : {nums}')
print('-'*20)
print(f'nums : {nums}')▼
nums : [5, 0, 2, 10, 1]
nums : [5, 2, 0, 10, 1]
nums : [10, 5, 2, 0, 1]
nums : [10, 5, 2, 1, 0]
--------------------
nums : [10, 5, 2, 1, 0]🏷️ 실습
1~100까지 난수 100개 생성, 요구 사항을 만족하는 모듈 제작
(요구사항1) 오름차순,내림차순 정렬 알고리즘 구현
(요구사항2) 최솟값, 최댓값 반환 함수 구현
- class : sortMod.py
#1. 클래스 만들기
class SortNumbers:
#2. 숫자(ns)를 받는 자료구조, 오름차순/내림차순 결정 함수(asc=True) 로 구성
def __init__(self, ns, asc=True):
#3. 속성 초기화
self.nums = ns
self.isAsc = asc
#4. 오름차순/내림차순 결정 함수(isAccending), 매개변수(flag)
def isAccending(self, flag):
self.isAsc = flag
#5. sort 함수
def setSort(self):
#6. 삽입정렬 for()문
for i1 in range(1, len(self.nums)):
i2 = i1 -1
cNum = self.nums[i1] #cNum : 현재 숫자
#7. 오름차순이라면
if self.isAsc:
while self.nums[i2] > cNum and i2 >=0: # i2가 현재숫자(cNum)크다면 자리를 바꿔야 함
self.nums[i2+1] = self.nums[i2]
i2 -= 1
#8. 내림차순이라면
else:
while self.nums[i2] < cNum and i2 >=0: # i2가 현재숫자(cNum)작다면 자리를 바꿔야 함
self.nums[i2+1] = self.nums[i2]
i2 -= 1
# 9. sort 함수 종료
self.nums[i2 +1] = cNum
#10. 외부에서 sort 된 함수를 가져갈 수 있는 함수()
def getSortedNumbers(self):
return self.nums
#11. 최소값 구하기
def getMinNumber(self):
# 12.위에가 오름차순이면,
if self.isAsc:
#13. 첫번째[0]가 최소값
return self.nums[0]
#14. 내림차순이면
else:
#15. 맨 끝값(len(nums)-1)이 최소값
return self.nums[len(self.nums) -1]
#16. 최소값 구하기
def getMaxNumber(self):
# 17.위에가 오름차순이면,
if self.isAsc:
#18. 맨 끝값(len(nums)-1)이 최대값
return self.nums[len(self.nums) - 1]
return self.nums[0]
#19. 내림차순이면
else:
#20. 첫번째[0]가 최대값
return self.nums[0]- 실행 : sortEx.py
#20. 랜덤 모듈 생성
import random
#22. class 가져오기
import sortMod as sm
#21. 숫자 범위 설정
nums = random.sample(range(1, 1000), 100)
print(f'정렬 전 숫자 100개 : {nums}')
#23. 객체 생성
sn = sm.SortNumbers(nums)
#24. 오름차순(accending)
sn.setSort() #정렬하고
sortNumbers = sn.getSortedNumbers() # 정렬한걸 받아서 sort
print(f'오름차순 : {sortNumbers}') # 출력
#25. 내림차순(deccending)
sn.isAccending(False)
sn.setSort() # 정렬하고
sortNumbers = sn.getSortedNumbers() # 정렬한걸 받아서 sort
print(f'내림차순 : {sortNumbers}') # 출력
#26. 최소값 & 최대값
print(f'최소값 : {sn.getMinNumber()}')
print(f'최대값 : {sn.getMaxNumber()}')▼
정렬 전 숫자 100개 : [259, 484, 379, 465, 657, 704, 761,... 744, 548, 363, 680]
오름차순 : [20, 26, 27, 89, 111, 117, 119, 126, 127, 134, 142, ...]
내림차순 : [993, 986, 983, 981, 949, 936, 923, 921, ...]
최소값 : 20
최대값 : 99
6. 선택정렬
현재의 나와 자리를 바꾸는 것
최소값을 찾아,기준이 되는 값과 교체하는 방식
- 자리바꾸는 코드 (1), (2) 중 선택해서 사용할 것!
nums = [4,2,5,1,3]
print(f'정렬 전 nums : {nums}')
# 기준이 되는 값 ~ 끝에서 1자리 앞
for i in range(len(nums) -1):
# 최소값의 인덱스 자리
minIdx = i
# i 와 비교하는 값들의 반복문 (i보다 크고, 끝까지)
for j in range(i +1, len(nums)):
# i가 기준(j) 보다 크다면
if nums[minIdx] > nums[j]:
# 최소값은 변경된다
minIdx = j
#▼ ⭐(1)방법 : python에서 서로 자리 바꾸는 코드
tempNum = nums[i] # i에 해당하는 값 저장
nums[i] = nums[minIdx]
nums[minIdx] = tempNum
#▼ ⭐(2)방법 : python에서 서로 자리 바꾸는 코드
nums[i], nums[minIdx] = nums[minIdx], nums[i]
print(f'변화 과정 : {nums}')
print(f'정렬 이후 nums : {nums}')▼
정렬 전 nums : [4, 2, 5, 1, 3]
변화 과정 : [1, 2, 5, 4, 3]
변화 과정 : [1, 2, 5, 4, 3]
변화 과정 : [1, 2, 3, 4, 5]
변화 과정 : [1, 2, 3, 4, 5]
정렬 이후 nums : [1, 2, 3, 4, 5]🏷️ 실습
학생 20명의 시험 점수를 오름/내림차순 정렬
시험점수는 50-100까지
- class : selectionSort.py
#1. 랜덤 모듈
import random
#6. class가져오기
import sortMod as sm
#-------------------------------------------------
#9. 깊은 복사
import copy
#-------------------------------------------------
#2. 기본 설정
scores = random.sample(range(50, 101), 20)
print(f'20명 맞는지 확인 : {len(scores)}')
print(f'정렬되기 전 data : {scores}')
#7. 오름차순 출력 (sortMod.py #4.번을 호출해서 옴)
#10. copy.deepcopy(scores) : 원본이 훼손되지 않고 완벽하게 복사
result = sm.sortNumber(copy.deepcopy(scores))
print(f'오름차순 결과 : {result}')
print(f'원본훼손 여부 확인 : {scores}')
#8. 내림차순 출력 (sortMod.py #4.번을 호출해서 옴)
result = sm.sortNumber(copy.deepcopy(scores), asc=False) # sortMod.py #3.번 True의 반대로 호출
print(f'내림차순 결과 : {result}')- sortMod.py
#3. 함수 : 받는 자료(ns), 오름/내림 기본값(asc=True)
def sortNumber(ns, asc=True):
#4. 자세한 설명은 선택정렬 개념 부분 참고
#오름차순
if asc:
for i in range(len(ns) -1):
minIdx = i
for j in range(i +1, len(ns)):
if ns[minIdx] > ns[j]:
minIdx = j
ns[i], ns[minIdx] = ns[minIdx], ns[i]
#내림차순
else:
for i in range(len(ns) -1):
minIdx = i
for j in range(i +1, len(ns)):
if ns[minIdx] < ns[j]:
minIdx = j
ns[i], ns[minIdx] = ns[minIdx], ns[i]
#5. 호출 받은 곳으로 다시 반환
return ns▼
20명 맞는지 확인 : 20
정렬되기 전 data : [55, 72, 66, 81, 56, 88, 54, 65, 83, 57, 86, 97, 79, 92, 89, 52, 85, 99, 98, 87]
오름차순 결과 : [52, 54, 55, 56, 57, 65, 66, 72, 79, 81, 83, 85, 86, 87, 88, 89, 92, 97, 98, 99]
원본훼손 여부 확인 : [55, 72, 66, 81, 56, 88, 54, 65, 83, 57, 86, 97, 79, 92, 89, 52, 85, 99, 98, 87]
내림차순 결과 : [99, 98, 97, 92, 89, 88, 87, 86, 85, 83, 81, 79, 72, 66, 65, 57, 56, 55, 54, 52]
7. 최대값
자료구조에서 가장 큰 값을 찾는다
class MaxAlgoritm:
#1. 받을 데이터 명 : ns
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
#2. 최대값 반환 : getMaxNum
def getMaxNum(self):
#3. maxNum idx 재설정
self.maxNum = self.nums[0]
#4. nums에 있는 data가 n에 1개씩 들어 옴
for n in self.nums:
#5. self.maxNum과 비교
if self.maxNum < n: #6. 작으면 더이상 최대가 아님
self.maxNum = n #7. 따라서 더 큰 n으로 재설정
return self.maxNum
#8. 객체 생성
ma = MaxAlgoritm([-2,-4,5,7,10,0,8,20,-11])
maxNum = ma.getMaxNum()
print(f'maxNum : {maxNum}')▼
maxNum : 20🏷️실습
리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘 제작
!! 문자인 경우 '아스키코드'를 이용해 비교 함
#1. class 생성
class MaxAlgorithm:
#2. 생성자 (외부에서 객체를 생성할때, cs라는 자료구조를 던져줌)
def __init__(self, cs):
#3. cs 자료를 받아서 속성 초기화
self.chars = cs
#4. chars에서 가장 큰 값을 찾는 maxChar 초기화
self.maxChar = 0
#3. getMaxChar라는 외부 사용가능 함수 생성
def getMaxChar(self):
#4. 외부에서 들어온 chars의 첫번째[0] data를 넣어 줌
self.maxChar = self.chars[0]
#5. chars에서 c를 뽑아서 for()반복을 돌림
for c in self.chars:
#6. 아스키코드로 반환해주는 ord 키워드 사용
# ord 안에 파라미터로 '문자'를 넣어주면 반환됨 : ord(self.maxChar)
if ord(self.maxChar) < ord(c):
#7. c가 더 크니까, maxChar가 c로 바뀜 (재할당)
self.maxChar = c
#maxChar 반환 : 반환해주면 호출한 곳에서 가장 큰 문자를 반환받을 수 있음
return self.maxChar
chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = MaxAlgorithm(chars)
maxChar = mc.getMaxChar()
print(f'maxChar: {maxChar}')▼
maxChar: x
8. 최소값
자료구조에서 가장 작은 값을 찾는다
▼ #7.최대값을 구하는 풀이와 유사함, 참고할 것!
class MinAlgorithm:
def __init__(self, ns):
self.nums = ns
self.minNum = 0
def getMinNum(self):
self.minNum = self.nums[0]
for n in self.nums:
if self.minNum > n:
self.minNum = n
return self.minNum
ma = MinAlgorithm([-2,-4,5,7,10,0,8,20,-11])
minNum = ma.getMinNum()
print(f'minNum : {minNum}')▼
minNum : -11🏷️실습
리스트에서 아스키코드가 가장 작은 값을 찾는 알고리즘을 만들어보자
class MinAlgorithm:
def __init__(self, cs):
self.chars = cs
self.minChar = 0
def getMinChar(self):
self.minChar = self.chars[0]
for c in self.chars:
if self.minChar > c:
self.minChar = c
return self.minChar
ma = MinAlgorithm(['c', 'x', 'Q', 'A', 'e', 'P', 'p'])
minChar = ma.getMinChar()
print(f'minChar : {minChar}')▼
minChar : A
9. 최빈값
빈도수가 가장 많이 나오는 것을 찾는 알고리즘
#1. 최대값을 class 로 구성
class MaxAlgorithm:
#2. 생성자 (외부에서 객체를 생성할때, ns라는 자료구조를 던져줌)
def __init__(self, ns):
self.nums = ns #3. ns 자료를 받아서 속성 초기화
self.maxNum = 0 #4. 가장 큰 숫자 속성 설정/초기화
self.maxNumIdx = 0 #5. maxNum에 해당하는 인덱스 속성 설정/초기화
#6. 가장 큰 인덱스 & 숫자를 구하는 setMaxIdxAndNum 구성
# 외부 사용가능 함수 생성
def setMaxIdxAndNum(self):
self.maxNum = self.nums[0] # 7. 외부에서 들어온 nums의 첫번째[0] data를 넣어 줌
self.maxNumIdx = 0 #8. maxNum에 해당하는 인덱스 0으로 초기화
#9. 최대값 구하기 (i : 인덱스, n : 숫자)
for i, n in enumerate(self.nums): #10. nums에서 i, n을 받아서 반복
if self.maxNum < n:
self.maxNum = n #11. 재할당
self.maxNumIdx = i #12. 재할당
# 13. 외부에서 가장 큰 숫자를 구해오는 함수
def getMaxNum(self):
return self.maxNum
# 14. 외부에서 가장 큰 숫자의 인덱스를 구해오는 함수
def getMaxNumIdx(self):
return self.maxNumIdx
nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlo = MaxAlgorithm(nums)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
print(f'maxNum: {maxNum}')
#-------------------------------------------------------------------
#15. nums 리스트가 몇개 인지 모른다는 가정 하에, 인덱스 리스트 구하기
#최대값 길이 만큼의 배열 만들기, 최대값 만큼의 인덱스 길이가 구해질 것.
indexes = [0 for i in range(maxNum + 1)] #16. [0으로 초기화 하겠다, maxNum의 갯수 만큼 반복해서 구하겠다]
print(f'indexes: {indexes}')
print(f'indexes length: {len(indexes)}')
#17. 새로 만든 인덱스(#15,16)에서 몇개가 있는지 확인하기 위해 구성하는 문장
for n in nums:
indexes[n] = indexes[n] + 1 #18.누적 자료 구성 : 새롭게 만든 인덱스 n번째(#15) = 기존 인덱스n번째 +1
print(f'indexes: {indexes}') #19. '7'이 4번 있음 = 7번째 인덱스는 4로 출력됨
maxAlo = MaxAlgorithm(indexes)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
print(f'maxNum: {maxNum}')
print(f'maxNumIdx: {maxNumIdx}')
#--------------------------------------------------------------------------------------
#20. 최종 결과 출력
print(f'최종 결과 : {maxNumIdx}의 빈도수가 {maxNum}로 가장 높다.')▼
maxNum: 17
indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
indexes length: 18
indexes: [0, 1, 0, 1, 0, 0, 1, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
maxNum: 4
maxNumIdx: 7
최종 결과 : 7의 빈도수가 4로 가장 높다.🏷️실습
- maxScore.py : class 문
#1. class 생성 (최대값을 이용해 최빈값 구성)
class MaxAlgorithm:
#2. 생성자(__init__) 자료구조 받기
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
self.maxNumIdx = 0
#3. 최대값과 최대값의 인덱스 세팅
def setMaxIdxAndNum(self):
self.maxNum = self.nums[0]
self.maxNumIdx = 0
#4. 인덱스 & 숫자가 필요하니까, enumerate 이용
for i, n in enumerate(self.nums):
if self.maxNum < n:
self.maxNum = n
self.maxNumIdx = i
def getMaxNum(self):
return self.maxNum;
def getMaxNumIdx(self):
return self.maxNumIdx;- mode.py : 실행문
#5. 랜덤으로 무작위 점수 출력
import random
#6.class호출
import maxScore as ms
#7. 리스트 만들어 주고!
scores = []
#8. 중복될 수 있어서, .sample() 보다 하나하나 뽑는 걸로 구성
for i in range(100):
rn = random.randint(71, 100) #9. 70~100점 중에
#10. 출제문제가 5단위로 점수가 끊어지고 있으니까, 그에 맞춰 문장 구성
#만약 rn이 100점이 아니면, rn을 5단위로 끊어질 수 있게 구성
#rn을 5로 나눈 나머지를 뺀다
if rn != 100: rn = rn - (rn % 5)
scores.append(rn) #11. 추가
print(f'scores: {scores}')
print(f'scores length: {len(scores)}')
print('-'*25)
#------------------------------------------
#12. 최댓값 알고리즘
maxAlo = ms.MaxAlgorithm(scores)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
print(f'maxNum: {maxNum}')
print('-'*25)
#------------------------------------------
#13. 인덱스 리스트 생성
indexes = [0 for i in range(maxNum + 1)] #14. [0으로 초기화, maxNum의 갯수 만큼 반복해서 구하겠다]
print(f'indexes: {indexes}')
print(f'indexes length: {len(indexes)}')
print('-'*25)
#------------------------------------------
#15. 인덱스 리스트에 빈도 저장
for n in scores:
indexes[n] = indexes[n] + 1
print(f'indexes: {indexes}')
print('-'*25)
#------------------------------------------
#16. while()돌면서 빈도를 출력
n = 1
while True:
maxAlo = ms.MaxAlgorithm(indexes)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
maxNumIdx = maxAlo.getMaxNumIdx()
if maxNum == 0: #17. maxNum이 0인건 의미가 없으니까
break #18. 종료
print(f'{n}. {maxNumIdx}빈도수: {maxNum}\t', end='')
print('+' * maxNum)
indexes[maxNumIdx] = 0
# ▲ 19. 높은 숫자 1번 출력 후 제외, 다음 숫자 출력을 위해 최대값을 0으로 매김,
# 그럼 그 다음 숫자가 최대 숫자가 됨
# 즉, 1번에 0을 부여해 2번이 최대 값을 가지게 함, 이걸 반복
n += 1▼
(1) scores: [75, 70, 75, 85, 75, 95, 100, 90, 95, 90, 95, 90, 85, 95, 100, 80, 95, 95, 100, 70, 75, 85, 85, 95, 70, 90, 95, 85, 90, 75, 75, 70, 70, 95, 70, 75, 80, 75, 90, 95, 75, 85, 80, 75, 75, 80, 70, 85, 100, 70, 100, 75, 95, 80, 85, 90, 75, 75, 80, 95, 85, 85, 85, 85, 95, 80, 80, 95, 75, 80, 75, 80, 95, 100, 80, 95, 90, 80, 95, 85, 75, 80, 75, 85, 90, 80, 95, 85, 90, 85, 95, 80, 85, 85, 70, 90, 95, 75, 90, 85]
(2) scores length: 100
-------------------------
최대값; maxNum: 100
-------------------------
인덱스 리스트; indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
인덱스 리스트 길이; indexes length: 101
-------------------------
인덱스 빈도수 저장; indexes: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 19, 0, 0, 0, 0, 15, 0, 0, 0, 0, 19, 0, 0, 0, 0, 12, 0, 0, 0, 0, 20, 0, 0, 0, 0, 6]
-------------------------
1. 95빈도수: 20 ++++++++++++++++++++
2. 75빈도수: 19 +++++++++++++++++++
3. 85빈도수: 19 +++++++++++++++++++
4. 80빈도수: 15 +++++++++++++++
5. 90빈도수: 12 ++++++++++++
6. 70빈도수: 9 +++++++++
7. 100빈도수: 6 ++++++제로베이스 데이터 스쿨
Daily Study Note
비전공자의 데이터 공부법