연속된 부분 서브 배열의 합이 k가 되는 경우 mujugi 안녕하세요~ 또 고민을 해보다가 질문이 생겨서 글을 씁니다 어떤 순서 집합이 있을 때 2수를 집어서 원하는 수를 만드는 알고리즘은 O(n)에 해결 할 수 있겠는데요 3수는 O(n^2) 이 걸리더라군요 (최적인지 모르곘습니다) 조금 더 확장해서 어떤 순서의 집합이 있을때 임의의 서브집합의 합 값이 0 인지 확인해보는 알고리즘을 짜봤더니 O(n)이 걸리더라구요 요기에서 약간 더 확장해서 어떤 순서의 집합이 있을때 임의의 서브집합의 합 값이 k 인지 확인해보려는 알고리즘을 짜보려니까 O(n^2)에서 진도를 못나가겠습니다 이문제의 최적 하한이 얼마인지 궁금합니다 (단 음수가 없다고 가정하면 O(n)으로 할 수 있겠더라구요) 예제 a = [1,-3,3,-6,4-2,7,2] k = -5 sub = [1,-3,3,-6] 또한 지정된 수가 아닌 없으면 지정된 수와 최대한 가까운 혹은 최대한 먼 이렇게 바꾸면 문제의 난이도가 확변하던데 쉽게 할 수 있는 방법이 있을까요 11년 전
7개의 댓글이 있습니다. Kureyo [0,i]까지의 합을 S(i)라고 하면, [i,j]까지의 합이 k가 되기 위해서는 S(j)-S(i-1)=k여야 할테죠 ( S(-1)=0이라고 정의합시다 ) [0,i-1]까지의 S(x)값들을 stl set에다 넣고 내 S(i)에 대해 k-S(i)를 그 안에서 찾으면 O(n lg n)이 가능하지않을까요? 11년 전 link astein Kureyo// 좋아요 'ㅅ'b 그런데 k - S(i)가 아니라 S(i) - K 인 것 같음! :) 11년 전 link Being 존재성 확인만 하면 되니까 해쉬에 박으면 O(n)이겠네요~ 11년 전 link mujugi 아 덕분에 해결 했습니다 해시를 쓸경우 O(n) 까지 줄어드는군요 j가 이전까지 누적해둔 S라고 보고 i가 새로 증가시키는 인덱스라고 했을 때 S(i) = K+S(j)가 해시에 있는지 보면되네요 감사합니다 ^^ 11년 전 link mujugi Being // 1초 늦었네요 ㅎㅎ 11년 전 link sven 서브 집합이라는게 원래 집합에서 연속된 수들의 집합인가요? 11년 전 link mujugi 좀 더 명시적으로 이야기 했어야하는데 제가 쓴 포스트에선 그렇습니다 일반적으로는 부분집합이니까 순서가 상관없을것 같습니다 :) 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
mujugi
안녕하세요~
또 고민을 해보다가 질문이 생겨서 글을 씁니다
어떤 순서 집합이 있을 때
2수를 집어서 원하는 수를 만드는 알고리즘은
O(n)에 해결 할 수 있겠는데요
3수는 O(n^2) 이 걸리더라군요 (최적인지 모르곘습니다)
조금 더 확장해서
어떤 순서의 집합이 있을때
임의의 서브집합의 합 값이 0 인지 확인해보는 알고리즘을 짜봤더니
O(n)이 걸리더라구요
요기에서 약간 더 확장해서
어떤 순서의 집합이 있을때
임의의 서브집합의 합 값이 k 인지 확인해보려는 알고리즘을 짜보려니까
O(n^2)에서 진도를 못나가겠습니다
이문제의 최적 하한이 얼마인지 궁금합니다
(단 음수가 없다고 가정하면 O(n)으로 할 수 있겠더라구요)
예제
a = [1,-3,3,-6,4-2,7,2]
k = -5
sub = [1,-3,3,-6]
또한 지정된 수가 아닌
없으면 지정된 수와 최대한 가까운 혹은 최대한 먼
이렇게 바꾸면 문제의 난이도가 확변하던데
쉽게 할 수 있는 방법이 있을까요
11년 전