자료구조(3): 투 포인터, 슬라이딩 윈도우, 스택과 큐

투 포인터

2개의 포인터(ex. 시작 인덱스와 종료 인덱스)를 지정하여 알고리즘의 시간 복잡도를 최적화한다.

 

슬라이딩 윈도우

2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하여 문제를 해결한다.

 

 

 

스택

삽입 및 삭제가 후입선출로 이루어지는 자료구조이다. (한 쪽만 뚫려있는 통이라고 생각)

가장 늦게 들어온 값이 맨 끝에 위치하며, 값을 빼낼 때도 가장 끝에 위치한 값이 먼저 나온다.

삽입 및 삭제가 일어나는 가장 끝 부분을 top 이라고 한다.

※ 스택은 깊이 우선 탐색, 백트래킹 종류의 코딩 테스트에 효과적이다.

 

큐

삽입 및 삭제가 선입선출로 이루어지는 자료구조이다. (양 옆이 뚫려있는 통이라고 생각)

가장 먼저 들어온 데이터가 가장 먼저 나간다.

가장 앞의 데이터를 front, 가장 끝의 데이터를 rear 라고 한다. (append하면 rear 부분에 새로운 데이터가 삽입되고, popleft하면 front 부분의 데이터가 삭제, 확인된다.)

※ 큐는 너비 우선 탐색에서 자주 사용된다.