3단원 동명이인 문제(모두의 알고리즘 with 파이썬)

문제 3-1 

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

import sys

def name(): 
    A = list(map(str,sys.stdin.readline().rstrip().split(' ')))
    #입력받는 A리스트
    B = list(set(A)) #집합의 규칙에 따라 중복값 삭제된 뒤 LIST에 저장
    def johab(n):
        C = []
        for i in range(len(n)-1): #집합 B의 길이보다 1을 빼는 이유는 끝 요소는 검사할 필요가 없기 때문이다.
            for j in range(i+1,len(n)): #다음요소부터 끝 요소
                C.append(n[i]+ '-'+n[j]) #C리스트에 조합 요소 추가
        return C
    for i in johab(B):
        print(i)
name()

문제 3-2

다음 식을 각각 대문자 O표기법으로 표현해 보세요.

A. 65536 ======> O(1)

B. n-1 =======> O(n)

C. (2*(n**2))/3 + 10000n =========>O(n**2)

D. 3*(n**4)-4*(n**3) + 5*(n**2)-6*n + 7 ===========> O(n**4)

 

 

 

===>대문자 O표기법 : 제일 큰 계수만 고려 나머지 애들은 무시

계산 복잡도 O(n**2)인 알고리즘은 입력 크기 n이 커지면 계산 시간은 그에 비례한다.