Union Find3 [프로그래머스] Lv3 문제풀이1(feat. JAVA) 정수 삼각형 - Dynamic Programming import java.io.*; import java.util.*; class Solution { public int solution(int[][] triangle) { int answer = 0; int[][] dp = new int[triangle.length][triangle[triangle.length-1].length]; dp[0][0] = triangle[0][0]; for(int i = 1; i < triangle.length; i++) { for(int j = 0; j < i + 1; j++) { if(j == 0) { dp[i][j] = dp[i-1][j] + triangle[i][j]; } else if (j == i) { dp[i][.. 2023. 10. 4. [알고리즘] 자바로 Union Find 구현하기 유니온 파인드란? 그래프/트리의 대표적 알고리즘 서로소인 부분집합의 표현 여러 노드가 있을 때, 두 노드가 같은 그래프에 속해 있는지 알 수 있는 알고리즘 두가지 메소드로 구현 가능 : union(x, y), find(x) 유니온 파인드 알고리즘이란, 하위 노드의 부모 노드를 배열에 저장하는 방식으로, 여러 노드들이 어떤 집합에 속해 있는지를 알 수 있는 유용한 알고리즘이다. 유니온 파인드를 능숙하게 사용할 수 있게 되면, 백준 등 여러 코딩 문제들도 손쉽게 풀 수 있다. 코드 구현 find find() 는 int 변수를 파라미터로 받는 재귀함수이다. 파라미터로 넘긴 노드의 젤 최상위 부모가 누구인지를 알려주는 함수이다. public int find(int x) { if(parent[x] == x) re.. 2023. 9. 20. [백준] 자바 문제 풀이 10216 : 골드4 import java.util.*; import java.io.*; public class Main { static int[] parent; static class Point { int x; int y; int r; Point(int x, int y, int r) { this.x = x; this.y = y; this.r = r; } } public static boolean union(int x, int y) { x = find(x); y = find(y); if(x == y) return false; if(x 2023. 9. 20. 이전 1 다음 728x90 반응형
