✅ Udemy 강의 구매
최근에 비대면 알고리즘 스터디를 시작하게되면서 자료구조와 알고리즘 학습이 필요하다고 느껴 Udemy에서 강의를 찾던 중 평점과 수강생 수를 보고 구매하게 되었다.
자료 구조와 알고리즘 (파이썬): https://www.udemy.com/share/103C6q3@lgmo3OmWgPEDr_BRFn6VFM0cF8h-85KqSeOY3_cPUcDIEtp0VszCssXNG_7_kHfx2A==/
이 강의는 한글 자막이 지원이 안된다는 점에서, 스크립트로 한글 번역을 통해 봐야하기 때문에 시각적으로 조금 불편하다 ㅠㅠ 그래도 처음 듣는 사람이 쉽게 이해할 수 있도록 설명에 대한 예시가 귀에 쏙쏙 들어온다!
✅ 알고리즘 복잡도
알고리즘 복잡도를 알기 전에 알고리즘이란 무엇일까? 당신이 도서관에 가서 책을 빌린다고 생각해보자. 이때 도서관에는 수많은 책(데이터)들이 책꽂이에 꽂혀있고, 이 책들은 분류코드(자료 구조)에 따라 구분되어 보관되고 있다. 그리고 책을 빌리기 위해 사서에게 건네주는 절차를 알고리즘이라고 볼 수 있다. 물론 책을 빌리는 방법(대면, 무인대출 ...)은 여러가지가 있으므로 알고리즘도 다양하다고 할 수 있겠다.
그렇다면 알고리즘 복잡도는 책을 빌리는 과정이 얼마나 복잡한 지를 나타내는 척도라고 볼 수 있다.
그렇다면 아래 설명의 이해를 돕기 위해 빌리고자 하는 책의 개수를 I(Input), 빌리는 데 걸리는 시간을 H(Hour), 빌리는 데 필요한 인력 or 시스템의 메모리를 M(Memory)이라 하자.
📌 알고리즘의 표기법: Big-O(빅오), Big-θ(빅세타), Big-Ω(빅오메가)
Big-O: 알고리즘 연산 횟수의 상한을 나타내는 표기법
Big-θ: 알고리즘의 연산 횟수가 상한과 하한이 모두 동일할 때 사용하는 표기법
Big-Ω: 알고리즘의 연산 횟수의 하한을 나타내는 표기법
🚨🚨🚨 위 표기법들은 "수학적 성능 범위"를 설명하는 방식이며, 상황(최악,평균,최선)을 대표하는 것이 아니다.
📌 알고리즘 복잡도는 시간 복잡도와 공간 복잡도로 나뉘어진다.
시간 복잡도: Input 대비 Hour
공간 복잡도: Input 대비 Memory
✅ Big-O 표기법
학계에서 Big-O와 Big-θ가 주로 사용되지만, 실제 산업에서는 Big-O가 많이 쓰이고 있다. 따라서 Big-O 표기법과 시간복잡도를 기준으로 알고리즘 표기 방법에 대해 더 자세히 알아보자.
0️⃣ 시간 복잡도 간소화
O(N^2), O(N)으로 표기하며, O(N^2+2N), O(5N)이라 표기하지 않는다.
그 이유는 N이 무한대로 접근하게 된다면 최고차항에 비해 나머지항들은 실제 구현에 미비한 영향을 끼치기 때문이다. 또한, Big-O 표기법은 실행시간 값을 비교하기 위한 것이 아닌, 입력값에 따른 연산횟수의 증가율을 비교하기 위한 것임을 잊지 말자.
1️⃣ O(1)
상수 복잡도, I와 관계없이 H 동일
ex) 변수 선언, IF 문
2️⃣ O(N)
선형 시간 복잡도, I와 H 정비례
3️⃣ O(N^2)
이차 시간 복잡도, I이 이중 루프문 안에 있음
4️⃣ O(logN)
로그 시간 복잡도, 로그의 밑이 2이며, I이 늘어나도 H는 천천히 증가. I를 계속 절반으로 줄이면서 연산하는 구조
ex) 분할 정복
5️⃣ O(NlogN)
N개의 I를 처리하는 데 각 데이터를 logN 연산을 하는 경우
ex) 힙정렬, 우선순위 큐, 트리 기반 삽입/삭제, 분할 정복
6️⃣ O(2^N)
지수 시간 복잡도, I가 커질수록, 연산 횟수가 2의 N제곱만큼 증가
ex) 완전 탐색, 부분 집합, 백트래킹, 재귀 분기
🚨 연산 횟수가 기하급수적으로 증가하므로 최적화 기법이 반드시 필요
📍 복잡도 별 연산횟수 증가율 비교 그래프
✅ 클린 코드
코드를 어떻게 작성하는 게 가장 좋을까?
백준 문제를 풀기 전에 문득 이 생각이 들었다.
Python PEP - 8 (파이썬 코드 작성법): https://peps.python.org/pep-0008/
⭐️ 빈 줄
- 함수, 클래스 사이에는 2줄의 빈 줄
- 함수 내부는 1줄 정도로 블록 구분
⭐️ 띄어쓰기
x = 1
y = x + 1
- 연산자, 콤마, 콜론 앞뒤 공백을 적절히 넣어 가독성 높이기
⭐️ Import
import os
import sys
import numpy as np
from mymodule import utils
- 표준 라이브러리 -> 서드파티 -> 로컬 순서로 나눠서 작성
- 각 블록 사이에 빈 줄 하나
- 하나의 줄에 여러 개의 import를 하지 말 것
❌ import os, sys
⭐️ 주석
- 코드 설명은 #으로 시작하는 인라인 주석
- 함수/클래스 설명은 docstring("""...""") 사용
⭐️ 불필요한 코드 피하기
- 한 줄로 여러 작업 하지 말기
Case 1:
Case 2:if x > 0: print("positive")
아래와 같이 수정
if x > 0:
print("positive")
Case 3:if x == True:
아래와 같이 수정
if x:def bad(x=[]):
아래와 같이 수정
def good(x=None):
