[알고리즘:파이썬] 03. 동명이인 찾기

안녕하세요. 쏘피입니다. 오늘은 03. 동명이인 찾기 문제를 풀어보겠습니다.

 

 

 

 

---

문제: 동명이인을 찾으시오

---

잠깐! 문제를 풀기 앞서 파이썬 기초

 

집합:

1) 리스트와 같이 정보를 여러 개 넣어서 보관할 수 있는 파이썬의 기능

2) 집합 하나에는 같은 자료가 중복되어 들어가지 않고, 자료의 순서도 의미가 없다.

 

s = set() #빈 집합 만들기 s.add(1) # 자료 추가 s.add(2) s len(s) {1, 2} == {2, 1} #자료 순서 무관하므로 같은 집합

---

풀이:

 

1) 입력: 이름이 n개 들어있는 리스트

2) 출력: 이름 n개 중 반복되는 이름의 집합

3) 계산 알고리즘: 

    [1] 첫 번째 Tom을 뒤에 있는 Jerry, Mike, Tom과 차례로 비교

    [2] 두 번째 Jerry를 뒤에 있는 Mike, Tom과 비교

    [3] 마지막 Tom은 비교하지 않아도 됨. 앞에서 진행했기 때문에

* 주의 (1) 비교할 이름을 뽑은 다음에는 뽑은 이름보다 순서상 뒤에 있는 이름만 비교

         (2) 리스트의 마지막 이름을 기준으로는 비교하지 않아도 됨

         (3) 같은 이름을 찾으면 결과 집합에 그 이름을 추가

 

4) 파이썬으로 구현:

#문제 3: 동명이인 찾기 def find_same_name(a):     n = len(a)                    # 리스트의 자료 개수를 n에 저장     result = set()                # 결과를 저장할 빈 집합     for i in range(0, n-1):       # 0부터 n-2까지 반복         for j in range(i + 1, n): # i+1부터 n-1까지 반복             if a[i] == a[j]:      # 이름이 같으면                 result.add(a[i])  # 찾은 이름을 result에 추가     return result name = ["Tom", "Jerry", "Mike", "Tom"] #대소문자 유의: 파이썬은 대소문자를 구별함 print(find_same_name(name))

---

알고리즘 분석

---

두 이름이 같은지 비교하는 횟수를 따져봅니다.

n = 4일 경우, 3/2/1=6임.

n일 경우, 1+2+3+....+(n-1)=(n*(n-1))/2=1/2n^2-1/2n

빅오의 경우 O(n^2): n이 커지면 계산 시간은 그 제곱에 비례하므로 엄청난 차이로 증가

 

---

추가 연습 문제

---

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

예를 들어 입력이 리스트 ["Tom", "Jerry", "Mike"]라면 다음과 같은 세 가지 경우를 출력합니다.

Tom-Jerry, Tom-Mike, Jerry-Mike

 

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

A 65536

B n-1

C 2n^2/3+10000n

D 3n^4-4n^3+5n^2-6n+7

 

---

추가 연습문제 풀이

---

# 3-1 n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘   def find_pairs(a):     n = len(a)                    # 리스트의 자료 개수를 n에 저장          for i in range(0, n-1):       # 0부터 n-2까지 반복                          for j in range(i + 1, n): # i+1부터 n-1까지 반복                 print(a[i],"-",a[j])     return result name = ["Tom", "Jerry", "Mike", "Tom"] #대소문자 유의: 파이썬은 대소문자를 구별함 find_pairs(name)

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

A 65536: O(1) n값의 변화와 관계 없음

B n-1: O(n), n이 굉장히 커지면 -1은 거의 영향이 없어진다.

C 2n^2/3+10000n: O(n^2), n이 굉장히 커지면 10000n의 영향은 작아짐. 제곱에 비례하는게 핵심

D 3n^4-4n^3+5n^2-6n+7: O(n^4) n의 변화에 따라 가장 크게 변하는 항을 계수를 생략하여 표현

 

문제 출처: 모두의 알고리즘 with 파이썬

 

---