UNIT 03 (기초)

동명이인 찾기 - (1)

문제) n명의 사람 이름 중에서 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 만들어라.

#두 번 이상 나온 이름 찾기
#입력 : 이름이 n개 들어 있는 리스트
#출력 : 이름 n개 중 반복되는 이름의 집합

def find_same_name(a):
    n = len(a)
    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


name = ["Tom", "Jerry", "Mike", "Tom"]
print(find_same_name(name))
name2 = ["Tom", "Jerry", "Mike", "Tom", "Mike"]
print(find_same_name(name2))

#계산 복잡도 : O(n^2)

연습문제

3-1) n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘을 만들어라.
예를 들어 입력이 리스트 ["Tom", "Jerry", "Mike"]라면 다음과 같은 세 가지 경우를 출력한다.

• Tom - Jerry
• Tom - Mike
• Jerry - Mike

#n명에서 두 명을 뽑아 짝으로 만드는 모든 경우를 찾는 알고리즘
#입력 : n명의 이름이 들어 있는 리스트
#출력 : 두 명을 뽑아 만들 수 있는 모든 짝

def connect_friend(a):
    n = len(a)
    for i in range(0, n - 1):
        for j in range(i + 1, n):
            print(a[i], "-", a[j])


name = ["Tom", "Jerry", "Mike"]
print(connect_friend(name))
print()
name2 = ["Tom", "Jerry", "Mike", "John"]
print(connect_friend(name2))

3-2) 다음 식을 각각 대문자 O 표기법으로 표현해라.

A 65536 : O(1)
B n-1 : O(n)
C (2n^2)/3 + 10000n : O(n^2)
D 3n^4 - 4n^3 + 5n^2 - 6n + 7 : O(n^4)

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10