누구나 자료구조와 알고리즘 - (14) 공간 제약 다루기, 코드 최적화 기법

 

 

 

 

---

 

 

 

공간 복잡도의 빅 오

 

공간복잡도는 알고리즘이 얼마나 많은 메모리를 소모하는가이고, 시간복잡도는 알고리즘이 얼마나 빠른가이다. 메모리 제한이 있다면 공간 복잡도도 중요하게 고려되어야 한다. 대량의 데이터를 다루거나 메모리가 제한된 작은 장치를 프로그래밍할 때는 공간 복잡도가 정말 중요하다.

 

예를 들어, 배열을 받아 중복값이 있는지 확인해 반환하는 함수를 구현할 때 이중 루프를 사용하면 공간을 절약할 수 있지만 속도가 느리고, 해시 테이블과 루프 하나를 사용하면 속도는 빠르지만 공간을 소모한다.

 

근본적으로 각 상황마다 치소 허용 속도와 메모리 한도를 알아야 한다. 그러한 제약을 이해해야 다양한 알고리즘 중에서 고르고 선택할 수 있고 속도와 메모리 요구사항에 맞게 효율성을 유지할 수 있다.

 

 

---

 

 

코드 최적화 기법

 

1. 현재 코드의 효율성을 파악해야 한다.

빅 오 표기법과 다양한 빅 오 카테고리를 떠올려 알고리즘이 어떤 빅 오 카테고리에 속하는지 알아야 최적화에 뛰어들 수 있다.

 

2. 상상할 수 있는 최상의 빅 오를 생각한다.

현재 알고리즘의 효율성을 파악했으면 가능한 최상의 실행 시간을 가진 빅 오를 생각해야 한다. 상상 할 수 있는 최상의 빅 오란 당면한 문제에 기대할 수 있는 최상의 빅 오로 절대 달성할 수 없다고 믿는 빅 오다.

예를 들어 현재 구현이 O(N²)이고 최상의 빅 오가 O(logN)이라면 알고리즘을 그렇게 만들도록 노력해야 한다.

 

3. 어렵다면 패턴을 찾아본다.

 

4. 탐욕 알고리즘을 이용한다.

매 단계마다 그 순간에 최선처럼 보이는 방법을 고른다.

 

5. 자료 구조를 변경한다.

 

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.