Inflearn Community Q&A
asked
1-H 질문입니다.
Resolved
Written on
·
42
·
Edited
0
문제 보자마자 슬리이딩 윈도우가 생각나서 해당 방법으로 구현을 했습니다 . 구간합을 이용한 문제를 푸실때 누적합으로 구현하게 하시는 이유가 궁금 합니다.
Quiz
알고리즘의 시간복잡도가 주로 측정하는 것은 무엇일까요?
알고리즘의 실제 실행 시간
입력 크기에 비례한 주요 로직의 반복 횟수
알고리즘이 사용하는 메모리 양
코드의 전체 줄 수
Answer 2
0
안녕하세요 정우님 ㅎㅎ
슬라이딩 윈도우도 괜찮습니다.
누적합 또는 슬라이딩 윈도우로 이문제를 푸는데 누적합이 코테에서 더 자주나와서 이걸 사용하고 + 이걸 개념강의로 가르치고 있습니다. ㅎㅎ
+코드리뷰
슬라이딩 윈도우 너무 잘 구현하셨네요 ㅎㅎ 잘하셨습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 임정우님.
슬라이딩 윈도우 기법으로 문제를 해결하신 것에 대해 궁금증을 가지셨군요. 슬라이딩 윈도우와 누적합은 모두 효율적인 문제 해결을 위한 기법이지만, 각기 다른 상황에서 장점을 살리며 사용할 수 있습니다.
슬라이딩 윈도우는 정해진 크기의 구간을 한 칸씩 이동시키면서 구간 내의 값을 갱신하는 방법입니다. 주로 고정 길이의 부분 합이나 평균을 계산할 때 또는 특정 구간 내에서의 최대/최소값을 빠르게 찾을 때 활용됩니다. 슬라이딩 윈도우는 O(n) 시간복잡도로 문제를 해결할 수 있는 좋은 방법입니다.
반면, 누적합은 배열의 처음부터 특정 위치까지의 합을 사전에 계산하여, 이후 구간합을 O(1)의 시간복잡도로 빠르게 계산할 수 있게 해줍니다. 누적합은 주로 여러 번의 구간합을 빠르게 계산해야 할 때 유용합니다.
즉, 누적합을 이용하면 구간의 시작점과 끝점의 차이만으로 빠르게 결과를 얻을 수 있으며, 이는 반복적으로 구간합을 요청하는 문제에서 효율적인 방법입니다.
다음 URL들은 많은 수강생들이 말한 것처럼, 여러 상황에 대한 누적합과 슬라이딩 윈도우의 장단점을 이해하는 데 도움될 것입니다:
- “1-H 문제에서 슬라이딩 윈도우와 구간합” : 누적합과 슬라이딩 윈도우의 사용에 대한 구체적인 설명과 예시.
- “6-L 질문있습니다 :)”: 실수형 데이터를 다룰 때 발생할 수 있는 오차 문제에 대해 논의합니다.
- “1-H 2559번 질문있습니다!”: 누적합을 활용한 풀이에서 발생할 수 있는 잘못된점과 수정 사항을 설명합니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.