파이썬 알고리즘 (저자 최영규)

024_2학기 알고리즘 수업에서 사용되는 '파이썬 알고리즘' (저자 최영규)' 내용 정리입니다.

제 1장

알고리즘의 조건

입력, 출력, 명확성, 유한성, 유효성

최댓값 찾기

def find_max(a):
 max=a(0)
 for i in range(len(a)):
  if a[i] > max :
  max = a[i]
 return max

최대 공약수 찾기

def gcd(a,b)
 while b!=0 :
 r=a%b
 a=b
 b=r
return a

-> 개인적 코드

def gcd(a,b)
 if b==0:
  return a
 else:
  return gcd(b, a%b)

정렬

정렬: 데이터를 순서대로 재배열하는 문제 (레코드를 키의 순서로 재배열)
비교할수있는 모든 속성은 정렬의 기준이 된다.

레코드: 정렬할 대상
필드: 대상이 가지고 있는 성질
키, 정렬키: 정렬의 기준이되는 필드

비교기반과 분재기반 정렬
대부분은 비교하지만, 기수정렬과 같이 분배하는 방법도 존재
분배기반: 빠른 정렬가능, 제한적 킷값
비교기반: 연산이 분배에 비해 김
안정성: 동일한 킷값을 갖는 레코드가 있을때, 정렬후에도 이들의 상대적 위치가 바뀌지 않는 경우
제자리 정렬 : 입력 배열 외에 추가적인 메모리를 사용하지 않는경우

제 2장

시간 효율성: 더 빨리 결과를 내는 알고리즘이 더 효율적
이론적으로 복잡도를 분석하는 방법이 사용됨
공간효율성 알고리즘이 컴퓨터 메모리를 얼마나 사용하는지 나타냄

(2.1) 순차 탐색 ( 선형알고리즘 ): 리스트에 어떤 값을 가진 항목을 찾을때,
첫번째 항목부터 순차적으로 검사해야함

def s_search (a,b):
 for i in range(len(a))
  if a[i] == b:
   return i
  return -1
  
 c=list(map(int,input().split())
 d=int(input())
 
 print(" %d찾기:" %(b),s_search(a,b))
  

빅오 표기법: 어떤 함수의 점근적 하한을 표시하는방법
O(1): 연산이 한번
O(N): for과 같은 순환 연산이 한개포함
O(n^2): for 내부에 for과같이 내부순환 연산이 한개 존재

중복항목 탐색

제3장

선택 정렬
억지기법(완전탐색):
제자리 정렬

def S(A):
 n=len(A)
 for i in range (n-1):
 i=min
  for j in range (i+1,n):
  if A[j]<A[min]:
  min=j
  A[i],A[min]=A[min],A[i]
  P(A,i+1)
 def P(arr,val):
 print("  step%2d= "%val, end='')
 print(arr) 
A=list (map(int,input().split())
print(f'orginal: ',A)
S(A)
print(f'selection: ',A)

순차탐색(선형탐색)

문자열 매칭 (억지기법)

완전탐색: 가능한 모든 경우를 탐색하는 방법