패스트캠퍼스 챌린지 15일차

시청 날짜 : 11/15/2021
시청 강의 : 투포인터(Two Pointers)

Two Pointers

투포인터 알고리즘이란 화살표 두개에 의미를 부여해서 탐색 범위를 압축하는 방법

1차원 배열 위에 2개의 포인터를 만드는 경우

• 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동

start→
start→

10	11	18	19	54	21

-> 전형적인 double for loop

int[] arr = {10,11,18,19,54,21};
int N = arr.length;
for(int i = 0 ; i< N ; i++){ //i 포인터
    for(int j = 0 ; j< N ; j ++){ //j 포인터
        ...
    }
}

• 2개의 포인터가 양 끝에서 서로를 향해 이동
  start→ ........................ ←start

10	11	18	19	54	21

for(int i = 0 ; i < N ; i++){
    for(int j = N-1 ; j>=0 ; j--){
        ....
    }
}

관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터 값으로 표현하는 경우

Two Pointer 문제 힌트

1차원 배열에서의 "연속 부분 수열 " or "순서를 지키며 차례대로"

"곱의 최소" 문제는 투포인터 로 접근해 본다

연습문제

BOJ 1806 - 부분합

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오

 

강의에서 들은 문제 풀이 방법은 잘 이해가 클릭되지 않아서 좀 더 편해보이는 더블 for loop로 풀고싶었으나 성공하지 못했다. 후에 강의를 다시 한번 들은 후 풀어보려고 한다 ㅠㅠ

---

패스트캠퍼스 환급 챌린지 바로가기👉 https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.