코딩테스트 - 패스트캠퍼스 챌린지 29일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 두 포인터 (Two Pointers)

학습 후기
두 포인터 - 화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법
1. 1차원 배열 위에 2개의 포인터를 만드는 경우
1) 2개의 포인터가 모두 왼쪽에서 시작하여 같은 방향으로 이동
2) 2개의 포인터가 양 끝에서 시작하여 서로를 향해 이동
2. 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우

문제에서의 키워드
1차원 배열에서의 연속 부분 수열 or 순서를 지키며 차례대로
곱의 최소 A * B, A가 커지면 B는 작아짐
이런 키워드가 나오면 두 포인터로 접근해볼 만하다.

이번 강의에서 풀어본 문제
https://www.acmicpc.net/problem/1806

1806번: 부분합

시간제한 (0.5초) - Java (1초)
문제 풀기 전 변수
문제에서 연속된 수의 부분합의 범위 S를 0 < S <= 100,000,000이고 수열의 각 원소들이 10,000 이하의 자연수이기에 int 값으로 처리 가능하다.
시간 복잡도 계산
1) 완전 탐색
첫 번째 자리부터 시작해서 부분합 S를 넘을 때까지 2, 3,... N까지 더하고, 두 번째 자리부터 시작해서 부분합 S를 넘을 때까지 3, 4,... N까지 더해서 완전 탐색으로 구하면 이때 시간 복잡도는 O(N^2)이 나올 수 있으며 N이 10만으로 최대일 경우 10만 * 10만 = 10,000,000,000 100억으로 1초에 1억 번 계산한다면 시간 복잡도가 초과된다. 따라서 이 방법으로는 풀 수 없다.
2) 두 포인터
위에서 설명한 키워드 중 연속 부분 수열이 나왔으므로 두 포인터 방법을 문제에 적용하여 풀어본다.
왼쪽 시작 L의 이동 횟수 N번, 오른쪽 끝을 R로 두었을 때 이전의 R부터 시작해서 이동, L, R이 각자 최대 N번 이동하기에 시간 복잡도는 O(N)이고 N이 최대 10만 번이라고 하더라도 시간제한에 걸리지 않고 충분히 가능하다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

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