투포인터 시간복잡도
42
15 asked
1. 현재 학습 진도
몇 챕터/몇 강을 수강 중이신가요? 2챕터/10강
어떤 알고리즘을 학습하고 계신가요? 링드크리스트
여기까지 이해하신 내용은 무엇인가요?
2. 어려움을 겪는 부분
어느 부분에서 막히셨나요? 투포인터 시간복잡도 부분
코드의 어떤 로직이 이해가 안 되시나요?
끝에서 k번째의 값 문제 부분에서 11분 38초 자막에 N이 매우커지면 2N과 N이라서 차이가나긴한다고 되어있는데 투포인터도 2N의 시간복잡도 아닌가요? fast가 N만큼 slow가 N-K만큼 시간복잡도가 걸리고 이것은 1번풀이에서도 동일한거 아닌가요?
왜 N값이 커지면 달라지는지 궁금합니다.어떤 개념이 헷갈리시나요?
3. 시도해보신 내용
문제 해결을 위해 어떤 시도를 해보셨나요?
에러가 발생했다면 어떤 에러인가요?
현재 작성하신 코드를 공유해주세요
이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다.
명석님, 투포인터 알고리즘의 시간복잡도에 대해 문의하신 부분에 대해 설명드리겠습니다. 투포인터 기술은 대개 O(N) 시간복잡도를 갖고 있으며, 두 포인터가 리스트를 각각 이동하며 한 번씩만 전체 리스트를 순회하기 때문입니다.
질문하신 부분에서 “N이 매우 커지면 2N과 N이라서 차이가 나긴 한다”라는 언급은 이론적인 오버헤드를 강조하기 위한 설명일 것입니다. 실질적인 계산에서는 상수 배수를 무시하고, 주로 최악의 경우를 고려하므로 큰 차이는 발생하지 않습니다.
그러나 정확한 맥락은 강의 영상의 특정 로직이나 문제 조건에 따라 차이가 발생할 수 있을 것입니다. 원활한 이해를 위해 강의나 관련 자료를 한 번 더 검토해보시면 좋을 것 같아요.
더 궁금한 점이 있다면, 고민하지 마시고 언제든지 질문해 주세요. 😊
참고 URL: 인프런 FAQ
코딩테스트 처음인데 이런 공부방법이어도 괜찮을까요
0
35
1
3-3 정렬-2 선택정렬 로직
0
30
1
링크드 리스트 끝에서 k번째 값 출력하기
0
33
1
LinkedList 과제 Fast, slow 포인터
0
43
1
수강평 작성 후 자료
0
45
2
수업교재 링크 오류
2
103
2
프로그래머스에서 제출 후 채점시 틀림ㅠ
0
119
2
1-10 알고리즘 더 풀어보기(2) 질문 있습니다
0
66
2
문제 풀이 방식 관련 질문입니다!
0
80
2
1-5 알고리즘과 친해지기 (2) - 최빈값찾기 질문 있습니다
0
82
2
수업자료 pdf 받고싶습니다
0
98
2
강의 자료 오류 수정
0
67
1
2-10 더하거나 빼거나 관련 질문입니다
0
58
2
3-8 해쉬 -2
0
45
2
Linked List Element Delete Explanation Problem
0
61
2
강의3-4 스택 탑 문제
0
73
2
코드스니펫 입출력 케이스에 오류가 있는것 같아요
0
93
3
링크드 리스트 원소 찾기 구현 방식 질문드립니다.
0
71
2
1874 - 스택 문항
0
77
2
DP Java 예제 자료형 오버플로우 문제
0
95
2
4-9 4주차 숙제중 농심라면 문제
0
103
2
DFS 에서 스택을 사용하는 이유
1
177
3
들여쓰기가 햇갈리네요
0
117
2
강의자료 5일차 11. 카카오 추가 코딩 테스트 - 4 java코드가 잘못되어 있습니다.
0
48
2