[ALGORITHMS]문제 03 동명이인 찾기 1

문제 3

동명이인 찾기 1

N명의 사람 이름 중에서 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 만들어 보세요.

예를들어 사람 이름으로 구성된 리스트 ["Tom","Jerry","Mike","Tom"]이 입력으로 주어졌다면 결과는 집합 ["Tom"]이 됩니다

왜냐하면, Tom이란 이름이 두번 나오기 때문입니다

1.집합

집합은 리스트와 같이 정보를 여러개 넣어서 보관할 수 있는 파이썬의 기능입니다.

다만, 집합 하나에는 같은 자료가 중복되어 들어가지않고, 자료의 순서도 의미가 없다는 점이 리스트와 다릅니다.

4번쨰 줄 s.add(2)는 이미 2가 들어가 있기 때문에 2를 집어 넣지 않습니다.

빈 집합을 만드려면 set()을 이용하교,집합에 자료를 추가하려면 add()함수를 이용합니다. 또한 집합 안에 자료가 몇개 있는 지 알려면 len() 함수를 이용합니다

*자주 쓰는 집합 기능

2. 동명 이인을 찾는 알고리즘

결괏값을 저장할 집합을 알아보았으므로 지금부터는 문제를 실제로 풀어 보겠습니다. 

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

1. 첫 번째 Tom을 뒤에 있는 Jerry, Mike, Tom과 차례로 비교합니다.

2. 첫 번째 Tom과 마지막 Tom이 같으므로 동명이인입니다.(동명이인: Tom)

3. 두 번째 Jerry를 뒤에 있는 Mike, Tom과 비교합니다(앞에 있는 Tom과는 이미 비교했음)

4. 세 번째 Mike를 뒤에 있는 Tom과 비교합니다.

5. 마지막 Tom은 비교하지 않아도 됩니다(이미 앞에서 비교했음)

6. 같은 이름은 Tom 하나뿐입니다.

*이 알고리즘에서 주의할 점은 다음과 같습니다

첫째 비교할 이름을 뽑은 다음에는 뽑은 이름보다 순서상 뒤에 있는 이름하고만 비교하면 됩니다. 앞에 순서들의 이름은 이미 다 비교했고 자기 자신과의 비교는 무의미 하기 때문입니다

둘째 리스트의 마지막 이름은 비교를 안해도 됩니다.

셋째 같은 이름을 찾으면 결과 집합에 그 이름을 추가합니다.

* 동명 이인을 찾는 알고리즘

3.알고리즘 분석

이 알고리즘의 계산 복잡도를 분석해 봅시다. 같은 이름을 찾는 알고리즘이므로

두 이름이 같은지 '비교'하는 횟수를 따져 보면 됩니다.

*입력 크기 : n

- 0번 위치 이름 : n-1 비교 (자기를 제외한 모든 이름과 비교)

- 1번 위치 이름 : n-2 비교

....

- n-2번 위치 이름 : 1번 비교

- n-1번 위치 이름 : 0번 비교

결국 전체 비교 횟수는 0+1+2+....+(n-1)번 즉 1부터 n-1까지 더한 합입니다

1+2+3+...+(n-1) 는  (1/2)n^2 +(1/2)n입니다

따라서 대문자 O표기법으로는 O(n^2)가 됨을 알 수 있습니다.

* 연습 문제

 1. n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 

모든 조합을 출력하는 알고리즘을 만들어보세요

예를 들어 ["Tom","Jerry","Mike"]라면

Tom - Jerry

Tom - Mike

Jerry - Mike

이렇게 3가지를 출력해야 합니다

답:

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

A. 65536             답 : O(1)

B. n-1                답 : O(1)

C. (2/3)n^2+10000n        답 : O(n^2)

D. 3n^4-4n^3+5n^2-6n+7         답 : O(n^4)

읽어주셔서 감사합니다