chp10 집합(set)

이 글은 골든래빗 <코딩 테스트 합격자되기 파이썬편>의 10장 써머리입니다.

 

[집합 기본 개념]: 중복이 없는 원소를 가지는 자료 구조.

상호배타적(disjoint) 집합: 교집합이 없는 관계  -> 그래프 알고리즘에 활용 多

그외 활용 예) 이미지 분할, 도로 네트워크 구성, 최소 신장 트리 알고리즘 구현, 클러스팅 작업 등

 

표현방법1) 트리형태: 인덱스는 자식노드, 그 값은 부모노드.  루트노드인 경우 인덱스도 루트노드

disjoint 관계라면 한 배열(리스트)에 같이 표현 可

-> union - find 알고리즘 연계

find연산: 특정 노드의 루트 노드 재귀 탐색  -> 루트노드를 찾는 과정으로 최악으론 O(N) 시간복잡도.

 

효율적으로 하는 방법? -> 경로 압축 이용

경로 압축 개념은 이렇게 루트노드가 같다면 바로 연결하는 것이다.

 

 

union연산: 두 집합을 합치는 것. 두 집합의 루트 노드를 파악하고, 이를 같게 하는 것(둘 중 아무거나 선택)

랭크: 루트 노드로부터 끝 노드 까지의 거리중 가장 긴 거리

 

합칠 때 랭크기반으로 union 연산을 수행하는게 더 효율적이다. 즉, 랭크가 큰 노드에 작은 랭크의 노드를 합쳐야 한다.

랭크 2와 1인 두 집합에 대해서 왼쪽은 1에 2를 합쳐 더 길어졌으나, 오른쪽은 2에 1을 합쳐 랭크(깊이)가 불변하였다.

 

 

 

 

 

문제 33) 간단한 유니온-파인드 알고리즘 구현하기

union(x, y)로 x와 y가 속한 두 집합을 합치고, find(x)로 x가 속한 집합의 대표 원소를 찾아야 합니다.

k는 노드 개수, operations는 수행할 연산을 담은 리스트입니다. 연산 종류는 2가지입니다.

1. ['u', 1, 2]: 노드 1과 노드 2에 대해 union 연산 수행

2. ['f', 3] 노드 3의 find 연산 수행

루트 노드(초기 노드)의 부모 노드는 자기 자신으로 설정할 때, operatons의 연산을 모두 수행 후 집합의 개수를 반환하는 함수를 구현하세요.

 

 

문제랑 주어진 예시가 이해가 안가서 저자의 풀이를 보기로 했다.

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  # 집합의 개수를 반환

assert solution(3,[['u',0,1],['u',1,2],['f',2]]) == 1
assert solution(4,[['u',0,1],['u',2,3],['f',0]]) == 2

직접 구현하란 문제는 거의 나올 일은 없겠지만 알고리즘을 공부하란 의미로 만든 문제라고 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 34) 폰켓몬

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

# N = 총 마리수, nums = 폰켓몬 종류번호 담긴 배열
# 목적: N/2마리의 폰켓몬 선택 방법 중, 가장 많은 종류의 폰켓몬 선택한 경우의 개수 return
# idea: set으로 변환한 다음 N개수와 비교해서 값 출력
def solution(nums):
    yardstick = len(nums) // 2
    return yardstick if yardstick <= len(set(nums)) else len(set(nums))

set개념을 사용하면 매우 가볍게 풀 수 있는 문제이다. 처음엔 문제 그대로 구현하고 조금 더 코드를 짧게 재구성했다.

yardstick도 정의 안하고 쓰면 2줄코드는 되겠지만..  짧다고 다 좋은게 아니고 return값이 너무 길어지므로 패스

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 35) 영어 끝말잇기

https://school.programmers.co.kr/learn/courses/30/lessons/12981

프로그래머스

문제 풀이 미완성

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 36) 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

문제 풀이 미완성

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 37) 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

문제 풀이 미완성