개발자는 기록이 답이다

13. 경로탐색(인접리스트, ArrayList) 예시 입력 1 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 예시 출력 1 6 정점이 1000개 10000개로 들어온다면 인접행렬로는 비효율적이다. 왜냐하면 정점이 5라고하고 5행 5열로 잡으면 된다. 1번 정점에서 갈 수 있는 정점이 어디인지 탐색하는데, 100개 정도까지는 괜찮지만 1000개 10000개라고 하면 인접행렬이라는 그래프로 할때 10000x10000을 해야해서 메모리를 크게 잡습니다. 그리고 1번 정점에서 갈 수 있는걸 찾으려면 1부터 10000까지 for문을 다 돌아야 합니다. 메모리랑 시간복잡도 면에서 너무 비효율적입니다. 그래서 이럴때 인접리스트를 사용합니다. N이 5라고 가정했을때, 1번 리스트부터 5번 리스..

11. 그래프와 인접행렬 그래프에 배워보고, 그 다음에 그래프를 코드안에서는 어떻게 구현하는지 알아보겠습니다. G(V,E)로 이뤄진 집합입니다. Graph는 vertex(정점,노드)와 edge(간선)으로 이루어진 집합 G(V,E) 1. 무방향 그래프 양방향 그래프라고 보면 됩니다. 양쪽 다 갈 수 있으면 무방향으로 하고 연결되어있다고 가정합니다. 도시라는 주제가 주어지면, 노드가 도시가 되고 간선이 도로라고 보면 됩니다. 1번에서 2번 갈 수 있고, 2번에서 1번 갈 수 있다는 것입니다. 5 5 // 정점개수, 간선 개수 1 2 1 2 2 4 3 4 2 5 프로그래머스에서 입력이 들어오면 이것을 그래프로 어떻게 구현할까요? 2차원 배열로 그래프라는 걸로 잡습니다. graph 1 2 3 4 5 1 0 1 ..