시간복잡도,공간복잡도/투 포인터 , 슬라이딩 윈도우

시간복잡도

• 시간 복잡도 란?

시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간의 양을 나타낸다.
입력의 크기(n) 에 따라 시간이 어떻게 변하는지를 분석한다.

 

• 표기법

일반적으로 빅오 표기법(O)으로 표현한다.

◎빅오 표기법
O(n) , O(log n) , O(n^2) 등으로 표기한다.

 

공간복잡도

• 공간 복잡도 란?

공간 복잡도란 알고리즘이 실행되는 동안 사용되는 메모리의 양을 나타낸다.
입력의 크기(n) 에 따라 필요한 메모리의 양을 분석한다.

 

• 표기법

시간 복잡도와 마찬가지로 빅오 표기법(O)으로 표현한다.

---

투 포인터

 

• 투 포인터란?

투 포인터 기법은 배열의 두 위치를 동시에 탐색하여 특정 조건을 만족하는 경우를 찾는데 사용된다.

투 포인터 이해를 돕기위한 이미지

 

• 구현 방법

① . 두 포인터 초기화

배열의 시작과 끝 포인터를 초기화한다.(초기값을 준다.)

 

② . 조건에 따라 포인터 이동

두 포인터를 이동하며 조건을 확인하고 조건에 맞춰 포인터를 조정한다.

 

③ . 결과 저장

조건을 만족할 때 마다 결과를 업데이트한다.

 

슬라이딩 윈도우

 

• 슬라이딩 윈도우란?

슬라이딩 윈도우는 연속적인 요소를 다루는 문제에서 매우 유용한 기법이다.
주어진 배열이나 문자열에서 특정 조건을 만족하는 부분 배열이나 부분 문자열을 찾는데 사용된다.
윈도우의 크기를 동적으로 조정하면서 탐색한다.

슬라이딩 윈도우는 말 그대로 윈도우(창문)만큼의 값을 슬라이딩하면서 값을 탐색하는 기법이다.

슬라이딩 윈도우 이해를 돕기위한 이미지

 

• 구현 방법

① . 윈도우의 시작과 끝 포인터 정의

두 포인터 (left,right)를 사용하여 윈도우의 시작과 끝을 정의한다.

 

② . 조건에 따라 포인터 이동

오른쪽 포인터(right)를 이동하며 조건을 확인하고

조건이 맞지 않을 경우 왼쪽 포인터(left)를 이동하여 윈도우를 조정한다. 

 

③ . 결과 저장

조건을 만족할 때 마다 결과를 업데이트한다.