[챗GPT로 코딩 공부] 다익스트라 알고리즘 코드로 구현하기

내일배움캠프 수료생들은 챗GPT를 어떻게 개발 공부에 활용할까요?
Jun 28, 2024
[챗GPT로 코딩 공부] 다익스트라 알고리즘 코드로 구현하기
✍🏼
챗GPT, 개발 공부에 있어서 든든한 친구 같은 존재이죠. 내일배움캠프의 수강생들도 혼자 공부할 때에는 챗GPT의 도움을 받고 있는데요. 오늘은 내일배움캠프 수료생들의 챗GPT 경험담을 보고, 여러분의 개발 공부에 적용해봅시다.
 
CS 공부를 하던 중 그래프에서 최단 경로를 찾는 다익스트라 알고리즘에 관해 어려움을 겪고 있었습니다. 이 알고리즘의 원리와 구현 방법을 이해하는 데 시간이 많이 걸렸고, 어떻게 코드로 구현해야 할지 감을 잡기 어려웠습니다.
 

다익스트라 알고리즘의 기본 원리와 동작 방식

첫 번째 질문에 대해 챗GPT는 다익스트라 알고리즘의 기본 원리와 동작 방식을 설명해 주었습니다. 블로그에서 찾은 정보를 기반으로, 좀 더 제가 모르겠는 부분을 추가해서 질문하니 저에게 맞는 답변을 해주었습니다. 특히 예시를 들어주며 설명해줄 수 있냐고 질문하면, 해당 질문에 대해 이해하기 쉬운 예시를 들어주며 이해를 도와주는 점이 좋았습니다.
아래는 챗GPT가 설명한 다익스트라 알고리즘의 기본 원리와 동작 방식입니다.
다익스트라 알고리즘의 기본 원리와 동작 방식은 다음과 같습니다:
  • 출발점 설정: 시작 노드를 선택하고 해당 노드까지의 거리를 0으로 초기화합니다.
  • 초기화: 다른 모든 노드까지의 거리를 무한대로 설정합니다.
  • 미방문 노드 중 최단 거리 선택: 아직 방문하지 않은 노드 중 시작점으로부터 가장 가까운 노드를 선택합니다.
  • 거리 갱신: 선택한 노드를 거쳐 다른 노드로 가는 거리가 기존에 알고 있던 거리보다 짧으면 해당 거리 정보를 갱신합니다.
  • 반복: 모든 노드를 방문할 때까지 3, 4 단계를 반복합니다.
이 알고리즘은 그리디 방식으로 작동하며, 항상 현재 알고 있는 가장 짧은 경로를 선택합니다.
 

다익스트라 알고리즘을 Java로 구현하는 방법

두 번째 질문에서는 다익스트라 알고리즘을 Java로 구현하는 방법을 단계별로 설명해 주었습니다.
import java.util.*; public class DijkstraAlgorithm { public static class Node implements Comparable<Node> { public int id; public int distance; public Node(int id, int distance) { this.id = id; this.distance = distance; } @Override public int compareTo(Node other) { return Integer.compare(this.distance, other.distance); } } public static int[] dijkstra(int n, List<List<Node>> graph, int start) { PriorityQueue<Node> pq = new PriorityQueue<>(); int[] distances = new int[n]; Arrays.fill(distances, Integer.MAX_VALUE); distances[start] = 0; pq.add(new Node(start, 0)); while (!pq.isEmpty()) { Node current = pq.poll(); int currentId = current.id; for (Node neighbor : graph.get(currentId)) { int newDist = distances[currentId] + neighbor.distance; if (newDist < distances[neighbor.id]) { distances[neighbor.id] = newDist; pq.add(new Node(neighbor.id, newDist)); } } } return distances; } public static void main(String[] args) { int n = 6; List<List<Node>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } graph.get(0).add(new Node(1, 5)); graph.get(0).add(new Node(2, 1)); graph.get(1).add(new Node(2, 2)); graph.get(1).add(new Node(3, 3)); graph.get(2).add(new Node(3, 4)); graph.get(3).add(new Node(4, 2)); graph.get(4).add(new Node(5, 1)); graph.get(5).add(new Node(3, 1)); int[] distances = dijkstra(n, graph, 0); System.out.println("최단 경로: " + Arrays.toString(distances)); } }
 

다익스트라 알고리즘 구현 시 발생하는 오류 해결 방법

다익스트라 알고리즘을 구현할 때 발생할 수 있는 오류 해결 방법을 물어보았습니다. 챗GPT는 그래프의 초기화 문제, 우선순위 큐의 잘못된 사용, 노드의 잘못된 거리 계산 등이 있을 수 있었습니다. 이를 해결하기 위해 그래프 초기화와 우선순위 큐 사용에 주의해야 하며, 각 노드의 거리 업데이트가 제대로 이루어지는지 확인해야 한다고 했습니다.
 
만약 다시 질문을 하게 된다면, 구현 방법을 물어볼 때 수도코드를 제공해달라고 할 것 같습니다. 수도코드를 통해 제가 직접 구현해본 후, 시도한 코드에 대해 다시 첨부해서 코드의 문제점을 찾고 수정해나가며 직접 코드를 완성해 볼 것 같습니다.
 
 

내일배움캠프가 여러분의 러닝메이트가 되어드리겠습니다

내일배움캠프의 많은 수강생들이 부트캠프 생활을 수료하고 현업에서 개발자로 활약하고 있습니다. 내일배움캠프는 모든 운영진이 교육, 특강, 12시간 밀착 케어, 찐한 관리, 인재 채용까지 열과 성을 다해 수강생들의 꿈을 지원하고 있습니다. 수많은 장애물을 넘을 수 있도록 내일배움캠프가 든든한 러닝메이트가 되어드리겠습니다. 내일배움캠프과 함께 여러분의 개발자 여정을 시작하세요.
 
CREDIT
글 | 이지선 내일배움캠프 수료생 편집 | 정효재 팀스파르타 에디터
Share article
Subscribe to our newsletter
RSSPowered by inblog