본문 바로가기

Wook's 개척일기234

[프로그래머스 : 레벨 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.
[Java] 2차원 배열 출력 방법 배열 출력하는 방법에는 2가지가 있다. 1. for문을 이용한 출력 2. Arrays.toString()을 이용한 출력 방법 1차원 배열은 Arrays.toString()을 하게 되면 안에 있는 값이 정상적으로 출력이 된다. int[] temp = {1,2,3,4,5}; System.out.println(Arrays.toString(temp)); 결과 [1, 2, 3, 4, 5] 하지만 2차원 배열에서 위와 같은 방식으로 하게 되면 배열의 주소를 return 하게 된다. int[][] temp = {{1,2},{3,4},{5}}; System.out.println(Arrays.toString(temp)); 결과 [[I@15db9742, [I@6d06d69c, [I@7852e922] 그래서 2차원 배열도 .. 2021. 6. 14.
[Java] 2차원 배열 정렬 방법 2차원 배열을 사용하다보면 특정 index를 기준으로 정렬하고 싶을때가 있다. 물론 우리가 자료구조를 통해서 정렬을 할수도 있지만 정렬을 하는게 주된 문제가 아닐때는 자바에서 주어지는 정렬 클래스를 사용하는게 더 빠른 방법이다. 그래서 지난번에 배운 Comperable 혹은 Comperator 클래스를 사용하면 된다. https://wpioneer.tistory.com/101 [Java] Comperator 와 Comperable 자바에서는 배열이나 리스트의 정렬을 위해서 Comperator와 Comparable 인터페이스를 제공한다. 두 인터페이스는 모두 정렬을 하기 위해서 사용한다는것은 동일하다. 하지만 둘의 차이점은 아래와 같 wpioneer.tistory.com 2차원 배열 오름차순 1차원 배열을.. 2021. 6. 14.

티스토리툴바