자료구조-투 포인터

이론

📖 투 포인터?
2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 것.

문제풀이

📖 백준 2018 (🔗백준 2018 문제)

📍 시간복잡도분석으로 사용할 알고리즘의 범위를 줄여야한다.

✏ O(n) 시간복잡도알고리즘 사용.
시간제한은 2초인데 N의 최대값은 10,000,000이므로 O(nlogn)의 시간복잡도 알고리즘을 사용하게되면 제한시간이 초과될 것이다. 따라서 O(n) 시간복잡도 알고리즘을 사용해야된다.

✏ 투 포인터 사용.
시작인덱스,종료인덱스 지정하기.

✏ 투 포인터 이동원칙.
sum>N : sum=sum-start_index; start_index++;
sum==N: end_index++; sum=sum+end_index; count++:
sum<N : end_index++; sum=sum+end_index;

#시간복잡도 분석 - O(n)의 시간복잡도 알고리즘 이용 - 투 포인터
#투 포인터
#연속된 자연수의 합 -> 시작인덱스,종료인덱스 지정해서 표현

#투 포인터 이동원칙
#sum>N : sum=sum-start_index; start_index++;
#sum==N:  end_index++; sum=sum+end_index; count++:
#sum<N : end_index++; sum=sum+end_index;

import sys
input=sys.stdin.readline

n=int(input())
count=1
start_index=1
end_index=1
sum=1

while end_index != n:
	if (sum==n):
		end_index+=1
		sum+=end_index
		count+=1
	elif (sum>n):
		sum-=start_index
		start_index+=1
	elif (sum<n):
		end_index+=1
		sum+=end_index

print(count)

📖 백준 1253 (🔗백준 1253 문제)

✏ 데이터를 정렬시킨 후, 투 포인터 알고리즘 사용.

✏ 주어진 N개의 수에서 다른 두 수의 합으로 표현되는 수를 "좋은 수"라고 했으므로, 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안된다.

✏ 투 포인터 이동원칙(k=판별수,i=start_index,j=end_index)
A[i]+A[j]==k: count++;
A[i]+A[j] > k : j--;
A[i]+A[j] < k: i++;

import sys
input=sys.stdin.readline

n=int(input())
test=list(map(int,input().split()))
count=0

test.sort()

for a in range(n):
	i=0
	j=n-1
	k=test[a]

	while i<j:
		if(test[i]+test[j]<k):
			i+=1
		elif(test[i]+test[j]>k):
			j-=1
		else:
			if(i!=a and j!=a):
				count+=1
				break
			elif(i==a):
				i+=1
			elif(j==a):			
				j-=1
	
print(count)

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준