[자료구조] Union Find / Disjoint-Set 알고리즘 개념 및 최적화

목 차 Union-Find Algorithm 기본 개념 최적화 Union-Find Algorithm 기본적으로 Union-Find는 자료구조이다. 하지만 이 자료구조를 지원하는 Union과 Find는 알고리즘이다. 여러 노드가 서로 중복되지 않는 집합 여러 개로 나뉘어 있을 때, 각 집합을 대표하는 노드를 찾거나 두 집합을 합치는 연산을 하는 자료구조이다. 기본 개념 1. Union: 두 개의 원소가 포함된 집합을 하나로 합친다. 2. Find: 주어진 원소가 속한 집합의 대표 노드를 반환한다. 최적화 대표적인 최적화는 '경로압축' 인데, 바로 Find 연산을 수행할 때, 방문한 노드를 모두 그 집합의 대표 노드로 바꾸는 것이다. 여기에 'Rank' 시스템을 도입하면 시간 복잡도가 눈에 띄게 줄어드는데,..

Algorithm 2023.10.16

[백준] 1697: 숨바꼭질 - JS (그래프 탐색(DFS&BFS))

목 차 문제 접근 방식 풀이 문제 접근 방식 이번에는 BFS로 풀려고 한다. 구현 전에 설정한 조건은 다음과 같다. 방식: BFS (queue) 이동: -1, +1, *2 방문 체크: push 후 해당 요소를 1로 바꿈 범위: 100000 while문 조건: queue.length queue 에는 [item(이동), time]이 한 노드임 item과 K가 같다면 출력 후 반복문 종료 push 조건 - 1: item - 1 >= 0 && arr[item - 1] == 0 + 1: item + 1

Algorithm 2023.10.12

[Algorithm] 그래프 탐색 알고리즘(DFS, BFS)

목 차 DFS와 BFS 구현 방법 대표 문제 유형 DFS와 BFS DFS: 깊이 우선 탐색, 재귀 함수를 사용하여 구현하는 것이 일반적이다. 재귀를 타고타고 탈출 조건에 도달하고, 그 다음에 파라미터를 하나씩 바꿔 가면서 정답을 찾는 방식. BFS: 너비 우선 탐색, Queue나 LinkedList를 사용하는 것이 일반적이다. DFS와 BFS의 장단점 DFS 장점 현재 경로상의 노드만 기억하므로 적은 메모리를 사용한다. 재귀함수를 사용하여 구현이 BFS 보다 간편하며, 코드 검증이 쉽다. 단점 비효율적인 경로를 탐색하는 경우가 있다. 가장 먼저 찾은 경로가 최단 경로라는 보장이 없다. BFS 장점 시작노드에서 가장 가까운 노드부터 탐색하기 때문에 최단 경로를 보장한다. 단점 모든 노드를 큐에 저장하므로 ..

Algorithm 2023.10.12

[백준] 1654: 랜선 자르기 - JS (이분 탐색)

목 차 문제 접근 방식 풀이 문제 예시로 const 랜선: number[] = [802, 743, 457, 539] 이렇게 랜선 4개가 있다면 여기서 랜선 11개를 가져가야 할 때 최대로 자를 수 있는 길이를 구하라는 것이다. 접근 방식 일단 나무 자르기와 비슷한 방식으로 접근하기로 했다. 아래는 코드 설계 전 내가 설계할 코드의 큰 틀을 설계한 것들이다. 최댓값 = max 최솟값 = min 반 값 = half for문: 전체적인 계산 처리를 하는 코드 result = for문에서 계산된 결과가 N과 같다면 result 변수에 저장한다. 단, result 변수의 초기값은 0으로 시작하고, 최대의 값을 구해야 하므로 result의 값 보다 큰 경우 갱신하도록 한다. 풀이 tamp >= N 일 때 resul..

Algorithm 2023.09.05