게시글
질문&답변
이해되지 않는 부분이 있어서 질문드립니다.
저도 같은 질문으로 헷갈려서 계속 파고드느라 시간이 걸렸네요.. 새로 공부하시는 분들을 위해 쉽게 설명하자면,[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 = 12는 {2}, {2, 1}(rt - lt + 1로 이 세이브포인트에서 가짓수 누적)answer = 33은 {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
- 댓글수
- 2
- 조회수
- 387
질문&답변
4분쯤 인텔리제이 실행버튼이 생기지 않습니다.
저도 Junit이 기본 실행으로 잡혀있어서 실행이 안됐는데 구글링해서 해결했네요! https://ottl-seo.tistory.com/entry/%EC%9D%B8%ED%85%94%EB%A6%AC%EC%A0%9C%EC%9D%B4-Run-%EC%8B%A4%ED%96%89-%EC%95%88-%EB%90%A0-%EB%95%8C-%ED%95%B4%EA%B2%B0-%EB%B0%A9%EB%B2%95이 분 블로그대로 Run Configuration에서 어플리케이션을 새로 추가해서 기존에 쓰던걸로 다시 맞춰주시면 Run됩니다!!
- 좋아요수
- 0
- 댓글수
- 2
- 조회수
- 781




