22.12.19(월) -12.21(수) /정렬

-딕셔너리
key값을 통해 value 구함
-list.split() : 공백을 기준으로 분리 -> 리스트로 반환

• 알고리즘
  -보초법 : 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정 간략화
  마지막 이전에 찾아야 성공/ 마지막에 찾으면 임의로 추가했던 데이터이기 때문에 실패
  -이진검색 : 데이터가 정렬되어 있다는 가정
  startidx,endidx,mididx,midval

값이 0이고 길이가 20인 리스트 생성

ranks=[ 0 for i in range(20)]

-for문으로 숫자 2개 비교하고 싶을 때 : 중첩 for문

• 숫자 2개 자리바꾸는 법

1. temp=nums[j]; nums[j]=nums[j+1]; nums[j+1]=temp
2. nums[j],nums[j+1] = nums[j+1],nums[j]

12.20(화)

• 버블정렬

  for i in range(len(nums)):
  for j in range(len(nums)-1-i):
  if nums[j] >nums[j+1]:
  nums[j],nums[j+1] = nums[j+1],nums[j]

-깊은복사(원본유지)

import copy
def bubble(students,deepcopy=True):
if deepcopy:
nstudents=copy.copy(students)
else:
nstudents=students

ex파일 : sortedstudents=sm.bubblesort(students,deepcopy=True)

• 삽입정렬 (오름차순)

  for i1 in range(1,len(nums)):
  i2=i1-1
  cnum=nums[i1]

  while nums[i2] > cnum and i2>=0:
      nums[i2+1] = nums[i2]
      i2-=1
  
  nums[i2+1]=cnum

  (내림차순)
  while nums[i2] < cnum and i2>=0:
  

12.21(수)

• 선택정렬 : 주어진 리스트 중 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체(2번째 값부터 비교)

for i in range(len(nums)-1):
minidx=i

for j in range(i+1,len(nums)):
    if nums[minidx] >nums[j]:
        minidx=j

nums[i],nums[minidx] = nums[minidx],nums[i]

-깊은 복사
import copy

result=sm.sortnumber(copy.deepcopy(scores))

-Class
1. 생성자 def init(self):
2. 함수

• 최대값

  class Maxalgorithm:
  def init(self,ns):
  self.nums=ns
  self.maxnum=0

  def getmaxnum(self):
      self.maxnum=self.nums[0]
  
      for n in self.nums:
          if self.maxnum < n:
              self.maxnum=n
  
      return self.maxnum
      

• 최빈값
  : 값을 인덱스라고 생각하고 가장 큰값 기준 +1크기로 리스트 만들어서 1씩 추가 (최대값 모듈 이용해서 최빈값 구함)

q1. 점수를 5단위로 랜덤하게 나타내고 싶을 때

rn =random.randint(71,100)
if rn!=100: rn = rn-(rn%5)

-유클리드 호제법(최대공약수)
: 두 자연수 n1,n2(n1 > n2)에 대하여 n1 /n2로 나눈 나머지를 r이라고 할 때, n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다.

def gcd(n1,n2):
if n1%n2==0:
return n2
else:
return gcd(n2, n1 % n2)

-병합정렬 : 분할 후 합치기(재귀함수 이용)
-퀵 정렬 : 기준값보다 작은 값과 큰 값으로 분리

def qsort(ns):
if len(ns) <2:
return ns
mididx=len(ns)//2
midval=ns[mididx]

smallnums=[];samenums=[];bignums=[]
for n in ns:
    if n<midval:
        smallnums.append(n)
    elif n==mididx:
        samenums.append(n)
    else:
        bignums.append(n)
        
return qsort(smallnums) +samenums + qsort(bignums)