프로그래밍나무

  • 홈
  • 태그

Union-Find 1

Union-Find

개념 서로 중복되지 않는 부분 집합들을 표현할 때 사용하는 알고리즘 해당 알고리즘에 필요한 연산은 부분 집합들을 서로 묶는 연산(Union), 해당 원소가 어느 집합에 속해있는지 찾는 연산(Find)이 있습니다. 부분 집합들을 표현하는 방법 배열 해당 원소가 몇 번째 집합에 속해 있는지 각각의 원소마다 표시합니다. 1번째 부분 집합 : {0, 1, 2} 0 -> 1, 1 -> 1, 2 -> 1 Union 연산: 모든 원소에 대해서 몇 번째 집합에 속해 있는지에 대한 수정이 일어납니다.( O(N) ) Find 연산: 해당 원소가 몇 번째 집합에 속해있는지 바로 찾을 수 있습니다.( O(1) ) 트리 부분집합마다 트리를 생성하여 각 원소가 부모 원소를 표시하고 있습니다(루트 원소는 자기 자신을 표시) 1번째..

CS/알고리즘 개념 2021.07.16
1
더보기
  • 분류 전체보기 (75)
    • Backend (15)
      • Spring (10)
      • JPA (2)
      • Oracle (2)
      • 기타 (1)
    • Frontend (5)
      • Vue (5)
    • Tools (1)
      • Jenkins (1)
    • 코딩테스트 (15)
      • 백준 (10)
      • SWEA (2)
    • CS (14)
      • CS 면접 준비 (2)
      • 알고리즘 개념 (10)
      • 자료구조 (2)
    • Cloud (1)
      • AWS (0)
    • 프로그래밍 언어 (5)
      • C++ (2)
      • JAVA (3)
    • Git (2)
    • Docker (3)
    • 책 (5)
      • 기술 관련 (5)
    • 프로젝트 (5)
      • SNS를 통한 운동팀 매칭 서비스 (4)
      • 설문조사 서비스 (1)
    • 기타 (1)

Copyright © Kakao Corp. All rights reserved.

티스토리툴바