algorithm_004_essential_twoPointer.md

필수 알고리즘 - 투 포인터

팁

처음부터 생각하기 어렵다. 쉬운 방법부터 생각해서 알고리즘을 생각하기

• O(N^2) 시간복잡도가 20억을 초과한다면
• 연속하는 특징이 있는지 체크한다.
• for문 내부 투포인터 계산하는 값의 최대값의 확인이 필요하다. ::: Int의 범위를 초과하는지 볼것
• 투포인터 문제의 종류
  • 두개 다 왼쪽에서 // 각각 왼쪽, 오른쪽 // 다른 배열
  • 일반적 ->>> O(N)
  • 정렬 후 투포인터를 하는 경우가 있음 ->>> O(NlgN)

기본문제

백준 2559 수열

범위

• 첫 번째 정수 N은 2 이상 100,000 이하
• 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다

먼저 가장 쉬운 방법으로 먼저 시작

처음 아이디어

• for 문으로 각 숫자 위치에서 이후 K개의 수를 더함
• 이때마다 최대값으로 갱신

이때마다 최대값으로 갱신

처음 시간 복잡도

For문으로 해결할 경우 O(N) 각 위치에서 K개의 값을 더함 O(K) 총 O(NK)

NK = 10만 * 10만 -> 2억을 넘어가기 때문에 시간 초과!!!

여기서 시작해야한다.

수정아이디어

연속되어있기 때문에 특징을 이용할 수 있을까?? 라는 아이디어로 투포인터를 접근해야한다.

• 처음 K개의 값을 구한다.
• For문으로 다음 인덱스의 값을 더하고, 앞의 값을 뺌
• 최대값을 갱신

수정시간복잡도

숫자 N개 만큼 For문 -> O(N) 여기서 각각의 연산에서 맨앞을 빼주고, 맨뒤를 더해주는 작업이 2개씩 들어간다. :: O(N * 2) -> O(2N)

시간복잡도 표기에서 상수를 없애면 동일하게 O(N)이 된다.

자료구조

Int타입은 언어에 따라 데이터 폭이 달라서 가능여부가 달라진다. Int, Long 같은 것들이 최대의 크기가 정해져 있는 경우가 있다.

• 전체 정수배열 : [Int]

현재 문제에서는 -100 < N < 100 :INT가 가능하다.

• 합한 수: Int
  • 100(각각 최대값) * 10만개 = 천만개 Int는 최대 20억 까지니까 가능