TIL | 9.21.수 [자료구조와 알고리즘 / Python 복습 🐢]

- 자료구조와 알고리즘 [시간 복잡도 / 공간 복잡도 / 점근 표기법]

1. 시간 복잡도
시간 복잡도란? 입력값의 양에 따른 출력 시간의 복잡도

쉽게 말해 각 코드 한 줄 실행이 1번의 연산이라고 볼 수 있다.
(for, if, while 등 반복해서 실행되는 코드 또한 반복해서 세어준다 | 알고리즘을 위해 필요한 연산의 전체 횟수)

👉 입력값 N에 대하여 얼마나 비례하여 실행 되느냐가 제일 중요한 관건이라고 할 수 있다.

for num in array:              # array 의 길이만큼 아래 연산이 실행
    for compare_num in array:  # array 의 길이만큼 아래 연산이 실행
        if num < compare_num:  # 비교 연산 1번 실행
            break
    else:
        return num
            
 👉 array 의 길이만큼 N번 * array 의 길이만큼 N번 * 비교연산 1번 = N * N의 시간 복잡도

2. 공간 복잡도
공간 복잡도란? 알고리즘을 위해 필요한 메모리의 양 (저장공간의 차지)

쉽게 말해 저장된 변수, list, dict, index 등의 저장 공간(길이)를 얼마나 차지 하는지를 말한다.
공간 복잡도는 시간 복잡도 보다 중요성이 떨어지기 때문에 조금 더 시간 복잡도에 중점을 두고 코딩을 해야한다.

👉 이유는, 저장공간의 상수(메모리 차지 용량)가 아무리 크다해도, 시간 복잡도의 N에 얼마나 비례하여 실행되느냐에 따라 결과값은 쉽게 바뀌기 때문에 (아무리 더해봤자 곱하는걸 이기기 쉽지 않음 : 100+100+100+100+... vs 2*2*2*2*2*2*2*....)

 

🔥 중요도 🔥 시간 복잡도 >> 공간 복잡도

3. 점근 표기법
시간 복잡도와 공간 복잡도의 정도를 나타낼 수 있는 표기법
+ 모든 알고리즘을 표현하는 방식

[점근 표기법의 종류]

빅오(Big-O)표기법	빅 오메가(Big-Ω) 표기법
최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인가	최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인가
알고리즘에서 주로 쓰이는 표기법 (최악의 경우를 대비해야 하기 때문)	최상의 경우는 고려 할 필요성이 떨어짐

[우리가 고려해야 할 상황?]

• 3-1) 입력값에 비례해서 얼마나 늘어날지 파악해보자. 1 ? N ? N^2 ?
• 3-2) 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.
• 3-3) 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자

[+ 참고 링크]
https://xodud2972.tistory.com/60

Python 51 - 시간복잡도, 공간복잡도, 빅오표기법 ( 알고리즘 공부 )

 

---

 

 

+ 자료구조와 알고리즘 추가

4. ASCII Code
컴퓨터는 알파벳을 숫자로 인식한다.
따라서, 알파벳을 추후에 계산하거나, 알고리즘에 맞게 적용하고 싶을 때 ASCII 코드로 변환해 활용할 수 있다.

[str.Isalpha]
str.Isalpha를 이용해 현재 입력된 str이 알파벳인지 아닌지 알려준다 (True / False)

print("a".isalpha())    # True
print("1".isalpha())    # False

s = "abcdefg"
print(s[0].isalpha())   # True

[ord(' ')]
알파벳을 → 숫자(ASCII 코드)로 변환하기 위해 ord() 를 이용한다.

print(ord('a'))               # 97
print(ord('a') - ord('a'))    # 97-97 -> 0
print(ord('b') - ord('a'))    # 98-97 -> 1

+ 알파벳의 빈도를 체크하기 위한 배열을 만들땐

alphabet_occurrence_array = [0] * 26

아스키 코드를 이용해 'a'=97 를 인덱스 0번으로 기준을 설정 모든 알바벳 번호에서 97을 빼주면 순서대로 1,2,3... 인덱스에 저장
👉 index[0] = 'a', index[1] = 'b', index[2] = 'c', ........ , index[25] = 'z'



5. 소수에서의 시간 복잡도
소수란? 1과 자기자신만을 약수로 갖는 수를 말한다.

• 5-1) 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근(N ** 0.5)보다 크지 않은 어떤 소수로도 나눠지지 않는다.
• 5-2) 주어진 자연수 N이 변수에 대해 나눴을때 나머지 == 0 이라면 소수(X) / 나머지 != 0 이라면 소수(O)

👉 예) 16의 제곱근 = 4이다 . (나눠떨어지지 않을땐 미만으로 계산 : 12의 제곱은 = 4(X) 3(O) )
그럼 16보다 작은 1 ~ 4의 배수들 중 16을 나눴을 때 나머지가 0이 아닌 수가 소수이다.

 

 

 

---

 

 

 

- 🐢 Python 복습 | 거북이 반 🐢 [class 상속]

 

1. 상속 | Inheritance 

Class에서 상속이란?

물려주는 클래스(Parent Class, Super class)의 속성과 메서드를 물려받는 클래스(Child class, sub class)가 가지게 되는 것입니다.

 

[선언방법]

class 부모클래스:
    ...속성...
    ...메서드...

class 자식클래스(부모클래스): 👉 부모클래스를 인자로 넣어 상속
    ...내용...

  활용 예)

class Country: 

    name = '국가명'
    population = '인구'
    capital = '수도'

    def show(self):
        print('국가 클래스의 메소드입니다.')


class Korea(Country): 

    def __init__(self, name):
        self.name = name

    def show_name(self):
        print('국가 이름은 : ', self.name)


test = Korea('대한민국')

print(test.name)        👉 '대한민국'
print(test.population)  👉 '인구'
print(test.capital)     👉 '수도'
test.show()             👉 '국가 클래스의 메소드입니다.'

test.show_name()        👉 '국가 이름은 : 대한민국'

 →  Korea Class에서 선언된 변수 'test'이지만 Country Class 상속을 받았기 때문에 population, capital 또한 선언가능

 

 

 

 

[메서드 오버라이딩]

• 오버라이딩이란? 부모클래스에서 상속받은 그래로 속성과 메서드를 이용하지 않고 자식 클래스 내에서 재정의 하는것을 말한다.
• 👉 자식클래스에서 재정의된 값만 출력됨

class Country: 

    name = '국가명'
    population = '인구'
    capital = '수도'

    def show(self):
        print('국가 클래스의 메소드입니다.')


class Korea(Country): 

    def __init__(self, name,population, capital):
        self.name = name
        self.population = population
        self.capital = capital
👉 입력값 새로 받아서


    def show(self):
        print('국가 이름은 : ', self.name)
        print('국가 인구는 : ', self.population)
        print('국가 수도는 : ', self.capital)
👉 재정의된 값 출력


test = Korea('대한민국', 50000, '서울')

print(test.name)
print(test.population)
print(test.capital)
test.show()

👉 국가명, 인구, 수도 → 대한민국 50000 서울 : 재정의됨

 

 

• 부모클래스의 메소드도 수행하고, 자식클래스의 메소드의 내용도 함께 출력하기를 원할땐 super()를 이용하여 부모클래스를 호출한다.  👉 부모 클래스의 메서드 + 자식 클래스에서 재정의된 값 모두 출력

class Country: 

    name = '국가명'
    population = '인구'
    capital = '수도'

    def show(self):
        print('국가 클래스의 메소드입니다.')


class Korea(Country): 

    def __init__(self, name,population, capital):
        self.name = name
        self.population = population
        self.capital = capital


    def show(self):
        super().show()
        
        print('국가 이름은 : ', self.name)
        print('국가 인구는 : ', self.population)
        print('국가 수도는 : ', self.capital)


test = Korea('대한민국', 50000, '서울')

print(test.name)
print(test.population)
print(test.capital)
test.show() 👉 부모 클래스 + 자식 클래스 : 두 번 출력됨