SY DevLog

투 포인터 알고리즘 - 다른 방향 배열에서 두 원소의 합이 어떠한 값 X와 일치하는 경우의 수를 구할 때 사용하는 알고리즘 단, 다른 방향 진행 방법에서는 배열이 정렬된 상태에서 가능하다. 배열이 2개가 존재할 때, 배열 하나는 포인터가 왼쪽에서부터 시작하여 오른쪽으로 이동하고 다른 하나는 포인터가 오른쪽에서부터 시작하여 왼쪽으로 이동한다. 배열을 1개 사용할 때, start 포인터가 왼쪽에서 하나씩 증가하고 end 포인터가 오른쪽에서 하나씩 감소했던 것과 동일한 방식이다. 사실 배열이 한 개든, 두 개든 알고리즘 자체는 동일한데, 그냥 분리해서 이해하고자 따로 다뤘다. 투 포인터 알고리즘 - 다른 방향(배열 1개일 때) 투 포인터 알고리즘 - 2. 다른 방향(배열 1개) 투 포인터 알고리즘 - 다른 방..

투 포인터 알고리즘 - 다른 방향 배열에서 두 원소의 합이 어떠한 값 X와 일치하는 경우의 수를 구할 때 사용하는 알고리즘 단, 다른 방향 진행 방법에서는 배열이 정렬된 상태에서 가능하다. 같은 방향으로 진행되는 투 포인터 알고리즘은 다른 포스팅에서 참고하면 된다. 투 포인터 알고리즘 - 같은 방향 투 포인터 알고리즘 - 1. 같은 방향 투 포인터 알고리즘 포인터 두 개를 이용하여 문제를 해결하는 방법 전체 배열에서 연속하는 부분합(구간합)이 특정값 M와 일치하는 경우의 수를 구할 때 사용 만약에 연속하는 부분합을 구하는 lotuslee.tistory.com 다른 방향으로 진행하는 알고리즘은, 1. 하나의 배열을 사용하는 방법과 2. 두 개의 배열을 사용하는 방법이 있다. 반복문 탈출조건이 약간 다르긴 ..

투 포인터 알고리즘 포인터 두 개를 이용하여 문제를 해결하는 방법 전체 배열에서 연속하는 부분합(구간합)이 특정값 M와 일치하는 경우의 수를 구할 때 사용 만약에 연속하는 부분합을 구하는 문제에서 투 포인터 알고리즘을 사용하지 않으면, 이중 반복문이 필요하기 때문에 시간복잡도가 O(N²) 가 된다. 그러나 투 포인터 알고리즘을 사용하면 O(N) 으로 줄일 수 있음 투 포인터 알고리즘은 크게 1. 두 포인터가 같은 방향으로 진행하는 방법 2. 두 포인터가 다른 방향으로 진행하는 방법 두 가지로 나눌 수 있다. 이번에는 우선 두 포인터가 같은 방향으로 진행하는 방법에 대해 다룰 것이다. 투 포인터 알고리즘 시간복잡도 : O(N) 투 포인터 알고리즘에서 필요한 프로퍼티 : - 부분합의 시작 인덱스를 가리키는 ..