코테 팁

코드를 중단시킬때 break보다 exit(0)을 쓰면 출력 초과가 나지 않는다.

합집합 찾기(Union-Find)알고리즘

• 원소들의 연결 여부를 확인하는 알고리즘이다.
• (그림 가정) 더 작은 원소를 부모로 삼도록 설정

처음엔 모두 자기가 자기를 가리키고 있다.

1-4는 작은 수가 부모이기 때문에 4가 1을 가리키고 4는 1이 된다.

2-4는 현재 4가 1이기때문에 2-1이 되고 부모가 더 작은 수 이기 때문에 2도 1이 된다.
따라서 1, 2, 4는 1이 되고 3만 다른값이기 때문에 집합은 총 두개 {1, 2, 4}, {3}이 된다.

코드:

def find(x):
	if x == parent(x):
		return x
	else:
    	p = find(parent(x)):
        parent[x] = p
        return parent[x]

def union(x, y):
	x = find(x)
    y = find(y)
    
    parent[y] = x

실질적인 자기의 부모를 먼저 찾고 그 부모와 새로운 값을 합친다.

계수 정렬(counting sort) 알고리즘

• 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법이다.
• 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정한다.
• 데이터가 등장한 횟수를 센다.
  
  유의사항 : 데이터의 개수가 많을 때 시간초과 때문에 파이썬에서는 sys.stdin.readline()을 사용해야 한다.