algorithm(python), [2문제] sns 평균 연결선과 관계에 따른 정렬

Goal

sns친구 관계 연결선 평균을 구하는 알고리즘을 구현하고 이해한다.

참고자료

조엘 그루스(김한결, 한성주, 박은정 옮김), "밑바닥부터 시작하는 데이터 과학 2판", O'REILLY

게시글에 오류, 수정, 추가, 개선이 필요할 경우 지적해주시면 감사하겠습니다.

---

1. 해결해야하는 문제

1. 각각의 id를 가진 사람의 네트워크 구성이 그림과 같을 때 각 사람들의 평균 연결 수는 몇 개인지 구하여라

   • 조건
     • 각 사용자는 id와 이름의 정보를 가진다.

2. 친구 관계가 가장 많은 순으로 정렬하라

[1번] 문제내용

각각의 id를 가진 사람의 네트워크 구성이 그림과 같을 때 각 사람들의 평균 연결 수는 몇 개인지 구하여라

• 조건
  • 각 사용자는 id와 이름의 정보를 가진다.

[1번-1] 아이디어

1. 각 사용자의 연결선 길이를 구하는 함수를 구현한다.
2. 사용자의 정보는 리스트의 dictionary로 구현한다.
3. 초기 사용자 간의 관계는 list의 tuple로 구현한다.
4. [3번]의 내용을 dictionary 관계로서 표현한다.
   • 딕셔너리로 구현할 경우 시간복잡도를 O(1)로 가져갈 수 있으므로 채택
5. 평균을 구한다.
   • sum()과 위에서 구현한 함수를 이용해 사용자들의 연결 합계를 구한다.
   • (연결 합계 / 총 사용자 수)로 목표를 해결

[1번-2] 문제풀이 및 출력

# [1] 사용자 길이를 구하는 함수
def number_of_friends(user) :
    user_id = user["id"]
    friend_ids = friendships[user_id]
    return len(friend_ids)

# [2] 사용자 정보는 리스트의 딕셔너리로 구현한다.
#    - name은 언급이 없었으므로 임의의 값을 넣었다.
users =[
    {"id": 0, "name": "Hero"},
    {"id": 1, "name": "Dunn"},
    {"id": 2, "name": "Sue"},
    {"id": 3, "name": "Chi"},
    {"id": 4, "name": "Thor"},
    {"id": 5, "name": "Clive"},
    {"id": 6, "name": "Hicks"},
    {"id": 7, "name": "Devin"},
    {"id": 8, "name": "Kate"},
    {"id": 9, "name": "Klein"},
]

# [3] 초기 사용자 간의 관계를 리스트의 튜플로 구현한다.
#    - 사실, 직접 dictionary에 넣어도 된다.
friendship_pairs = [(0, 1),(0, 2),(1, 2),(1, 3),(2, 3),(3, 4),
                    (4, 5),(5, 6),(5, 7),(6, 8),(7, 8),(8, 9)]

# [4-1] 사용자 간의 관계를 value를 list로 가지는 empty dictionary로 나타낸다.
friendships = {user["id"]: [] for user in users}

# [4-2] 각 사용자가 가지는 관계를 list형식으로 value 채워넣는다.
for i, j in friendship_pairs :
    friendships[i].append(j)
    friendships[j].append(i)

# [5-1] 각 사용자들의 관계를 더한다.
total_connections = sum(number_of_friends(user) for user in users)
# [5-2] 사용자들이 몇 명인지 저장한다.
num_users = len(users)
# [5-3] (연결 합계 / 총 사용자 수)를 하여 목표를 해결한다.
avg_connections = total_connections / num_users
# 답 출력
print(avg_connections) # output : 2.4

---

[2번] 문제내용

• 1-2 친구 관계가 가장 많은 순으로 정렬하라

[2번-1] 아이디어

1. list의 tuple을 이용한다.
   • tuple은 (사용자 id, 연결된 친구 수)이다.
     • 사용자 id -> 위에서 구현한 users를 활용한다.
     • 연결된 친구 수 -> 위에서 구현한 number_of_friends 함수를 이용한다.
2. [1]번의 변수와 sort 함수를 이용해 문제를 해결한다.
   • key는 연결된 친구 수가 기준이 되어야한다.
   • 가장 많은 순이므로 reverse를 이용해준다.

[2번-2] 문제풀이 및 출력

def number_of_friends(user) :
    user_id = user["id"]
    friend_ids = friendships[user_id]
    return len(friend_ids)

users =[
    {"id": 0, "name": "Hero"},
    {"id": 1, "name": "Dunn"},
    {"id": 2, "name": "Sue"},
    {"id": 3, "name": "Chi"},
    {"id": 4, "name": "Thor"},
    {"id": 5, "name": "Clive"},
    {"id": 6, "name": "Hicks"},
    {"id": 7, "name": "Devin"},
    {"id": 8, "name": "Kate"},
    {"id": 9, "name": "Klein"},
]
friendship_pairs = [(0, 1),(0, 2),(1, 2),(1, 3),(2, 3),(3, 4),
                    (4, 5),(5, 6),(5, 7),(6, 8),(7, 8),(8, 9)]

friendships = {user["id"]: [] for user in users}

for i, j in friendship_pairs :
    friendships[i].append(j)
    friendships[j].append(i)

# [1번 문제] 사용의 평균 연결 수
total_connections = sum(number_of_friends(user) for user in users)
num_users = len(users)
avg_connections = total_connections / num_users
print("사용자들의 평균 연결선 : ",avg_connections) # output : 2.4

# [2번 문제] 친구 연결선이 가장 많은 순으로 정렬하기
num_friends_by_id = [(user["id"], number_of_friends(user)) for user in users]
num_friends_by_id.sort(key = lambda id_and_friends: id_and_friends[1], reverse = True)
print("친구 관계가 가장 많은 순으로 정렬 : ",num_friends_by_id) # output : [(1, 3), (2, 3), (3, 3), (5, 3), (8, 3), (0, 2), (4, 2), (6, 2), (7, 2), (9, 1)]