알고리즘 자습서: 샴페인 타워 설명

최근에 저는 데이터 구조와 알고리즘을 검토하고 연습했습니다. 일반적인 자습서 가이드를 보완하기 위해 내가 만난 흥미로운 문제에 대한 짧은 일련의 솔루션 연습을 시작하기로 결정했습니다.

오늘은 Leetcode (#799)의 계단식 샴페인 타워 문제를 살펴보겠습니다.

내용물

Problem Description

Problem Explanation

Modeling the Tower

Solution

문제 설명

Leetcode에서 찾을 수 있는 직접적인 문제 설명은 다음과 같습니다.

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup of champagne.

Then, some champagne is poured into the first glass at the top. When the topmost glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has its excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

기본적으로 이 문제는 폭포 캐스케이드를 모델링하고 삼각형의 각 항목이 "왼쪽 부모"와 "오른쪽 부모"의 합계인 Pascal's Triangle의 변형입니다. 여기에서 총 합계 대신 총 오버플로 합계를 계산해야 합니다.

Back to Top

문제 설명

문제 설명을 읽으면 캐스케이드 효과에 대한 감각을 얻을 수 있고 타워 맨 위에 있는 행이 그 아래에 있는 행에 어떤 영향을 미치는지 알 수 있습니다. 그러나 설명의 행/열 특성을 고려할 때 "샴페인 타워"를 배열의 배열로 생각하기 시작해야 합니다. 여기서 타워의 각 인덱스는 길이가 이전 인덱스보다 하나 더 큰 배열로 구성됩니다.
예: tower = [ [0], [0,0], [0,0,0], ... ]
이를 염두에 두고 다이어그램에 표시된 정삼각형으로 타워를 그리는 대신 각 행의 인덱스가 정렬되도록 타워를 다시 구상하고(직각 삼각형) 해당 값이 서로 어떻게 관련되는지 확인합니다. 설명에 설명된 것과 동일한 처음 4개의 쏟아짐.

One Pour:
[ 1 ], 
[ 0, 0 ], 
[ 0, 0, 0 ], 
[ 0, 0, 0, 0 ], 

Two Pours:
[ 1 ], 
[ 0.5, 0.5 ], 
[ 0  , 0  , 0 ], 
[ 0  , 0  , 0  , 0 ]

Three Pours:
[ 1 ], 
[ 1  , 1 ], 
[ 0  , 0  , 0 ], 
[ 0  , 0  , 0  , 0 ]

Four Pours:
[ 1 ], 
[ 1   , 1 ], 
[ 0.25, 0.5 , 0.25 ], 
[ 0   , 0   , 0   , 0 ]

넘치는 "부모"에 대한 "자식"안경의 인덱스를 자세히 살펴보면 받는 자식 중 하나는 동일한 인덱스를 가지며 다른 자식은 항상 현재 인덱스보다 하나 더 큰 것을 볼 수 있습니다. 이 관계는 솔루션에서 "오버플로"금액이 할당될 위치를 결정하는 데 도움이 됩니다.

두 번째 중요한 점은 앞에서 언급했듯이 아이들이 오버플로 금액의 합계를 받고(전체 합계인 파스칼의 삼각형과 달리) 이 합계가 1을 초과할 수 없으며 그렇지 않으면 오버플로가 발생한다는 것입니다. 이것은 각 잔에 대해 컵에 얼마나 많은 액체를 붓는지(직접 또는 넘침을 통해)와 잔에 얼마나 남을 수 있는지(1)를 비교하여 넘침량을 결정해야 한다는 것을 의미합니다.

이러한 아이디어를 염두에 두고 주어진 수의 타설 및 행에 대해 탑을 구성하는 함수를 작성해 봅시다. 이것은 최종 해결책이 아니거나 문제가 궁극적으로 요구하는 것이 아니지만 무슨 일이 일어나고 있는지 시각화하는 데 도움이 되는 것 같습니다.

Back to Top

타워 모델링:

이 함수는 지정된 행 번호까지 전체 탑을 구성하는 중첩된 배열을 출력하며, 각 잔의 양은 주어진 타설 횟수에 해당합니다. 기능 내의 주석은 프로세스의 각 단계를 설명합니다. 안경/줄이 어떻게 관련되어 있는지 이해하는 데 도움이 되도록 이 모델에 대해서도built a CodeSandbox visualizer

const champagneFullTower = (poured, query_row) => {
  // Initialize the tower as a nested array representing the first cup.
  // This first cup is where all of the liquid poured initially goes.
  const tower = [[poured]]

  // Iterate for each row of the tower that we are modeling.
  // Access the current row, and initialize a new array for the next row
  for (let i = 0; i < query_row; i++){
    const currentRow = tower[i]
    const nextRow = []

    /*
    Iterate through each cup in the current row, calculating its fill and overflow.
    Its fill amount cannot exceed 1, so Math.min() will check for this.
    Calculate the overflow amount by subtracting 1 from the amount available.
    Overflow amount canot be negative, so Math.max() is used to ensure this.
    */
    for (let j = 0; j < currentRow.length; j++){
      const fillAmount = Math.min(1, currentRow[j])
      const overflowAmount = Math.max(0, currentRow[j] - 1)
      /*
      The two "child cups" each receive 1/2 of the overflow amount.
      This should accumulate with any amount it received from a different parent.
      || operator is used to handle the initial undefined state of each index.

      Remember, each parent overflows to the same index below it, and index + 1
      */
      nextRow[j] = nextRow[j] + overflowAmount / 2 || overflowAmount / 2
      nextRow[j+1] = nextRow[j+1] + overflowAmount / 2 || overflowAmount / 2
      currentRow[j] = fillAmount
    }
    // Add the row we just constructed to the tower
    tower.push(nextRow)
  }
  // Return the portion of the tower we processed
  return tower.slice(0, query_row)
}

Back to Top

해결책

우리가 해결하고 있는 문제에 대해 타워 전체를 반환하고 싶지는 않습니다. 대신 주어진 행이나 열에 있는 금액을 반환하도록 요청합니다. 한 가지 방법은 원하는 유리만 반환하도록 return 문을 수정하여 반환되는 최대 값이 1이 되도록 하는 것입니다(마지막 행에 대한 오버플로를 계산하지 않았으므로). 또한 올바른 유리를 식별하기 위해 Leetcode의 query_glass 매개변수를 추가해야 합니다. 이 기능은 아무 안경이나 클릭하여 모델링됩니다on the visualizer.

const champagneTower = (poured, query_row, query_glass) => {
  const tower = [[poured]]
  for (let i = 0; i < query_row; i++){
    const currentRow = tower[i]
    const nextRow = []

    for (let j = 0; j < currentRow.length; j++){
      const fillAmount = Math.min(1, currentRow[j])
      const overflowAmount = Math.max(0, currentRow[j] - 1)
      nextRow[j] = nextRow[j] + overflowAmount / 2 || overflowAmount / 2
      nextRow[j+1] = nextRow[j+1] + overflowAmount / 2 || overflowAmount / 2
      currentRow[j] = fillAmount
    }
    tower.push(nextRow)
  }
  // Math.min() ensures 1 is the highest returned value
  return Math.min(1, tower[query_row][query_glass])
}

실제로 문제를 해결하기 위해 전체 타워를 추적할 필요가 없으므로 currentRow 및 nextRow만 추적하여 기능을 약간 단순화할 수 있습니다.

const champagneTower = (poured, query_row, query_glass) => {
  currentRow = [poured]
  for (let i = 0; i < query_row; i++){
    const nextRow = []
    for (let j = 0; j < currentRow.length; j++){
      const overflowAmount = Math.max(0, currentRow[j] - 1)
      nextRow[j] = nextRow[j] + overflowAmount / 2 || overflowAmount / 2
      nextRow[j+1] = nextRow[j+1] + overflowAmount / 2 || overflowAmount / 2
    }
    currentRow = nextRow
  }
  return Math.min(1, currentRow[query_glass])
}

Back to Top