인접행렬에서 탐색할때의 경우

작성한 질문수 2

0

안녕하세요 범수님 ㅎㅎ

네 이는 데이터 지역성과 연관이 되어있습니다.

C++의 2차원 배열은 행 우선(row-major) 방식으로 메모리에 저장됩니다.
즉, 배열의 요소는 한 행의 데이터가 연속적으로 메모리에 저장됩니다.
예를 들어, 다음과 같은 배열을 생각해볼게요.

int arr[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

이는 메모리에 다음과 같이 저장됩니다.

[1] [2] [3] [4] [5] [6] [7] [8] [9]

이 때문에 다음과 같이 순회를 한다고 했을 때

arr[0][0] -> arr[0][1] -> arr[0][2] -> arr[1][0] ...

• 배열이 메모리에 저장된 방식과 동일한 순서로 데이터에 접근하면서 공간적 지역성을 최대한 활용하므로 캐시 효율이 높아 -> 속도가 빠르게 됩니다.

   

또한, 교안내의 다음과 같은 부분이 있는데 참고부탁드립니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

안녕하세요, 인프런 AI 인턴입니다. BeomSu Kim님.

인접행렬에서 행(i)을 중심으로 순회하는 것이 더 좋은 이유는 데이터 접근 효율성에 기인합니다. C++에서는 2차원 배열이 행 우선(row-major order)으로 메모리에 저장됩니다. 따라서 행별로 순회하면 메모리에 연속적인 공간을 읽게 되어 캐시 히트율이 높아지고, 프로그램의 실행 속도가 빨라질 수 있습니다. 이를 데이터 지역성(data locality)이라고 하며, 메모리 접근 패턴을 효율적으로 만들어 성능 최적화에 기여할 수 있습니다.

기존에 유사한 질문이 있었으며 이를 참고하면 더 이해에 도움이 될 수 있습니다. 관련된 내용을 확인하시고 도움이 되시길 바랍니다.

1. 질문: 마지막 풀이에서 if(a[i][j] && visited[i] == 0) 이 부분이 잘 이해가 안 갑니다.
   
   • 해당 질문에서는 행(i)을 기반으로 접근하는 경우와 관련한 논의가 포함되어 있습니다.
     

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.