Bellman Ford 알고리즘: 코딩 인터뷰 가이드

TL;DR: Bellman Ford 알고리즘은 일부 간선의 가중치가 음수인 경우에도 가중치가 부여된 방향 그래프에서 단일 소스 최단 경로를 찾습니다. 소스 거리를 0으로 초기화하고 다른 모든 거리를 무한대로 초기화하고 모든 가장자리를 V - 1회까지 완화한 다음 한 번의 추가 패스를 만듭니다. 추가 개선이 있으면 도달 가능한 음의 가중치 사이클이 존재한다는 것이 증명됩니다.

Bellman Ford 알고리즘이란 무엇입니까?

Bellman Ford는 동적 프로그래밍 스타일의 최단 경로 알고리즘입니다. 첫 번째 전체 패스 이후 가장 잘 알려진 경로는 최대 하나의 가장자리를 사용합니다. 두 번째 이후에는 최대 두 개의 가장자리입니다. 단순 경로에는 최대 V - 1 에지가 포함되며, 이는 루프 수와 정확성 인수를 모두 설명합니다. Dijkstra의 알고리즘과 달리 Bellman Ford는 음이 아닌 가장자리 가중치를 가정하지 않습니다.

가장자리 완화를 어떻게 설명합니까?

가중치 w를 갖는 u에서 v로의 간선에 대해 완화는 거리[u] + w가 거리[v]보다 작은지 여부를 묻습니다. 사용자에게 접근할 수 있을 때만 추가를 수행하세요. 후보가 더 좋으면 거리[v]를 업데이트하고 선행자[v]를 u로 설정합니다. 이전 배열은 거리에 대한 선택 사항이지만 실제 경로를 재구성하고 결과를 명확하게 설명할 수 있습니다.

인터뷰에서 Bellman Ford를 어떻게 추적합니까?

작은 그래프를 사용하고 패스당 하나의 거리 행을 작성합니다. 소스 A는 0에서 시작하고 다른 모든 정점은 무한대에서 시작합니다. 일관된 순서로 전체 에지 목록을 스캔하고 각 업데이트를 기록합니다. 전체 패스에 아무런 변화가 없으면 일찍 중지하십시오. 도달 가능한 음수 사이클이 존재하지 않는 경우 가장자리 순서는 중간 행을 변경할 수 있지만 최종 정확한 거리를 변경할 수는 없음을 명시하십시오.

어떤 의사 코드를 작성해야 합니까?

거리 및 선행 배열을 생성한 다음 전체 가장자리 스캔 V 마이너스 1회를 반복합니다. 조기 종료를 위해서는 변경된 플래그를 사용하세요. 마지막으로 모든 가장자리를 다시 한 번 스캔하고 도달 가능한 거리가 여전히 개선될 수 있으면 음수 주기를 보고합니다. 프로덕션 코드에서는 경로 합계를 보유하고 추가하기 전에 무한대 감시자를 보호할 수 있는 숫자 유형을 선택합니다.

시간과 공간의 복잡성은 무엇입니까?

표준 인접 가장자리 목록 구현은 V에서 1회 패스와 1회 탐지 패스 각각에서 E 에지를 스캔할 수 있기 때문에 O(VE) 시간에 실행됩니다. 거리와 선행자를 위해 O(V) 보조 공간을 사용합니다. 조기 중지는 유리한 입력을 향상시키지만 최악의 경우 한계는 O(VE)로 유지됩니다.

언제 Dijkstra 대신 Bellman Ford를 선택해야 합니까?

음의 에지 가중치가 허용되거나 면접관이 도달 가능한 음의 사이클 감지를 명시적으로 요청하는 경우 Bellman Ford를 선택하십시오. 일반적으로 더 빠르기 때문에 간선 가중치가 모두 음수가 아닌 그래프에 대한 우선순위 대기열이 있는 Dijkstra를 선택하십시오. 모든 쌍의 최단 경로의 경우 먼저 그래프 밀도, 음수 가중치 및 경로가 필요한지 또는 거리만 필요한지 여부를 명확히 합니다.

어떤 실수를 피해야 합니까?

도달할 수 없는 정점에서 긴장을 풀거나, 음의 에지를 음의 사이클과 혼동하거나, 모든 음의 사이클이 결과를 무효화한다고 주장하지 마십시오. 소스에서 도달할 수 있는 사이클만 최단 경로에 영향을 미칩니다. 또한 V - 2 패스만 실행하거나, 최종 감지 패스를 건너뛰거나, 선행 항목을 유지하지 않고 경로를 재구성하는 것을 피하세요.

설명을 어떻게 연습할 수 있나요?

30초 정의, 2분 정확성 설명, 전체 구현의 세 가지 버전을 연습하세요. 도달할 수 없는 정점, 순환이 없는 하나의 음수 간선, 도달 가능한 음수 순환 및 조기에 안정화되는 그래프를 테스트합니다. 이는 암기된 코드와 진정한 이해를 분리합니다.

AI를 사용하여 이미 이해한 자료를 정리하고, 설명을 연습하고, 성과를 검토하세요. 고용주와 평가 제공자의 규칙을 따르고 경험, 숫자 또는 결과를 꾸며내지 마십시오.

AI 면접 부조종사 가이드, 이력서 기반 준비, 면접 후 검토 워크플로를 계속 진행하세요.

자주 묻는 질문

대본이 아닌 증거로 연습하세요

YesToTheOffer는 이력서, 역할 설명 및 개인 메모에 기초 준비와 실시간 답변 구조를 제공한 다음 인터뷰 후 검토를 위해 성적표를 보존할 수 있습니다.