📌 10장 집합(자료구조)
📌💡 10-1. 집합:
- 개념 : 중복이 없는 원소들을 갖는 자료구조, 순서 X
- 종류 : 유한 집합, 무한 집합, 공집합, 상호배타적 집합(=교집합이 없는 집합)
** 상호배타적 집합인 경우
A 집합 : {1,2,3},B 집합 : {4,5,6,7}
** 상호배타적 집합인 아닌 경우
A 집합 : {1,5,3},B 집합 : {4,5,6,7} -> 교집합 5 존재
분야
- 이미지 분야 : 이미지를 다른 부분으로 나누는데 사용 ex) 사람, 배경 분할할때 사용
- 도로 네트워크 구성 : 도로 구축시, 교차하지 않도록 설계할때 사용
- 최소 신장 트리 알고리즘 구현 : 간선 추가시, 사이클 형성 여부 체크할때 사용
- 게임 개발 : 캐릭터 동작을 자연스럽게 구현 ex) 플레이어와 적군이 겹치지 않도록
- 클러스터링 작업 : 각 작업이 서로 겹치지 않도록 구성 -> 동시에 여러작업 사용 가능
📌💡10-2. 집합의 연산
집합 표현 방법 - 트리로 구현시
- 대표 원소 : 집합의 원소 중 집합을 대표하는 역할
-> 트리로 표현시, 루트노드
집합 = 배열로 표현 -> 마지막 노드값까지 인덱스 생성
배열의 인덱스 = 자기 자신, 배열의 값 = 자기 자신의 부모노드
( 루트노드 인덱스 0, 루토노드의 값 0 -> 동일)
( 집합에 없는 인덱스 -1로 표현)
📌💡10-3. 유니온-파인드 알고리즘
💡10-3-1. 파인드 연산
특정 노드의 루트 노드가 무엇인지 탐색하는 방법 ex) 특정 노드가 같은 집합에 있는지 확인할 때 사용
- 재귀함수로 구현하여, 최종 값 반환 => 최악 O(N)
- 현재 노드의 부모 노드 확인, 부모 노드가 루트 노드이면 찾기 연산 종료
- 찾기 연산 종료 못할 시 1 반복
💡10-3-1-1. 파인드 연산(경로압축)
파인드 연산으로 할시, 노드 4의 루트노드 찾기 : find(4)
집합 = {1,2,3,4} 일시 모든 인덱스를 탐색해야함 => 총 3번 탐색 => O(N)
방법 : 트리 깊이를 줄이기
집합 = {1,2,3,4}를
집합 A = {1,2}, 집합 B = {1,3}, 집합 C = {1,4}로 변경 후
find(2), find(3), find(4) 하면 => 총 1번 탐색
💡10-3-2. 유니온 연산
두 집합을 하나로 합치는 방법 = 두 집합의 루트 노드를 가게 하는 것
1. 두 집합에서 파인드 연산을 통해 루트 노드 찾기(= 파인드 연산)
2. 찾은 두 루트 노드의 값을 비교
3. 두 집합을 합치기 (= 두 집합의 루트 노드를 같게)
문제점 : 트리의 깊이가 깊어질시, 연산 비용이 커지는 단점 발생
💡10-3-2-1. 유니온 연산(랭크)
트리의 균형을 유지하기 위해, 랭크 도입
랭크 : 현재 노드를 기준으로 하였을 때, 가장 깊은 노드까지의 경로의 길이
1. 두 노드의 루트 노드 구하기 (= 파인드 연산)
2. 루트 노드의 랭크 비교
2-1. 랭크값 다를 시, 큰 루트 노드를 기준으로 삼기
2-2. 랭크값 같을 시, 바꾸고 최종 루트 노드 랭크에 1을 더함
📌 10. 문제
🩶 문제 33. 간단한 유니온-파인드 알고리즘 구현하기
권장 시간 복잡도 : O(N)
- 상호배타적 집합 표현시 -> union(x,y), find(x,y)
- operations 배열 수행할 연산 종류 2가지로 구현
[u,1,2]로 들어올 시, 노드 1과 노드 2에 대해 union(x,y) 수행
[f,3]로 들어올 시, 노드 3의 루트찾기 find(x,y) 수행
제약조건 :
- 0 <= k <= 1000 : 노드의 개수
- 1 <= len(operations) <= 100,000
- opertaions[i][0] = 문자열 'u','f' 중 한개
- 'u' = union 연산, union 연산 뒤로는 정수 2개
- 'f' = find 연산, find 연산 뒤로는 정수 1개
- x와 y는 0이상 k-1 이하의 정수
- 연산은 항상 유효함 - union, find 연산의 인수는 상호배타적 집합 내에 있는 노드 번호
def find(parents, x):#루트 노드 찾기
if parents[x] == x: # 만약 x의 부모가 자기 자신이면, 즉 x가 루트 노드라면
return x# 루트 반환
# 그렇지 않다면 x의 부모를 찾아서 parents[x]에 저장하고,
# 그 부모 노드의 루트 노드를 찾아서 parents[x]에 저장합니다.
parents[x] = find(parents, parents[x])
return parents[x] # parents[x]를 반환합니다.
def union(parents, x, y): # 두 개의 집합을 합치는 함수
root1 = find(parents, x) # x가 속한 집합의 루트 노드 찾기
root2 = find(parents, y) # y가 속한 집합의 루트 노드 찾기
parents[root2] = root1 # y가 속한 집합을 x가 속한 집합에 합침 = 루트노드 같게
def solution(k, operations):
parents = list(range(k)) # 처음에는 각 노드가 자기 자신을 부모로 가지도록 초기화
n = k # 집합의 개수를 저장할 변수, 처음에는 모든 노드가 서로 다른 집합에 있으므로 k
for op in operations: # operations 리스트에 있는 연산들을 하나씩 처리
if op[0] == "u": # 'u' 연산이면
union(parents, op[1], op[2]) # op[1]과 op[2]가 속한 집합을 합칩니다.
elif op[0] == "f": # 'f' 연산이면
find(parents, op[1]) # op[1]이 속한 집합의 루트 노드를 찾습니다.
# 모든 노드의 루트 노드를 찾아서 집합의 개수를 계산
n = len(set(find(parents, i) for i in range(k)))
return n # 집합의 개수를 반환
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution(3,[['u', 0, 1], ['u', 1, 2], ['f', 2]])) # 반환값 : 1
# print(solution(4,[['u', 0, 1], ['u', 2, 3], ['f', 0]])) # 반환값 : 2🩶 문제 34. 포켓몬
권장 시간 복잡도 : O(N)
제약조건 :
- nums는 폰켓몬의 종류 번호가 담긴 1차원 배열
- nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수
- 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타내기
- 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return
def solution(nums):
choice = len(nums)//2 # 선택할 수 있는 포켓몬 수
nums = set(nums) # 중복된 포켓몬 종류 제거
return min(len(nums), choice) # 고를 수 잇는 포켓몬 가능 수와 중복 제거된 포켓몬의 최소 수