[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 37회차 미션

참고: 공간 복잡도 

- 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
   - 시간 복잡도: 얼마나 빠르게 실행되는지
   - 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

> 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘

 

- 통상 둘 다를 만족시키기는 어려움
  - 시간과 공간은 반비례적 경향이 있음
  - 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 
  - 그래서! 알고리즘은 시간 복잡도가 중심

 

공간 복잡도 대략적인 계산은 필요함
- 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음
- 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음
- 또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 공간 복잡도를 묻는 경우도 있음

Complexity:
- expected worst-case time complexity: O(N)
- expected worst-case space complexity: O(N)

> 현업에서 최근 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있음 

 

1. 공간 복잡도 (Space Complexity)
- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
- 총 필요 저장 공간
  - 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  - 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
  - S(P) = c + S_p(n) 
    - c: 고정 공간
    - $ S_p(n) $: 가변 공간

> 빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간예 좌우됨

 

2. 공간 복잡도 계산
- 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 됨 
  - 이를 빅 오 표기법으로 표현할 수 있으면 됨 

 

 공간 복잡도 예제1
- n! 팩토리얼 구하기
  - n! = 1 x 2 x ... x n
- n의 값에 상관없이 변수 n, 변수 fac, 변수 index 만 필요함
- 공간 복잡도는 O(1)

> 공간 복잡도 계산은 실제 알고리즘 실행시 사용되는 저장공간을 계산하면 됨

 

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

 

factorial(3)

6

 

공간 복잡도 예제2
- n! 팩토리얼 구하기
  - n! = 1 x 2 x ... x n
- 재귀함수를 사용하였으므로, n에 따라, 변수 n이 n개가 만들어지게 됨
  - factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
- 공간 복잡도는 O(n)

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

  데이터 딕셔너리

읽기 전용으로 제공되는 테이블 및 뷰들의 집합

DB 전반에 대한 정보 제공

ORACLE DB는 SQL이 수행될 때마다 데이터 딕셔너리 접근

DB에서 작업이 진행되는 동안 ORACLE은 데이터 딕셔너리를 읽어 객체의 존재 여부와 사용자에게 적합한 접근 권한이 있는지 확인

SELECT * FROM DICT;

DICT는 DICTIONARY의 약자

권한이 있는 데이터사전에 대한 데이터사전명과 설명 정보 제공

데이터베이스에 있는 모든 스키마 OBJECT들의 내용 정의

SELECT * FROM DICT WHERE table_name =’USER_OBJECTS’;

스키마 오브젝트들과 이들이 데이터베이스에서 차지하는 공간 등에 대한 정보

테이블의 칼럼들에 대한 DEFAULT 값 정보

모든 오라클 사용자들에 대한 정보

각 사용자에게 부여된 권한 정보

2.     데이터 딕셔너리 종류

기준 테이블 및 참고 가능한 뷰

시스템 뷰

ALL 뷰

DBA 뷰

USER 뷰

기타 Data Dictionary

TAB -> SELECT * FROM TAB;

3.     무결성 제약조건

TABLE LEVEL에서 적용되는 RULE

제약조건은 데이터의 무결성 유지를 위해 사용자가 지정가능

제약조건은 테이블을 생성할 당시에 지정 가능

테이블 생성 후 ALTER 명령어를 통해서도 추가 가능

컬럼을 필수 필드화

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG