다익스트라 알고리즘 설명을 통해 지원자의 알고리즘 기초 지식과 개념을 명확하게 설명하는 능력을 평가한다.
이 질문 뒤에 면접관이 확인하려는 것은 따로 있습니다.
다익스트라 알고리즘은 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘입니다. 핵심은 현재까지 알려진 최단 거리가 가장 짧은 노드를 매 단계 선택해 인접 노드의 거리를 갱신하는 방식이고, 음수 간선이 없을 때만 올바르게 동작합니다. 알고리즘 수업에서 우선순위 큐를 써서 구현해봤는데, 처음에는 방문 체크 없이 짰다가 사이클이 있는 그래프에서 무한루프가 났습니다. 시간 복잡도는 O((V+E)logV) 정도로, 노드 수가 많으면 A*처럼 휴리스틱을 추가하는 방식이 더 효율적이라는 것도 비교하며 배웠습니다. 네트워크 라우팅이나 지도 경로 탐색처럼 실제 시스템에서 변형된 형태로 쓰인다는 걸 알고 나서 이 알고리즘이 더 와닿았습니다.
다익스트라를 배우면서 음수 간선이 있을 때는 올바른 결과를 보장하지 못한다는 제약이 실제로 중요하다는 걸 알게 됐습니다. 이 경우를 위해 벨만-포드 알고리즘이 존재하는데, 매 단계 모든 간선을 확인하기 때문에 시간복잡도가 O(VE)로 느려지는 대신 음수 간선을 처리할 수 있습니다.
음수 사이클이 존재하면 최단 거리 자체가 무한히 줄어들어 계산이 불가능한데, 벨만-포드는 이 사이클을 감지하는 기능도 갖추고 있습니다. 문제의 조건이 음수 간선 여부에 따라 쓸 수 있는 알고리즘이 달라진다는 것을, 잘못된 선택으로 틀린 결과가 나온 경험을 통해 배웠습니다. 알고리즘은 어떤 조건에서 동작하는지를 아는 것이 구현 능력만큼 중요하다는 걸 그 과정에서 느꼈습니다.
조건 확인이 알고리즘 선택의 출발점입니다.
알고리즘 공부에서 어떤 패턴의 문제에 어떤 알고리즘이 맞는지를 파악하는 것이 단순 구현보다 중요하다는 걸 깨달았습니다. 처음에는 문제를 보면 바로 구현부터 시작했는데, 풀이가 틀리거나 시간 초과가 났을 때 알고리즘 선택 자체가 잘못됐던 경우가 많았습니다.
그래프 문제라도 최단 거리인지, 탐색인지, 연결 여부인지에 따라 다익스트라·BFS·유니온파인드 중 다른 것을 써야 하는데, 이 감각이 문제를 많이 풀수록 쌓였습니다. 처음 5분을 입력 형태와 제약 조건 파악에 쓰는 것이 코딩 테스트에서 가장 효율적인 시간 배분이라는 걸 경험했습니다. 알고리즘 역량은 암기보다 패턴 인식이라는 걸, 막혔던 문제들을 돌아보면서 확인했습니다.
문제 유형을 읽는 감각이 쌓이면 풀이 속도가 달라집니다.
답변에서 흔히 빠지는 것들 — 빠져 있으면 꼬리질문이 깊어집니다.
이 질문에 이어 삼성전자 네트워크 엔지니어 면접관이 던질 가능성이 높은 후속 질문.
이 페이지의 질문·답변·꼬리질문은 유사 직군 채용 시장의 공개된 면접 후기·커뮤니티 게시물을 분석해 구성한 학습 자료입니다. 특정 회사가 실제로 이 질문을 출제했다는 것을 보장하지 않으며, 모든 예시는 우문현답이 직접 작성한 창작물입니다. 해당 회사의 공식 입장과는 무관합니다. 회사 측의 정정 요청이 있을 경우 24시간 이내에 응답·수정합니다.