📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
금 개념정리
토

🔷 10.집합⭐⭐

10-1 개념

1. 순서와 중복이 없는 원소들을 갖는 자료구조
2. 상호배타적 집합(Disjoint set): 교집합이 없는 집합 관계

• 참고 블로그
  - 집합 그림, 동작 과정이 좋음
  - 내용, 시간복잡도 관련 설명이 좋음

3. 상호배타적 집합 특성을 활용하는 분야
   배워야 하는 이유: 그래프 알고리즘에서 많이 활용하기 때문
   • 이미지 분할: 서로 다른 부분으로 나누는 데 사용 ex) 사람/배경
   • 도로 네트워크 구성: 각 도로가 교차하지 않도록 설계-> 교차로 혼잡을 줄임
   • 최소 신장 트리 알고리즘 구현 -> 간선을 추가할 때마다 사이클을 형성하는지 여부
   • 게임 개발: 캐릭터 동작을 자연스럽게 구현 ex) 두 캐릭터가 겹치지 않도록 함
   • 클러스터링 작업

10-2 집합의 연산

유니온-파인드 알고리즘

1. 파인드 연산: 특정 노드의 루트 노드가 무엇인지 탐색하는 방법. 특정 노드가 같은 집합에 있는지 확인할 때 사용
2. 파인드 연산의 연산 비용 문제, 경로 압축으로 해결
   ➡️ 부모 테이블에 루트 노드를 바로 저장. 루트노드에 빠르게 접근
3. 합치기 연산: 두 집합을 하나로 합치는 연산
4. 합치기 연산의 연산 비용 문제, 랭크로 해결
   ➡️랭크: 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이

문제

1. 포켓몬

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

풀이 과정

• 포켓몬 n 마리 중에 n/2 마리, 종류를 가장 다양하게 선택해야 한다.
• 포켓몬 종류 번호의 개수를 return 하는 함수 구현
• n/2가 종류보다 크면 종류의 수 선택
• n/2가 종류보다 작다면 n/2를 선택
• 제한사항: n은 짝수이므로 //연산자와 /연산자는 같은 결과

def solution(nums):
    answer = 0
    set_pokemon = set(nums)
    if len(nums)//2 > len(set_pokemon):
        answer = len(set_pokemon)        
    else:
        answer = len(nums)//2
    return answer

간추린 풀이⬇️

def solution(ls):
    return min(len(ls)/2, len(set(ls)))

2. 영어 끝말잇기

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

def solution(n, words):
    used_words = set() # 이미 사용한 단어 저장하는 set
    prev_word = words[0][0] # 이전 단어의 마지막 글자
    
    for i, word in enumerate(words):
        if word in used_words or word[0] != prev_word:
            return [(i%n) + 1, (i//n)+1]
        used_words.add(word)
        prev_word = word[-1]
        
    return [0,0]

참고 블로그: https://1ets-just-do-it.tistory.com/126
비슷한데 조금 다르게