투포인터1 [알고리즘] - 투 포인터 (Two Pointer) 👉 투 포인터란? ▪ 어떤 값을 가리키는 두 개의 변수(포인터)를 의미한다. ▪ 주로 1차원 배열에서 순차적으로 접근할 때 사용되며, 연속합, 부분합 등에 사용된다. ▪ 두 개의 포인터 배치 방법 - 같은 방향에서 시작 - 서로 다른 방향에서 시작 (양 끝) ▪ 중첩 for문에서의 개선된 시간복잡도 : 매 루프마다 1칸씩만 이동해서 전체 순회를 마침으로, O(N^2)문제를 O(N) 시간복잡도로 해결할 수 있다. 👉 투 포인터를 써야하는 경우 ▪ 입력으로 들어오는 데이터의 크기가 매우 큰 경우 (ex. 100,000,000) ▪ 다중 for문으로 구현이 가능해 보이지만 대략적인 시간 복잡도가 매우 큰 수치로 보일 경우 👉 투 포인터 vs DP (동적 계획법) ▪ 투 포인터로 풀리는 문제여도, 입력값의 크기.. 2023. 12. 21. 이전 1 다음
