모두의 알고리즘 문제 03. 동명이인 찾기 1 연습문제

3-1 n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘을 만들어 보세요.

#연습문제 3-1
def find_partner(n):
    t=len(n)
    result=set()
    for i in range(0, t-1):
        for j in range (i+1, t):
            print(n[i], "-", n[j])

listA=["Tom", "Jerry", "Mike", "Roll", "Kim", "Oirat", "Hudson"]

find_partner(listA)

실행 결과:

Tom - Jerry
Tom - Mike
Tom - Roll
Tom - Kim
Tom - Oirat
Tom - Hudson
Jerry - Mike
Jerry - Roll
Jerry - Kim
Jerry - Oirat
Jerry - Hudson
Mike - Roll
Mike - Kim
Mike - Oirat
Mike - Hudson
Roll - Kim
Roll - Oirat
Roll - Hudson
Kim - Oirat
Kim - Hudson
Oirat - Hudson

 

 

 

3-2 다음 식을 각각 빅 오 표기법으로 표현해 보세요.

 

65536 -> O(1). n 값의 변화가 없기 때문에.

 

n-1 -> O(n). n이 커질수록 -1의 영향이 없어진다. n값에 식의 크기가 비례해 커진다.

 

2n^2/3 + 10000n -> O(n^2). n이 굉장히 커지면 2n^2/3과 비교했을 때 10000n의 영향이 직아진다. n의 변화에 따라 가장 크게 변하는 항의 계수를 생략해 표현하면 된다. 제곱에 비례한다가 관계의 핵심이니 계수도 생략하고 O(n^2)로 표현한다.

 

3n^4 - 4n^3 + 5n^2 - 6n + 7 -> O(n^4). 위와 마찬가지의 이유다. n의 변화에 따라 가장 크게 변하는 항이 n^4가 있는 항이라 그 항의 계수를 생략하고 표현한 것이다.