-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
코드 리뷰 부탁드립니다!!
23.06.04 00:07 작성 조회수 232
0
안녕하세요 선생님!
강의를 듣기 전에 혼자 풀어보았습니다.
이중 for문으로 풀어서 시간복잡도 상으로는 좋지 않을 것 같은데 이것도 괜찮은 코드일까요?
function solution(k, arr) {
let answer = 0;
let sum = 0;
let check = 0;
for (let i = 0; i < arr.length - 2; i++) {
for (let j = 0; j < k; j++) {
sum += arr[i + j];
check += 1;
}
answer = Math.max(answer, sum);
sum = 0;
check = 0;
}
return answer;
}
let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));
답변을 작성해보세요.
0
인프런 AI 인턴
2023.06.06
안녕하세요, 인프런 AI 인턴입니다.
코드를 살펴보니 투 포인터(Two Pointer) 알고리즘을 이용한 코드 같습니다. 시간복잡도는 O(N*K)로 나쁘지 않지만, N과 K의 입력 범위에 따라서는 시간 초과가 발생할 수도 있습니다.
만약에 입력값이 큰 경우 시간 복잡도를 좀 더 줄이기 위해 다른 알고리즘을 사용할 필요가 있습니다. 한 가지 예로는 최대 부분합 알고리즘이 있습니다. 이 알고리즘을 사용하면 시간복잡도 O(N)으로 풀이가 가능합니다.
참고로, 이 문제는 백준 알고리즘(https://www.acmicpc.net/problem/2559)에서 문제로 출제되었습니다. 백준에서는 시간복잡도를 줄이기 위해서 위와 같이 최대 부분합을 이용한 풀이가 일반적입니다.
최대 부분합 알고리즘에 대해서는 구글링을 통해 자세히 공부해보시기 바랍니다.
코드 리뷰 요청해주셔서 감사합니다. 좋은 하루 되세요!
답변 2