반응형
📌강의 정리
슬라이딩 윈도우라는 알고리즘 기법을 사용할 것이다.
슬라이딩 윈도우란 반복에서 하나의 창문처럼 구간을 설정해 그 구간을 옆으로 쭉 밀며
계산을 하는 알고리즘 기법이다.
이 문제에서는 이중포문을 사용해 슬라이딩 윈도우를 구현하면 조건이 최대값들일때
100000*500 해서 어마어마한 숫자가 나올 수 있기에 포문을 하나만 이용해서 구현한다.
그럴 경우 핵심은 하나의 윈도우에서의 값이 나오면 다음 반복에서 단순히 앞의 값은 더하고
뒤의 값은 빼주는 것이다. 이렇게 하면 하나의 반복문으로 복잡도를 늘리지 않고 이 문제를 풀 수 있다.
📌느낀점
드디어 옛날에 풀었던 부분을 다시 다 풀고 새롭게 푸는 첫번째 문제이다.
처음시작할때는 이걸 언제 다 풀어 했는데 생각보다 훨씬 빠르게 다 풀었다..
정말 매일매일 하나씩 풀어 누적하는게 효과가 어마어마하다.
이번에도 역시 강사님의 풀이는 나의 풀이를 한발 더 앞서 나아갔다.
물론 나의 풀이로도 풀리긴 하지만 복잡도가 높아 숫자조건이 높아지면 틀릴 수 있다.
하지만 강사님 풀이는 for문을 한번만 쓰기에 간결하고 효과적이다.
나도 저렇게 심플하고 적절한 풀이를 해야 한다!
//나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(k, arr) {
let answer;
let sum = 0;
let max = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < arr.length - k; i++) {
for (let j = i; j < i + k; j++) {
sum += arr[j];
}
if (sum > max) max = sum;
sum = 0;
}
answer = max;
//첫번째 반복문은 0부터 arr.length의 -k 까지 반복한다.
//이때 하나의 반복마다 k까지의 범위를 다른 반복문이 더해주어
//sum에 합치고 max와 비교하여 최대값을 누적갱신 해 나아간다.
return answer;
}
let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(k, arr) {
let answer,
sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
answer = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
answer = Math.max(answer, sum);
}
return answer;
}
let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));
</script>
</body>
</html>
반응형
'JS 알고리즘 문제풀이 > 섹션 5. 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)' 카테고리의 다른 글
| 7.아나그램(Hash Map) (0) | 2022.06.20 |
|---|---|
| 6.학급 회장(Hash Map) (0) | 2022.06.18 |
| 4.연속부분수열2(Two Pointers Algorithm) (0) | 2022.06.16 |
| 3.연속부분수열1(Two Pointers Algorithm) (0) | 2022.06.15 |
| 2.공통원소구하기(Two Pointers Algorithm) (0) | 2022.06.14 |