친구녀석이 자기가 본 모 회사의 입사 프로그래밍 문제를 말해줬다.
어떤 배열이 있는데 그 배열의 원소는 음수, 양수의 값을 가지는 정수이다. 이 배열중 원소의 합이 가장큰 구간을 O(n)의 복잡도로 구하는 알고리듬을 프로그래밍 하라.
원래 이런 종류의 두뇌개발용 프로그래밍은 별로 좋아하지는 않지만, 숙제와 시험에 생성된(…) 뻘짓거리 찾기 탐지망에 딱걸려서 이리저리 생각을 해보았다.
생각해낸 방법은 딱 한번 순회는 아니지만, O(n) = O(2n) 이라고 우기고 들어가서, 다음과 같다.
- 배열을 순회하면서 구간을 음수구간의 덩어리와 양수구간의 덩어리로 나눈다.
- 구간 덩어리중 제일 큰 양수구간 덩어리를 선택한다.
- 제일큰 양수구간 덩어리를 중심으로 작은 구간으로 순회하며 값을 더한다.
- 만일 더한값이 제일큰 양수구간의 합보다 크면 제일큰 양수구간을 변경한다.
- 제일큰 양수구간 덩어리를 중심으로 큰 구간으로 순회하며 값을 더한다.
- 만일 더한값이 제일큰 양수구간의 합보다 크면 제일큰 양수구간을 변경한다.
아래는 잘 돌아가는가 확인하기 위해 루비로 짠 코드.
class RangeChunk
attr_accessor :r_start, :r_end, :r_sum
def initialize( nStart )
@r_start = nStart
@r_end = 0
@r_sum = 0
end
end
class StrangeRange
def initialize( _rangeSize = 0 )
@totalRange = Array.new( _rangeSize )
nCount = 0
@totalRange.each do | element |
# -500 ~ 500
element = 500 - rand(1000)
@totalRange[nCount] = element
print nCount.to_s + ". " + element.to_s + "\n"
nCount += 1
end
end
def selectBigRange
nCurrnetIndex = 0
nCurrnetBigRangeChunk = 0
nCurrentBigSumOfChunk = 0
bPlusRange = true
aChunkArray = Array.new
aRangeChunk = RangeChunk.new(0)
@totalRange.each do | element |
if bPlusRange
if element >= 0
aRangeChunk.r_end = nCurrnetIndex
aRangeChunk.r_sum += element
else
bPlusRange = false
# 처음을 양수구간이라고 가정했는데, 알고 보니 음수구간이었다면 그냥 음수구간으로 변경시켜주기
if aRangeChunk.r_end == nCurrnetIndex
aRangeChunk.r_sum = element
nCurrentBigSumOfChunk = element
else
aRangeChunk.r_end = nCurrnetIndex - 1
aChunkArray.push( aRangeChunk )
if aRangeChunk.r_sum > nCurrentBigSumOfChunk
nCurrentBigSumOfChunk = aRangeChunk.r_sum
nCurrnetBigRangeChunk = aChunkArray.length - 1
end
aRangeChunk = RangeChunk.new( nCurrnetIndex )
aRangeChunk.r_sum += element
end
end
else
if element >= 0
bPlusRange = true
aRangeChunk.r_end = nCurrnetIndex - 1
aChunkArray.push( aRangeChunk )
aRangeChunk = RangeChunk.new( nCurrnetIndex )
aRangeChunk.r_sum += element
else
aRangeChunk.r_end = nCurrnetIndex
aRangeChunk.r_sum += element
end
end
nCurrnetIndex += 1
end
#마지막 구간
aRangeChunk.r_end = nCurrnetIndex - 1
aChunkArray.push( aRangeChunk )
# 음수/양수구간으로 나눈게 맞는지 확인하기.
aChunkArray.each do | chunk_element |
print chunk_element.r_sum.to_s + "\n"
end
aBeforChunk = nil
aAfterChunk = nil
nNewBigSumOfChunk = nCurrentBigSumOfChunk
(nCurrnetBigRangeChunk-1).step(0, -1) do | i |
nNewBigSumOfChunk += aChunkArray[i].r_sum
if nNewBigSumOfChunk > nCurrentBigSumOfChunk
nCurrentBigSumOfChunk = nNewBigSumOfChunk
aBeforChunk = aChunkArray[i]
end
end
nNewBigSumOfChunk = nCurrentBigSumOfChunk
(nCurrnetBigRangeChunk+1).step(aChunkArray.length-1, 1) do | i |
nNewBigSumOfChunk += aChunkArray[i].r_sum
if nNewBigSumOfChunk > nCurrentBigSumOfChunk
nCurrentBigSumOfChunk = nNewBigSumOfChunk
aAfterChunk = aChunkArray[i]
end
end
nResultStartRange = aBeforChunk == nil ? aChunkArray[nCurrnetBigRangeChunk].r_start : aBeforChunk.r_start
nResultEndtRange = aAfterChunk == nil ? aChunkArray[nCurrnetBigRangeChunk].r_end : aAfterChunk.r_end
print "Big Range Start : " + nResultStartRange.to_s + ", End : " + nResultEndtRange.to_s + ". and Sum : " + nCurrentBigSumOfChunk.to_s + "\n"
end
end
if __FILE__ == $0
nRangeCount = ARGV.empty? ? 10 : ARGV[0].to_i
aSample = StrangeRange.new( nRangeCount )
aSample.selectBigRange
end
나중에 그 친구한테 들은이야기인데, 알고보니 ACM-ICPC 에서의 고전적인 문제라고 한다. ACM-ICPC 같은경우는 전혀 관심이 없었는데, 얼추 재미있는걸 하는구나… 라는 생각이 들었다.
ps. 언제 봐도.. 내 루비코드는 C++ 코드 같다. -_-
cf 댓글들
이응준 says
길다. 왜 이렇게 길어진거지?
and
줄~줄~ 길어졌지.. 생각해보니 이것저것 해줘야할게 많더라. 알고리즘만 검증하다보니 코드품질도 별로 안좋고…
루비나 파이썬이나, 이런종류의 알고리즘 검증용으로 쓰는것도 좋을듯 싶다. 요새 그래서 그래프를 한번 루비로 짜보고 있는중.
낭만고양이 says
안녕하세요? 우연히 들렀습니다.
이 문제는 Programming Pearls라는 책에도 나오는 문제입니다.
저도 같은 문제를 Ruby로 풀어본 것이 있습니다만, 한번 참고해보시기 바랍니다. 링크는 다음과 같습니다. :-)
http://www.buggymind.com/97
Programming Pearls라는 책은 시중에 “생각하는 프로그래밍”이라는 제목으로 번역이 되어 있습니다.
주제넘었습니다만, 도움이 되었으면 좋겠습니다.
건승하세요~
and
남겨주신 링크와 글 잘읽었습니다. 감사합니다.
“알고리즘을 만드는 데 있어서 중요한 것은 문제를 끊임없이 개선해 나가려는 노력”이라는 말이 제게도 크게 와닿네요.