Data Structures and Algorithms (1)

Data Structure and Algorithms (1)

1. 파이썬 문법 정리

• % : 실수 표기
  ex)
  a = 3.141592
  print("%.4f" % a) = 소수점 4자리까지 표기

• 사칙연산
  1) / : 나눗셈
  2) // : 몫
  3) % : 나머지
  4) ** : 제곱

• 포매팅
  {2:10.4f}
  -> 두 번째 포매팅
  -> 10칸의 문자열 공간에서 오른쪽 정렬값을 반올림 소수 네 번째까지 표시

• /n : 줄
  /t : 탭
  

• 인덱싱 & 슬라이싱
  ex) 999
  [0:2] = 99 (끝번호 해당 X)

• strip
  ex)
  s = "man.goes."
  print(s.split(".")) (중간 점은 삭제 안되고 표시)

• count
  ex)
  a = "~"
  b = a.count("")

• split
  ex)
  letters = "a, b, c"
  letter_list = letters.split(",")
  print(letter_list) = ['a', 'b', 'c']
  

• reverse
  data = [1,2,3,4]
  data.reverse()

• 튜플에 데이터 추가
  a = ('1', '2', '3')
  b = list(a)
  b.append('4')
  a = tuple(b)

• dictionary
  a = {'1':'a', '2':'b', '3':'c'}
  key = [data for data in a.keys()]
  value = [data for data in a.values()]
  item = [data for data in a.items()]
  

• 집합자료형
  lists = (1,2,2,3,4,5)
  sets = set(lists)
  -> {1,2,3,4,5}
  

• for
  range(시작숫자, 종료숫자, step)

• enumerate

for i, letter in enumerate(['A', 'B', 'C']):
    print(i, letter)
0 A
1 B
2 C

2. 리스트 값 중 음수만 제거하는 함수

code1

L = [0, -11, 31, 22, -12, 33, -44, -55]
L2 = list()
for i, n in enumerate(L):
    if n < 0:
        L2.append(n)
while len(L2) != 0:
    for i,n in enumerate(L2):
        if n in L:
            L.remove(n)
            L2.remove(n)

code2 (똑같은 조건에서 L2 없이)

n=0, t=len(L)
     while n<t:
         if L[n] < 0:
             L.remove(L[n])
             n -= 1
             t -= 1
          n += 1

3. Class 언패킹

*args

Class Person:
    def__init__(self, *args):
        self.name = args[0]
        self.age = args[1]
        self.address = args[2]
maria = Person(*['마리아', '20', '반포'])

**kwargs

Class Person:
    def__init__(self,**kwargs)
        self.name = kwargs['name']
        self.age = kwargs['age']
        self.address = kwargs['address']
maria = Person(name = '마리아' age = 20, address = '반포)

4. 시간 복잡도

• Big O (O) 표기법
  O(n) : 최악의 상황 가정 (아무리 최악의 상황에서도 이정도 성능 보장)
• 오메가 : 최상
• 세타 : 평균

5. 공간복잡도 (Space complexity) – 일반적으로 시간복잡도와 반비례 관계

프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
총 필요 저장공간

• 고정공간 (알고리즘과 무관한 공간) : 코드저장공간, 단순 변수 및 상수
• 가변 공간 (알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간
• S(P) = c + S_p(n)
  c: 고정공간
  S_p(n) : 가변공간
  *빅오 표기법을 생각해볼 때, 고정공간은 상수이므로 공간복잡도는 가변공간에 좌우됨

공간복잡도의 계산
ex1) n!
n! = 1 X 2 X 3 X … n

코드

def factorial(n):
fac = 1
for index in range (2, n+1)
  fac = fac * index
return fac

n의 값과 상관없이 변수 n, 변수 fac, 변수 index 만 필요
공간복잡도는 O(1) – 상수이기 때문에

ex2) n! 재귀

코드

def factorial (n):
if n>1:
  return n * factorial (n-1)
else:
return 1

n개의 별도 공간이 생기기 때문에 O(n)

본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.