본문 바로가기

Wook's 개척일기234

[프로그래머스 : 레벨 5] 방의개수 : HashSet(Java) 이번문제는 방을 찾는거라서 BFS 알고리즘 생각했는데 어떻게 사각형을 표현할지 감이 잡히지 않았다. (그리고 레벨 5인걸에 쫄기도 했다) 그래서 답을 보게 되었다. 근데 답을 보니 생각보다 이해가 쉬웠다. 답에서는 이번 문제를 수학적인 그래프로 사용을 했다. 문제부터 살펴보자. 문제 설명 원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다. ex) 1일때는 오른쪽 위로 이동 그림을 그릴 때, 사방이 막히면 방하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요. 제한사항 배열 arrows의 크기는 1 이상 100,000 이하 입니다. arrows의 원소는 0 이상 7 이하 입니다. 방.. 2021. 7. 9.
[프로그래머스 : 레벨 3] 순위 : 플로이드워셜 알고리즘(Java) 이번문제는 이긴 처리를 어떻게 처리할줄 몰라 답을 보게 되었다. 덕분에 플로이드 워셜 알고리즘에 대해서 알게되었다. 해당 알고리즘을 알고나니 이번 문제가 좀더 쉽게 이해가 됐다. 플로이드 워셜 알고리즘에 대해 잘 모르는 분들은 아래 링크를 통해 확인해보고 오면 될것 같다. https://wpioneer.tistory.com/146 [자료구조] 플로이드 워셜 알고리즘 (Java) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 이란? 플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대한 최단거리를 구하는 알고리즘이다. 이게 무슨소리냐면 아래와 같은 그래프 wpioneer.tistory.com 문제부터 살펴보자. 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부.. 2021. 7. 9.
[자료구조] 플로이드 워셜 알고리즘 (Java) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 이란? 플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대한 최단거리를 구하는 알고리즘이다. 이게 무슨소리냐면 아래와 같은 그래프에서 1 -> 4 로 가는 비용은 8 이지만 3번 노드를 거쳐서 가면 1 -> 3 : 2 3 -> 4 : 4 이렇게 가는 비용이 6이라 더 짧기때문에 1 -> 4 가는 비용을 6으로 바꿔준다는 얘기이다. 이렇게 해서 모든 노드로 가는 최소비용을 구하는것이다. 이걸 구현하는 방법은 위에서 보여줬듯이 모든 노드를 거쳤을때 가는 비용이 일반적으로 가는 비용보다 큰지를 확인하고 거쳤을때의 비용이 작다면 값을 바꿔주고 아니라면 값을 그대로 냅두는것이다. 이걸 위그림을 표로 만든것을 토대로 한번 해보자. 1.. 2021. 7. 9.
[프로그래머스 : 레벨 3] 가장 먼 노드 : BFS(Java) 이번 문제는 내가 다른 DFS 알고리즘으로 풀어서 틀려가지고 결국엔 답을 본 문제다. 막상 답을 보니 나도 금방 내 소스에 녹아냈는데 좀더 문제를 자세히 볼걸 하며 약간 아쉬웠던 문제였다. 일단 문제부터 살펴보자. 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 2.. 2021. 7. 9.

티스토리툴바