문제 소개

코드 및 해설

주요 알고리즘: 효율적으로 부분배열 합 구하기

코드 및 해설: pdf파일로 제공

코드 개선 (피드백)

(의견-1)
크기가 2000이상인 check배열을 이용해서 루프를 돌며 check[A[i]]와 check[A[j]]를 true로 저장한다. 이후 ThisSum을 구하고 check[평균값]이 true이면 평균 원소가 있다고 판정한다. (check배열은 i가 업데이트될 때마다 새로 선언함)

<단점: 메모리가 많이 필요함>

(의견-2)
선형 탐색을 하지 않고 Balanced Binary Search Tree를 이용해서 탐색한다. 부분배열의 원소를 노드로 저장하는 것과 트리 탐색을 하는 것은 O(logn)을 만족하므로 좋은 알고리즘이 될 것이다. (BBST는 i가 업데이트될 때마다 새로 생성함)

<단점: 코드가 복잡해짐>

테스트 결과 예시

입력: n=4, 원소={3,2,1,1}

출력: 6
A[0.0], A[0,2], A[1,1], A[2,2], A[2,3], A[3,3]