인프런 커뮤니티 질문&답변
작성한 질문수
투포인터 시간복잡도
작성
·
27
·
수정됨
0
1. 현재 학습 진도
몇 챕터/몇 강을 수강 중이신가요? 2챕터/10강
어떤 알고리즘을 학습하고 계신가요? 링드크리스트
여기까지 이해하신 내용은 무엇인가요?
2. 어려움을 겪는 부분
어느 부분에서 막히셨나요? 투포인터 시간복잡도 부분
코드의 어떤 로직이 이해가 안 되시나요?
끝에서 k번째의 값 문제 부분에서 11분 38초 자막에 N이 매우커지면 2N과 N이라서 차이가나긴한다고 되어있는데 투포인터도 2N의 시간복잡도 아닌가요? fast가 N만큼 slow가 N-K만큼 시간복잡도가 걸리고 이것은 1번풀이에서도 동일한거 아닌가요?
왜 N값이 커지면 달라지는지 궁금합니다.어떤 개념이 헷갈리시나요?
3. 시도해보신 내용
문제 해결을 위해 어떤 시도를 해보셨나요?
에러가 발생했다면 어떤 에러인가요?
현재 작성하신 코드를 공유해주세요
이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
명석님, 투포인터 알고리즘의 시간복잡도에 대해 문의하신 부분에 대해 설명드리겠습니다. 투포인터 기술은 대개 O(N) 시간복잡도를 갖고 있으며, 두 포인터가 리스트를 각각 이동하며 한 번씩만 전체 리스트를 순회하기 때문입니다.
질문하신 부분에서 “N이 매우 커지면 2N과 N이라서 차이가 나긴 한다”라는 언급은 이론적인 오버헤드를 강조하기 위한 설명일 것입니다. 실질적인 계산에서는 상수 배수를 무시하고, 주로 최악의 경우를 고려하므로 큰 차이는 발생하지 않습니다.
그러나 정확한 맥락은 강의 영상의 특정 로직이나 문제 조건에 따라 차이가 발생할 수 있을 것입니다. 원활한 이해를 위해 강의나 관련 자료를 한 번 더 검토해보시면 좋을 것 같아요.
더 궁금한 점이 있다면, 고민하지 마시고 언제든지 질문해 주세요. 😊
참고 URL: 인프런 FAQ