Search results for '알고리즘'

  1. 2007/11/18 -- 어느 회사의 프로그래밍 입사문제 (4)

어느 회사의 프로그래밍 입사문제

2007/11/18 15:01
4 Comments
친구녀석이 자기가 본 모 회사의 입사 프로그래밍 문제를 말해줬다.

어떤 배열이 있는데 그 배열의 원소는 음수, 양수의 값을 가지는 정수이다. 이 배열중 원소의 합이 가장큰 구간을 O(n)의 복잡도로 구하는 알고리듬을 프로그래밍 하라.

원래 이런 종류의 두뇌개발용 프로그래밍은 별로 좋아하지는 않지만, 숙제와 시험에 생성된(...) 뻘짓거리 찾기 탐지망에 딱걸려서 이리저리 생각을 해보았다.

생각해낸 방법은 딱 한번 순회는 아니지만, O(n) = O(2n) 이라고 우기고 들어가서, 다음과 같다.
1. 배열을 순회하면서 구간을 음수구간의 덩어리와 양수구간의 덩어리로 나눈다.
2. 구간 덩어리중 제일 큰 양수구간 덩어리를 선택한다.
3. 제일큰 양수구간 덩어리를 중심으로 작은 구간으로 순회하며 값을 더한다.
    3.1 만일 더한값이 제일큰 양수구간의 합보다 크면 제일큰 양수구간을 변경한다.
4. 제일큰 양수구간 덩어리를 중심으로 큰 구간으로 순회하며 값을 더한다.
   4.1 만일 더한값이 제일큰 양수구간의 합보다 크면 제일큰 양수구간을 변경한다.

아래는 잘 돌아가는가 확인하기 위해 루비로 짠 코드.

(Language : perl)
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++ 코드 같다. -_-

프로그래밍 , ,