algorithm3 합집합 찾기 Union - Find Set 알고리즘 합집합 찾기(Union and Find Set) 알고리즘 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 두개의 연산을 수행한다. Find 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 어떤 원소가 속한 집합을 대표하는 원소를 반환하는데, 이를 위해 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다. Union 두 개의 집합을 하나의 집합으로 합친다. 예제 문제 오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 철수네 반 학생은 N명이다. 철수는 각학생들의 친구관계를 알고 싶다. 모든 학생은 1부터 N까지 번호가 부여되어 있고, 철수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다. 만약 (1,.. 2021. 9. 13. 플로이드 와샬 Floyd Warshall 알고리즘 다이스트라(Dijkstra) : 하나의 점에서 출발했을 때 다른 모든 정점으로의 최단 경로(최소비용)를 구하는 알고리즘. 플로이드 와샬 : 모든 정점에서 모든 정점으로의 최단 경로(최소비용)를 구하고 싶을 때 사용한다. 거쳐가는 정점을 기준으로 최단 거리를 구하는 것 문제를 직접 풀어보며 알아보자. N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때, 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하라. ✔️ 입력 - n : 도시의 수 (N 정점 5 일 때 최소비용을 고려하면 자동으로 정점 3을 거치게 된다는 것이다. 이를 javascript 코드로 구현하면 다음과 같다. function solution(n, edges) { let answer =.. 2021. 9. 9. 알고리즘 | 이분탐색 개념과 예제 + 심화 📌 개념 다지기 이분 탐색 탐색 기법중 하나로, 탐색하고 싶은 범위를 두 부분으로 분할해서 찾는 방법이다. 두 부분으로 계속 분할해서 조건에 맞는지 찾아가기 때문에, 시간 복잡도가 O(log n)으로 매우 빠른편이다. ✔️탐색하는 방법 배열이 정렬(sort)되어 있어야한다. left와 right를 배열의 양 끝으로 설정한다. mid = (left + right) / 2 로 설정하여, mid 값이 기준값보다 작거나 큰지 확인한다. (오름차 배열 정렬되어있을 때) mid 값이 기준값 보다 작다면, left를 (mid+1)로 설정한다. (오름차 배열 정렬되어있을 때) mid 값이 기준값 보다 크다면, right를 (mid-1)로 설정한다. left > right 가 될 때 까지 2,3 번을 반복한다. ✏️이분.. 2021. 8. 26. 이전 1 다음
