投稿した質問数 15

0

명석님 좋은 질문 감사합니다!

1. 연산량 관점에서 명석님 분석이 맞습니다

포인터가 몇 번 움직이는지 세보면 다음과 같습니다

1번 풀이 (길이 먼저 세기):

• 1단계: cur이 끝까지 가면서 길이 세기 → (N−1)번 이동

• 2단계: cur이 end_length만큼 이동 → (N−K)번 이동

• 총 포인터 이동 = 2N − K − 1

2번 풀이 (투포인터):

• 1단계: fast를 K번 먼저 이동 → K번

• 2단계: slow, fast가 같이 이동 → (N−K)번인데 둘 다 움직이니까 2×(N−K)번

• 총 포인터 이동 = K + 2(N−K) = 2N − K

보시면 알겠지만, 포인터 이동 횟수만 세면 둘 다 대략 2N입니다.

2. "2N vs N"은 "루프 순회 횟수" 관점입니다

같은 내용을 "루프를 몇 번 도는가"로 바꿔서 세면 이야기가 달라져요.

1번 풀이: while 루프 (N−1번) + for 루프 (N−K번) → 루프 iteration ≈ 2N번 2번 풀이: for 루프 (K번) + while 루프 (N−K번) → 루프 iteration ≈ N번

즉, "루프 한 바퀴"라는 단위로 세면 2번 풀이가 절반이에요. 다만 2번 풀이는 한 iteration 안에서 포인터를 두 개 움직이니까, 실질적인 연산량은 1번 풀이랑 비슷해지는 거죠. "2N과 N 차이가 난다"고 표현하신 건 아마 이 루프 횟수 관점이었는데,제가 오해를 사게 말씀드린 것 같습니다 🙇

3. Big-O로는 둘 다 똑같이 O(N)입니다

결국 빅오 표기법은 상수항을 무시하는 규칙이라, 2N이든 N이든 N−K든 다 O(N)으로 묶여요. 그래서 코딩테스트에서 시간복잡도를 물어보면 두 방법 모두 "O(N)"이라고 답하는 게 정답입니다.

그렇다면 투포인터가 주는 진짜 이점은 뭘까요. 크게 두 가지입니다

첫째, 순회 한 번 만에 끝난다는 구조적인 우아함이 있어요. 스트리밍 데이터나 한 번밖에 못 읽는 데이터에서는 이게 결정적인 차이가 됩니다. 링크드 리스트 문제에서는 체감이 작지만, 파일이나 스트림을 다루는 실전 상황에서는 "두 번 읽기"가 아예 불가능한 경우도 많아요.

둘째, 투포인터 자체가 하나의 문제 풀이 패턴이에요. 슬라이딩 윈도우, 정렬된 배열에서 합 구하기, 회문 판별 등 여러 문제에서 훨씬 큰 효율 개선을 만들어내는 기법이거든요. 이 "끝에서 K번째" 문제는 투포인터를 연습하기 위한 문제지, 투포인터가 압도적으로 빠른 문제는 아니에요.

넘넘 좋은 질문 + 고민 감사합니다! 교재내에 해당 내용은 추가해두도록 하겠습니다 덕분에 더 좋은 강의를 제공할 수 있을 것 같아요 감사합니다!! 좋은 하루 보내시길 바랍니다

0

안녕하세요, 인프런 AI 인턴입니다.

명석님, 투포인터 알고리즘의 시간복잡도에 대해 문의하신 부분에 대해 설명드리겠습니다. 투포인터 기술은 대개 O(N) 시간복잡도를 갖고 있으며, 두 포인터가 리스트를 각각 이동하며 한 번씩만 전체 리스트를 순회하기 때문입니다.

질문하신 부분에서 “N이 매우 커지면 2N과 N이라서 차이가 나긴 한다”라는 언급은 이론적인 오버헤드를 강조하기 위한 설명일 것입니다. 실질적인 계산에서는 상수 배수를 무시하고, 주로 최악의 경우를 고려하므로 큰 차이는 발생하지 않습니다.

그러나 정확한 맥락은 강의 영상의 특정 로직이나 문제 조건에 따라 차이가 발생할 수 있을 것입니다. 원활한 이해를 위해 강의나 관련 자료를 한 번 더 검토해보시면 좋을 것 같아요.

더 궁금한 점이 있다면, 고민하지 마시고 언제든지 질문해 주세요. 😊

참고 URL: 인프런 FAQ