기초부터 탄탄하게! - 알고리즘 편

오늘은 알고리즘에 대해서 공부해보겠다.

알고리즘(Algorithm)이란, 어떤 문제를 해결하기 위한 명령어들의 집합이다.
즉, "입력 → 처리 → 출력"의 과정을 정리한 논리적인 절차이다.

 

알고리즘에는 시간복잡도, 공간복잡도가 있는데 우선 시간복잡도를 먼저 알아보겠다.

 

시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 걸리는 시간의 증가율을 분석하는 개념이다.
즉, 입력 크기(N)가 커질 때, 실행 시간이 얼마나 증가하는지를 나타내는 것.

시간 복잡도는 Big-O 표기법으로 표현하며, 가장 빠르게 증가하는 항만 남기고 계수를 제거해서 나타낸다.

시간복잡도

 

그 다음은 공간복잡도이다.

 

공간 복잡도(Space Complexity)는 알고리즘이 실행될 때 필요한 메모리 공간의 양을 의미한다.
즉, 코드가 실행되는 동안 얼마나 많은 메모리를 사용하는지 분석하는 개념이다.

공간 복잡도는 고정 공간(Static Space) + 가변 공간(Dynamic Space)으로 나뉘는데

 

고정 공간(Static Space, O(1))은 입력 크기와 관계없이 항상 일정한 메모리 공간을 차지한다.
예: 변수, 상수, 고정 크기의 배열 등

고정 공간 예시

 

가변 공간(Dynamic Space, O(N))은 입력 크기에 따라 메모리 사용량이 변하는 공간이다.
예: 동적으로 할당되는 배열, 리스트, 재귀 호출 스택 등

가변 공간 예시

 

마지막으로 전체적으로 정리를 하자면

 

시간 복잡도(Time Complexity)는 알고리즘 실행 시간이 입력 크기에 따라 어떻게 변하는지 분석하는 개념
- Big-O 표기법으로 나타내며, O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) 순서로 성능이 떨어짐
- 중복 반복문 제거, 해시셋 활용, 재귀 대신 반복문 사용 등의 방법으로 최적화 가능

 

 공간 복잡도(Space Complexity)는 알고리즘이 사용하는 메모리 크기를 의미
- 고정 공간(O(1)) vs 가변 공간(O(N))
- 배열 크기, 재귀 함수 사용 여부에 따라 공간 복잡도가 달라짐
- 불필요한 변수 줄이기 + 반복문 사용하면 공간 최적화 가능