1. 집합

• 자료 간 중복 없음
• 자료들의 순서 없음

s = set()
s.add(1)
s.add(2)
s.add(2)
s #{1,2}

len(s) # 2
{1,2} == {2,1} #True

1) len(a)

• 집합의 길이(자료 개수)

s = set()
len(s) # 0
len({1, 2, 3}) # 3

2) add(x)

• 집합에 자료 x를 추가

s = {1, 2, 3}
s.add(4) # {1, 2, 3, 4}이나 순서는 다를 수 있음

3) discard(x)

• 집합에 자료 x가 들어 있다면 삭제
• x가 집합에 없으면 변화 없음

s = {1, 2, 3}
s.discard(2) # s = {1, 3}

4) clear()

• 집합의 모든 자료 삭제

s = {1, 2, 3}
s.clear() # s = {}

5) x in s

• 어떤 자료 x가 집합 s에 들어 있는지 확인

s = {1, 2, 3}
2 in s #True
5 not in s #True

2. 동명이인 찾기 알고리즘

def find_same_name(s):
	n = len(s)
    result = set()
    for i in range(0, n-1):
    	for j in range(i+1, n):
        	if a[i] == a[j]:
            	result.add(a[i])
    return result

• 이중 루프 : 리스트 안에 있는 자료를 서로 빠짐없이 비교하되 중복해서 비교하지 않기 위함
• for i in range(0, n-1): : 0부터 n-2까지 반복. 리스트 마지막 값인 a[n-1]을 비교할 필요가 없음.
• for j in range(i+1, n): : i번째 위치에서 1을 더한 값에서 끝까지 비교

3. 알고리즘 분석

• 연산 횟수 : 전체 비교 횟수 = 1부터 n-1까지의 합
  • 0번 위치 : n-1번 비교
  • 1번 위치 : n-2번 비교
  • n-2번 위치 : 1번 비교
  • n-1번 위치 : 0번 비교

성능 : O(1/2n^2 - 1/2n) = O(n^2)

4. 응용

1) n명 중 2명을 짝지을 수 있는 모든 조합 출력

def pairing(a):
    n = len(a)

    for i in range(0, n-1):
        for j in range(i+1, n):
            print(a[i] + '-' + a[j])


list = ["a", 'b', 'c']
pairing(list)

• 경우의 수 : n(n-1)//2