코딩일기/알고리즘75 [프로그래머스 : 레벨 3] 단속카메라 (Java) 이번 문제는 문제 해결 방법을 위한 접근이 잘못되어서 많은 시간을 버렸다. 단속종료지점 >= 시작점 이개념으로 시작을 하긴 했지만 정렬 부분에 있어서 다른걸 정렬을 하다보니까 문제가 풀리지 않았다. 그래서 결국에 이번것도 답지를 보게 되었다. 문제를 보자. 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있.. 2021. 6. 15. [프로그래머스 : 레벨 3] 섬 연결하기 : 크루스칼 알고리즘 (Java) 이번 문제는 크루스칼 알고리즘을 직접구현하고 나서 문제를풀었더니 금방 풀렸다. 내 스스로 풀었다고 해야할지 아니면 답을 봤다고 해야할지 모르겠지만 어찌됐건 크루스칼 알고리즘을 배워서 적용시키니 금방 풀렸다. 문제부터 보자. 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1).. 2021. 6. 15. [자료구조] 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 노드들이 서로 간선을 통해서 연결되어 있을때 각 노드들을 모두 방문할수있는 최소경로를 구하는 알고리즘이다. 크루스칼 알고리즘은 탐욕 알고리즘으로 문제를 해결해나갈수 있다. 매번 경로를 선택할때마다 최단 경로를 선택해서 나아가기 때문이다. (그렇다고 탐욕 알고리즘이 최적의 해를 항상 구해주는것은 아니다.) 그럼 이제 크루스칼 알고리즘의 특징부터 확인해보자. 크루스칼 알고리즘의 특징 1. 간선(경로)의 개수는 항상 노드 - 1 이다. 2. 간선을 선택할때 사이클이 형성되어선 안된다. 이제 특징을 알아봤으니 크루스칼 알고리즘의 동작원리를 확인해보자. 크루스칼 알고리즘의 동작원리 크루스칼 알고리즘의 기본적인 동작 원리는 아래와 같다. 1. 경로가 제일 작은 순으로 선택을 한다. 2. 경로를 .. 2021. 6. 15. [자료구조] Union Find 알고리즘 : 재귀호출 (Java) Union Find 알고리즘이란? Union Find 알고리즘은 크루스칼 알고리즘의 구현을 위한 핵심 자료구조로 여러 노드가 존재할때 두개의 노드를 선택해서 그 도느가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 말로써는 이해가 어려울수 있으니 그림으로 설명을 하겠다. 위처럼 3개의 노드가 존재하고 있다고 가정하자. 각각의 노드들은 아직 연결되어 있는것이 없기 때문에 각각의 부모노드는 자기 자신이다. 그래서 위의 노드의 부모 노드표를 보면 아래와 같다. 1 2 3 1 2 3 위의 상황에서 우리는 1-2 를 서로 연결하고 싶다고 할때 그래프는 아래와 같이 변하고 표는 아래와 같이 변하게 된다. 1 2 3 1 1 3 ( 보통 위처럼 노드를 연결하게 될때 부모 노드는 수가 작은쪽의 노드를 수가 큰쪽의 .. 2021. 6. 14. 이전 1 ··· 10 11 12 13 14 15 16 ··· 19 다음
