이해되지 않는 부분이 있어서 질문드립니다.

작성자 없음

0

저도 같은 질문으로 헷갈려서 계속 파고드느라 시간이 걸렸네요..

새로 공부하시는 분들을 위해 쉽게 설명하자면,

[1, 2, 3, 1, 3] M=6으로 예를 들 때,

강사님 설명처럼 우선 왼쪽 포인터를 0으로, 오른쪽 포인터를 2(값 3)까지 쭉 최대로(M 허용 범위까지) 옮기면

1(인덱스0)에서 나올 수 있는 경우의 수는 {1}
2(인덱스1)는 {2}, {2, 1}
3(인덱스2)는 {3}, {3, 2}, {3, 2, 1}
....
이렇게 본인과 왼쪽에 있는 요소들을 한 번씩 포함한 집합들이 모이게 됩니다.

[우측 포인터 기준으로 집합 구성해서 {3}, {3,2} 이런 식입니다]

여기서 저 집합들의 개수를 구하는 게
rt - lt + 1입니다.
(배열 인덱스는 0번부터이므로 +1 처리)

다시 위 과정으로 돌아가서 가짓수 세는 라인을 추가하면,

1에서 나올 수 있는 경우의 수는 {1}
(rt - lt + 1로 이 세이브포인트에서 가짓수 누적) answer = 1

2는 {2}, {2, 1}
(rt - lt + 1로 이 세이브포인트에서 가짓수 누적)
answer = 3

3은 {3}, {3, 2}, {3, 2, 1}
(rt - lt + 1로 이 세이브포인트에서 가짓수 누적)
answer = 6
.....

따로 카운팅하지 않아도 M이 되지 않는 범위 안에서 포인터 양쪽을 쭈욱 늘리면 결국 한 번씩 돌면서 각각 가짓수를 저장하게 됩니다.

중요한건, 같은 수라고 이전에 계산한 조합들이랑 똑같은 애들이 아니예요.

앞에서 {1} , {1, 3} 이 있었다고 해도, 뒤에서 찾는 연속부분 {1} {1,3}과는 다른 존재로 칩니다.

이제 rt=3(값1)으로 한 칸 넘어가 봅시다.

일단 sum에 1을 더하면 |1,2,3,1|(인덱스 0~3)의 합이 7이 되어 M(6)을 초과합니다.
그래서 왼쪽(lt)을 한 칸 당겨줍니다 → lt=0에서 1로.
이제 |2,3,1|(인덱스 1~3), 합=6으로 M 이내가 됩니다.

이 시점(rt=3)에서 새로 추가되는 건, 끝점이 인덱스3(값1)인 부분배열들뿐입니다.

{1}, {1,3}, {1,3,2} → 3개

rt - lt + 1 = 3 - 1 + 1 = 3 → answer = 6 + 3 = 9

다음 rt=4(값3)으로 옮기고, 옮겨서 for문 종료때까지 반복합니다.

헷갈릴 만한 부분은, 카운트를 따로 세지 않아도, 끝점, lt rt를 활용해서 범위 안에서 본인을 포함하는 수열들만 구해도 카운팅된다는 점과,

앞에서 구한 수열과 뒤에서 찾은 수열은 다른 존재(중복되지않는 조합 구하는게 아님!)라는 점입니다.

저도 결국은 말이 길어졌지만 헷갈리셨던 분들 이해에 도움이 됐으면 합니다 :)

0

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

wodms4525님, 자바스크립트 알고리즘 문제풀이 입문 강의 관련하여 이해가 안 되는 부분이 생겼을 때, 먼저 유사한 질문이 있는지 확인해보시는 것이 좋습니다. 강의의 Q&A 섹션에서 유사한 문제에 대한 토론이 있을 수 있기 때문입니다.

질문해주신 rt-lt+1의 값이 카운트해야 하는 값과 일치하는 이유는 문제의 특정 상황에 따라 다르겠지만, 보통은 슬라이딩 윈도우 또는 투 포인터 알고리즘에서 두 인덱스(rt와 lt) 사이의 원소 개수를 계산할 때 사용됩니다. 여기서 rt는 오른쪽 포인터, lt는 왼쪽 포인터를 의미하며, 구간 내 원소의 개수를 구할 때는 rt - lt + 1을 계산하여 구합니다. 이 식은 lt부터 rt까지의 원소 개수, 즉 ‘오른쪽 인덱스 위치 - 왼쪽 인덱스 위치 + 1’로 구할 수 있는데, 인덱스가 0부터 시작한다고 가정할 때 두 지점 사이 구간의 원소 개수를 올바르게 계산하기 위해 1을 더하는 것입니다.

구체적인 코드의 맥락이나 해당 알고리즘의 작동 방식을 정확히 이해하기 위해서는 주어진 코드의 전체적인 로직을 살펴보아야 합니다. 코드의 전체적인 구조를 분석하면 어떤 이유로 rt-lt+1이 사용되었는지 더 명확하게 이해하실 수 있을 것입니다.

직접적으로 궁금한 점을 해결하기 위해선 강의 페이지 내의 수강 전 문의 게시판을 이용하시거나, 강의 해당 섹션의 ‘질문하기’ 기능을 사용하여 강의 제작자 또는 다른 수강생들에게 질문을 남길 수 있습니다. 인프런의 지식공유자님이나 다른 수강생들이 도움을 줄 수 있을 것입니다.

도움이 필요할 경우, 인프런의 1:1 문의하기 기능을 이용하시면 빠른 도움을 받으실 수 있습니다.

코드 이해에 도움이 되셨길 바라며, 알고리즘 학습에 성공적인 결과가 있기를 기원합니다!