인프런 커뮤니티 질문&답변
작성한 질문수
인접행렬에서 탐색할때의 경우
해결된 질문
작성
·
93
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요 큰돌님! 강의를 보던중 제가 아는 지식이 이곳에 적용이 되는지 궁금해져서 질문을 남겨놓습니다.
2주차 개념 4-1 인접행렬 8:00 경에 x(순회할때 j)를 중심으로 보는것보다 y(순회할때 i)를 중심으로 보는 것이 더 좋고 그 이유가 행별로 캐싱이 된다고 하셨는데요! 이때 y(순회할때 i)를 선택하는 것이 더 좋은 이유가 자세히 생각했을 때 데이터 지역성 때문에 그런것인지 의문을 가지게 되어 질문을 남겨보아요!
답변 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)이라고 하며, 메모리 접근 패턴을 효율적으로 만들어 성능 최적화에 기여할 수 있습니다.
기존에 유사한 질문이 있었으며 이를 참고하면 더 이해에 도움이 될 수 있습니다. 관련된 내용을 확인하시고 도움이 되시길 바랍니다.
- 질문: 마지막 풀이에서 if(a[i][j] && visited[i] == 0) 이 부분이 잘 이해가 안 갑니다.
- 해당 질문에서는 행(i)을 기반으로 접근하는 경우와 관련한 논의가 포함되어 있습니다.
- 해당 질문에서는 행(i)을 기반으로 접근하는 경우와 관련한 논의가 포함되어 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.