방향 그래프의 역간선을 별도로 저장합니다. 역탐색 이점과 동시 갱신·메모리 비용은 어떻게 맞추나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

역방향 adjacency는 predecessor 조회·양방향 탐색·진입 차수 갱신을 빠르게 하지만 같은 간선을 두 표현에 유지하는 쓰기 비용이 듭니다. 삽입·삭제가 양쪽에 일관되게 반영되어야 합니다.

단일 writer·락·불변 snapshot 등으로 독자가 반쪽 갱신을 보지 않게 합니다. 중복 간선·자기 간선·삭제 tombstone의 의미를 맞춥니다. 실제 역조회 빈도와 메모리·cache·재구축 비용을 비교합니다.

이해가 드러나는 지점을 확인해 보세요.

역방향 adjacency는 predecessor 조회·양방향 탐색·진입 차수 갱신을 빠르게 하지만 같은 간선을 두 표현에 유지하는 쓰기 비용이 듭니다. 삽입·삭제가 양쪽에 일관되게 반영되어야 합니다.
실제 역조회 빈도와 메모리·cache·재구축 비용을 비교합니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 역방향 adjacency는 predecessor 조회·양방향 탐색·진입 차수 갱신을 빠르게 하지만 같은 간선을 두 표현에 유지하는 쓰기 비용이 듭니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.

답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.