반응형 알고리즘51 [알고리즘] 그래프 문제에 활용되는 유니온 파인드(union-find) 유니온 파인드 union-find는 여러 노드가 있을 때 두 개의 노드를 연결하여 한 개의 집합으로 묶는 유니온 연산과 두 노드가 같은 집합에 있는지 확인하는 파인드 연산으로 구성된 알고리즘이다. 유니온 파인드의 기본 개념 union 연산 두 노드가 속한 집합을 1개로 합치는 합집합 연산 find 연산 노드가 속한 집합의 대표 노드를 반환하는 연산 유니온 파인드 알고리즘의 동작 과정 1. 유니온 파인드 배열 초기화 ex) 6개의 노드 일반적으로 1차원 배열을 이용해 표현한다. 처음에는 노드가 연결되어 있지 않기 때문에 각 노드가 대표 노드가 된다. 2. 유니온 연산 수행 ex) union(1, 4) 및 union(5, 6) 수행 union(1, 4) 1번의 대표 노드(1번)와 4번의 대표 노드(4번)를 .. 2024. 1. 2. [Java] 프로그래머스 - 징검다리 건너기 프로그래머스 징검다리 건너기 문제는 카카오 인턴쉽 기출 문제로, 징검다리를 최대 몇명이 건널 수 있는지 구하는 문제다. 난이도는 레벨3이며 이분탐색을 통해 해결할 수 있다. 프로그래머스 - 징검다리 건너기 문제 정보 알고리즘 분류 - 이진탐색 - 슬라이딩 윈도우 난이도 - Level 3 문제 요약 일렬로 놓여있는 징검다리의 디딤돌에는 각각 숫자가 적혀있으며, 한번 밟을 때마다 1씩 줄어듦 디딤돌의 숫자가 0이 되면 더이상 밟을 수 없으며, 가능한 다음 디딤돌로 건너 뛸 수 있음 밟을 수 있는 디딤돌이 여러개인 경우 무조건 가장 가까운 디딤돌로 가야 함 한번에 한명씩 징검다리를 건너는데, 한명이 다 건넌 뒤에 다음 사람 건넘 Q. 징검다리 각 디딤돌의 숫자 및 한번에 건너뛸 수 있는 최대 칸수 k가 주어졌.. 2023. 12. 7. [Java] 프로그래머스 - 가장 먼 노드 프로그래머스 가장 먼 노드 문제는 그래프의 한 노드에서 가장 멀리 떨어져 있는 노드의 개수를 구하는 문제다. 난이도는 레벨3이며 그래프 탐색를 통해 해결할 수 있다. 프로그래머스 - XX 문제 정보 알고리즘 분류 - 그래프 탐색 난이도 - Level 3 문제 요약 n개의 정점으로 이루어진 그래프가 있다. 1번 노드에서 가장 먼 노드의 개수는? 문제 풀이 과정 1번부터 BFS로 돌면서 다른 노드들까지의 최단거리를 구함 최대 거리를 갖는 노드의 개수를 구함 코드 import java.util.*; class Solution { public int solution(int n, int[][] edge) { int answer = 0; int maxLen = 0; // 주어진 그래프 정보를 연결 리스트로 변환 L.. 2023. 11. 23. [Java] 프로그래머스 - 불량 사용자 프로그래머스 불량 사용자 문제는 사용자 리스트와 밴 리스트가 주어졌을 때 밴된 사용자를 구하는 문제다. 난이도는 레벨3이며 그래프 탐색을 통해 해결할 수 있다. 프로그래머스 - 불량 사용자 문제 정보 알고리즘 분류 - 그래프 난이도 - Level 3 문제 요약 사용자 아이디 리스트와 밴 아이디 리스트가 주어짐 밴 아이디 리스트는 사용자 아이디 중 밴된 사용자들의 아이디로, 아이디의 일부가 *로 마스킹처리 되어있음 밴된 사용자 리스트의 경우의 수를 구하라. 문제 풀이 과정 쉬운 문제인 줄 알고 시작했으나.. 생각보다 오래 걸림 일단 사용자 아이디 각각이 어떤 밴 아이디에 걸리는지를 확인해서 따로 저장함 그리고 밴 아이디 개수만큼 사용자 아이디를 뽑아야 되는데, 문제는 순서가 없고 중복도 안된다는 것..! .. 2023. 11. 10. 이전 1 2 3 4 ··· 13 다음 반응형
