매트릭스 루핑: 이제 단일 루프로

나는 이전에 함께 일했고 항상 실행 시간을 줄이는 방법이 궁금했습니다. 내가 일반적으로 행렬 문제를 해결하는 방법은 값을 추출하기 위해 중첩 루프를 작성하는 것이었습니다. 그러나 이 방법은 가장 효율적이지 않은 On^2 런타임을 남깁니다.

문제

오늘 저는 매트릭스 문제에 다른 접근 방식을 요구하는 문제를 발견했습니다.

기본적으로 나는 행렬의 대각선의 합을 찾는 임무를 받았습니다. 1에서 9까지의 숫자 범위가 주어지면 왼쪽 상단의 합은 1 + 5 + 9 = 15이고 오른쪽 상단의 합계는 3 + 5 + 7 = 15입니다.



배열을 탐색하려는 나의 첫 번째 본능은 모든 값에 대한 액세스를 제공하는 중첩된 for 루프였습니다.

let (i = 0; i < matrix.length; i++{
    let (j = 0; j < matrix[i].length; j++){
    //add up the totals
    }
}

그러나 나는 그것이 필요하지 않다는 것을 빨리 깨달았습니다. 그런 다음 모든 값이 필요하지 않고 대각선만 필요합니다.

패턴 시각화

이 시점에서 프로그램이 값을 보는 방식(배열의 인덱스)으로 값을 기록하는 것이 도움이 되었습니다.

왼쪽 상단 값의 경우 matrix[0][0], matrix[1][1], matrix[2][2]를 사용하여 액세스할 수 있습니다.

오른쪽 상단 값의 경우 matrix[0][2], matrix[1][1], matrix[2][0]을 통해 액세스할 수 있습니다.

이 단계는 문제를 이해하는 데 매우 도움이 되는 것으로 판명되었습니다. 왼쪽 값의 패턴을 보면 값이 매번 1씩 증가하는 것을 볼 수 있습니다. 왼쪽 상단의 경우 첫 번째 부분이 1씩 증가하고 후반부는 1씩 감소합니다.

이러한 모든 값이 동일한 값만큼 증가(또는 감소)하므로 하나의 for 루프만 사용할 수 있습니다.

하나의 for 루프

위의 패턴에서 우리가 이미 알고 있는 것을 감안할 때 문제의 왼쪽을 다루는 것은 쉽습니다. 0,0에서 시작하여 매번 1을 더하기만 하면 됩니다. 행렬의 각 행을 순회할 때 for 루프를 사용하여 이 작업을 수행할 수 있습니다.

for (let i = 0; i < matrix.length; i++){
    left += matrix[i][i]
}

오른쪽의 전반부는 동일합니다. i를 사용하여 행렬의 각 행을 증가시킬 수 있습니다.

두 번째 부분에서는 행렬 및/또는 행의 길이가 필요합니다(이 행렬의 행 수가 열 수와 같다고 가정).

행의 길이가 필요한 이유는 무엇입니까? 행의 길이인 행의 끝에서 시작해야 합니다.

이를 염두에 두고 패턴을 다시 살펴보겠습니다: [0][2], [1][1], [2][0].

행의 길이가 3이므로 2에서 시작하려면 1을 빼야 합니다. 그런 다음 매번 i를 빼면 됩니다. 첫 번째 반복에서 i가 0에서 시작하므로 2로 끝납니다.

여기에 전체 문제가 있습니다. 코드를 DRYer로 만들기 위해 변수를 약간 변경했습니다.

  let row = arr.length
  let left = 0, let right = 0

  for(let i = 0; i < row; i++){
    left += arr[i][i]
    right += arr[i][row - 1 - i]
  }

요약

중첩된 for 루프를 사용하여 값을 가져오는 대신 단일 for 루프를 사용하여 필요한 값만 가져올 수 있습니다. 이렇게 하면 런타임이 O^n으로 단축됩니다.

이와 같은 문제에 접근하는 가장 유용한 방법은 아마도 프로그램이 볼 수 있는 값을 기록하는 것입니다. 그렇게 하면 패턴을 볼 수 있습니다(그리고 하나의 루프가 제대로 작동한다는 것을 깨달을 수 있습니다).

hackerrank에서 이 문제를 찾을 수 있습니다.