Python algorithm 개념 및 실습 - 동명이인 찾기

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

동명이인 찾기

 ["Tom","Jerry","Mike","Tom"]

# Tom 입장 : 3번 비교 == (n-1)

# Jerry 입장 : 2번 비교 == (n-2)

# Mike 입장 : 1번 비교 == (n-3)

# Tom 입장 : 0번 비교

# 계산 복잡도 O(n제곱)

# 중복된 이름을 set() 에 추가한 후 리턴

def dup_name(list1):

    result = set()

    size = len(list1)

    for i in range(0, size - 1):

        for j in range(i + 1, size):

            if list1[i] == list1[j]:

                result.add(list1[i])

    return result

if __name__ == "__main__":

    list1 = ["Tom", "Jerry", "Mike", "Tom"]

    print(dup_name(list1))

 

 

 

 딕셔너리 - key:value 구조

# {"Tom" : 1, "Jerry":2} ==> Tom은 한번이 나왔고, Jerry는 두번이 나옴,

# 중복된 이름을 set() 에 추가한 후 리턴

def dup_name(list1):

    name_dict = {}

    # 반복문 - 이름이 등장한 횟수를 딕셔너리로 만듦

    for name in list1:

        if name in name_dict:

            name_dict[name] += 1

        else:

            name_dict[name] = 1

 

    # 중간 확인.  {'Tom': 2, 'Jerry': 1, 'Mike': 1}

    print(name_dict)

 

result = set()

    for name in name_dict:

        if name_dict[name] >= 2:

            result.add(name)

    return result

if __name__ == "__main__":

    list1 = ["Tom", "Jerry", "Mike", "Tom"]

    print(dup_name(list1))