안장점

지침

이번 과제는 나무 위 집을 지을 수 있는 후보 나무를 찾는 거예요.

데이터 회사는 나무의 높이를 나타내는 격자 형태로 데이터를 제공해요. 격자의 행은 동서 방향을, 열은 남북 방향을 나타내요.

가능한 나무는 자기 행에서는 가장 크고, 자기 열에서는 가장 작은 나무예요.

어떤 격자에는 이런 나무가 하나도 없을 수도 있어요. 하나만 있을 수도 있고, 여러 개일 수도 있어요.

다음은 후보 나무가 딱 하나뿐인 격자예요.

      ↓
      1  2  3  4
    |-----------
  1 | 9  8  7  8
→ 2 |[5] 3  2  4
  3 | 6  6  7  1

• 2번째 행에는 5, 3, 2, 4가 들어 있어요. 가장 큰 값은 5예요.
• 1번째 열에는 9, 5, 6이 들어 있어요. 가장 작은 값은 5예요.

따라서 [2, 1] 지점(행: 2, 열: 1)은 나무 위 집을 짓기에 아주 좋은 자리예요.

Rust의 인덱스는 0부터 시작해요

Rust에서는 관례상 값을 순서대로 나열한 자료 구조의 각 항목에 0부터 시작하는 번호를 붙여요("인덱싱"). 이 규칙은 이 README에 있는 나머지 연습 문제 설명이 무엇이라고 하든 그대로 적용돼요. 인덱스가 1부터 시작한다고 언급되어 있더라도 마찬가지라서, 그런 인덱스 번호를 Rust의 인덱스 번호로 옮기려면 1을 빼야 해요.

효율성 관련 안내

이 연습 문제는 행렬의 내용을 저장할 때 _벡터의 벡터_를 사용해요. 이 연습 문제는 인덱싱 같은 벡터의 기본 개념과 중첩된 자료형이 가능하다는 점을 학습자가 이해하도록 돕기 위해 만들어졌지만, _벡터의 벡터_는 고성능 행렬 연산이나 더 많은 데이터를 효율적으로 처리하는 비슷한 작업에는 최선의 선택이 아니에요.

이 비효율성에 대한 자세한 설명은 이 연습 문제와 이 학습 트랙 전반의 범위를 벗어나요. 이런 측면을 캐시 지역성이라고 하는데, 현대 컴퓨터 구조의 세부 사항을 더 알고 싶다면 그 링크를 눌러서 좋은 입문 글을 찾아볼 수 있어요.

---

출처

J Dalbey의 Programming Practice problems