[211221] 코딩 테스트를 위한 투 포인터 알고리즘

모든 게시물은 macOS Monterey 12.0.1 버전 기준으로 작성하였습니다.
'이것이 취업을 위한 코딩 테스트다 with 파이썬' 토대로 작성하였습니다.

 

< 복습 >

 

• for문 쓸 때 무조건 for i in range() 가지 말고 리스트 그대로 iteration 할까도 고려하자.
• if l[i] == 0 or 1 으로 조건문 걸면 False or True로 인식해서 다 참으로 간다.(그런듯?)
• ㅣ = [] 형태로 리스트 초기화 후 for문에 l[i] 인덱싱하면 out of index 나온다.
• 리스트 sorting 할 때 l = l.sort() 하면 값 없어진다. 그냥 l.sort() 써라.
• 리스트 크기를 size(l)로 구할 수 없다. len(l)로 구해라.
• 그래프 모델링 할 때는 노드 인덱싱과 맞추기 위해 그래프의 첫 리스트를 []로 초기화한다.
• DFS는 재귀 함수 형태로 해결하고, BFS는 while queue로 반복문을 건다.
• BFS는 방문 처리하기 전에 popleft로 원소를 빼주고, 방문처리하면 append 잊지 말자.

 

---

 

투 포인터 알고리즘

 

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때

2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

 

책에서 이해하기 좋은 예를 들어주었다. "2, 3, 4, 5, 6, 7번 학생 나와봐." 보다는

"2번부터 7번까지의 학생 나와봐." 가 효율적이다. 이처럼 리스트에 담긴 데이터에

순차적으로 접근해야 할 때는 '시작점'과 '끝점' 2개의 점으로 표현할 수 있다.

 

이러한 투 포인터 알고리즘을 이용하여

'특정한 합을 가지는 부분 연속 수열 찾기'에 적용할 수 있다. 

 

 

 

 

정리하면 목표하는 숫자에 미치지 못하면 end를 늘리다가 그 숫자를 넘어버리면

start를 하나 올리면서 전체적인 숫자를 낮춰가며 count를 늘려나가는 것이다.