투 포인터

[Algorithm][투 포인터] LeetCode 3 - Longest Substring Without Repeating Characters

알고리즘 분류 Two Pointer 시간 복잡도 \( O(N) \) 문제 링크 https://leetcode.com/problems/longest-substring-without-repeating-characters/ 관련 글 [Algorithm 문제 풀이/백준] - [Algorithm][투 포인터] 백준 1806 - 부분합 이번 문제의 알고리즘 종류는 투 포인터입니다. 투 포인터는 이전 글에서도 다른 문제로 한번 접했습니다. 개념도 단순하고 코드도 상당히 짧지만, 알고리즘을 모른다면 쉽게 풀지 못하는 문제이기도 합니다. 해당 문제는 서로 다른 부분 문자열 중 가장 길이가 긴 것을 찾아야 합니다. 만약 이것을 이중 for문을 이용한다면 당연스럽게도 시간 복잡도는 \( O(N^2) \) 이므로 상당히 비효..

[Algorithm][투 포인터] 백준 1806 - 부분합

알고리즘 분류 투 포인터 시간 복잡도 \( O(N) \) 문제 링크 https://www.acmicpc.net/problem/1806 이번 문제의 알고리즘 종류는 투 포인터입니다. 주어진 배열에서 조건을 만족하는 연속된 수들 중 가장 짧은 길이를 알아야 합니다. 문제의 제목은 부분합이지만 실제로 이 문제를 푸는데 지난번에 다뤘던 부분합 알고리즘이 사용되진 않습니다. 왜냐하면 부분합 알고리즘은 각 지점마다 누적된 합을 구해놓고 특정 구간의 합만 구하면 되지만 이번 문제는 조건을 만족하는 모든 구간을 알아봐야하기 때문입니다. 투 포인터의 핵심은 "배열이 끝날 때까지 크면 줄이고 작으면 늘린다"입니다. 투 포인터는 배열을 처음부터 탐색하게 되는데 특정 구간의 시작점을 나타내는 S와 끝 지점을 나타내는 E가 있..