알고리즘 개념 특정 제한 조건 내에서 가장 높은 가치를 얻을 수 있는 선택 조합을 찾는 문제를 해결하기 위한 알고리즘즉, 조합 최적화 문제의 일종 배낭문제가 대표적 -  담을 수 있는 최대 무게가 정해진 배낭과 함께     각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때,     배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제  알고리즘 종류이때, 주어진 아이템의 분할 가능 여부에 따라 두 종류로 나뉜다.이번 블로그 글에서는 분할 불가한 0/1 Knapsack을 다룰 것이다.알고리즘 종류해결 방법특징(아이템 분할 여부) 0/1 Knapsack 동적 계획법, 백트레킹아이템 분할 불가  Fractional Knapsack 탐욕적 접근법아이템 분할 선택 가능 1..

알고리즘 개념유니온 파인드(Union-Find) 알고리즘은 분리 집합을 관리하는 알고리즘으로그래프 형태의 자료들의 연결 정보를 알고 싶을 때 사용된다.이 알고리즘의 핵심 목표는 합치기(Union)와 찾기(Find) 작업을 효율적으로 수행하는 것이다.주로 그래프에서 연결된 컴포넌트 관리 나 사이클 검출에 활용된다.    - 집합 소속 여부 판단 & 사이클 검출 : 임의의 두 노드의 연결 여부(집합 소속 여부) 확인        - 단, 무방향 그래프에서만 적용 가    - 경로 압축 : 그래프 내 노드 간의 경로 최적화  위의 경우 3과 5가 같은 그룹인지 알려면왼쪽의 경우 자신의 부모만 기록되어 있으므로 연결여부 확인이 따로 필요하다.이때 재귀 호출을 통해 루트 노드를 찾을 때 탐색 시간이 소요된다.un..