문제19. 대체 경로 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 가중치가 없는 그래프의 최단 경로 탐색 방법에 대한 문제이다. 가중치가 있는 그래프에 대해서는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플루이드 워샬 알고리즘 등을 고려해야 했겠지만, 가중치가 없는 그래프에 대해서는 BFS만을 이용해서 해결할 수 있다. BFS 알고리즘의 특성상, 먼저 큐에 들어간 노드부터 큐에서 꺼내어 쓰기 때문에, 출발지로부터 같은 거리만큼 떨어진 노드는 같은 타이밍에 큐에서 꺼내지게 된다. 당연한 말이지만, 더 멀리 떨어진 노드를 탐색하려면, 가까웠던 노드를 통해서 가야하기 때문에 더 멀리 떨어진 노드보다 가까이에 있는 노드가 더 먼..
그래프
문제17. 통신망 분석 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 문제는 그래프 표현 방법들을 알고 있고, 어떤 표현 방식이 적절한지를 판단할 수 있어야 풀 수 있는 문제였다. 오늘 문제의 컴퓨터의 개수, 즉 노드의 개수는 최대 100,000 개이다. 이를 인접행렬을 이용해서 풀기 위해서는 N * N의 이차원 배열이 필요하므로 사용하게 되는 공간은 최대 100,000 * 100,000 = 10,000,000,000 이다. 실제로 인접 행렬 방식으로 문제를 풀어 제출하면, 많은 수의 테스트 케이스에서 Runtime Error가 나는데, 이는 메모리 초과로 인해 발생한 에러이다. 시간적인 문제도 있다. 문제 조건을 보..
문제16. 연합 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 문제는 유향 그래프에 대한 탐색을 할 수 있는지를 보는 문제이다. 무향 그래프와 유향 그래프는 사실 크게 다르지 않다. 인접행렬 기준으로 설명하자면, 무향 그래프는 array[start_node][end_node]와 array[end_node][start_node]가 같은 값을 가졌고, 어떻게 접근해도 똑같은 결과를 얻었다. 반면에 유향 그래프는 array[start_node][end_node]와 array[end_node][start_node]가 다를 수 있다. 따라서 start_node에서 end_node로 향하는 edge가 있는지를 array[star..
문제14. 작은 노드 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘의 문제는 자료구조 중 하나인 그래프에 대한 기본적인 지식을 알고 있다면 어렵지 않은 문제이다. 그래프는 크게 두 가지 방법으로 표현할 수 있다. 바로 이차원 배열을 사용하는 방식인 인접행렬 방식과, 연결리스트를 사용하는 방식인 인접리스트 방식이다. 두 표현 방법 중 탐색에서 더 큰 효율을 보여주는 방법은 인접행렬 방식이다(단, 메모리 공간을 많이 소모한다는 단점이 있다.). 그래서 이 문제에서 내가 택한 방식은 인접행렬 방식이다. 인접행렬 방식은 이차원 배열의 각 인덱스가 노드가 되고, 두 인덱스로 접근한 배열의 값이 1이면 두 노드 사이에 간선이 있..
