[엘카데미 챌린지] 21일차 파이썬 알고리즘 (8) 마무리

1. 개요

오늘도 어김없이 알고리즘 문제를 풀이하였다.

딕셔너리를 이용해 동명이인을 찾는 문제와 큐를 이용해 모든 친구를 찾고 친밀도를 계산하는 문제를 풀이하였다.

오늘부로 엘카데미 챌린지가 종료되었다. 3주간 알차게 학습한 것 같다. 앞으로도 포스팅은 계속 이어나갈 것이다.

---

2. 문제

1) 딕셔너리를 이용해 동명이인을 찾는 알고리즘

n명의 사람 이름 중에 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 생각해 보자.

리스트 s를 매개 변수로 받아 딕셔너리에서 등장 횟수가 2 이상인 것들 결과에 추가하여 집합 result에 저장해 반환하는 함수 find_same_name을 작성하라.

 

풀이

1. 각 이름이 등장하는 횟수를 저장할 빈 딕셔너리(name_dict) 생성
2. 입력으로 주어진 리스트에서 각 이름을 꺼내면서 반복
3. 주어진 이름이 name_dict에 있는지 확인
4. 이미 있다면 등장 횟수를 1 증가
5. 아직 없다면 그 이름을 키(key)로 하는 항목을 새로 만들어 1을 저장
6. 1~5번 과정을 거치면 name_dict에는 리스트에 등장하는 모든 이름과 각각의 등장 횟수가 저장
7. 만들어진 딕셔너리에서 등장 횟수가 2 이상인 이름을 찾아 결과 집합에 넣은 다음 출력으로 반환

def find_same_name(names):
    name_dict = {}
    result = set()

    for name in names:
        if name in name_dict:
            name_dict[name] += 1
            if name_dict[name] >= 2:
                result.add(name)
        else:
            name_dict[name] = 1

    return result

name = ["Tom", "Jerry", "Mike", "Tom"]
print(find_same_name(name))

name2 = ["Tom", "Jerry", "Mike", "Tom", "Mike"]
print(find_same_name(name2))

---

2) 모든 친구를 찾는 알고리즘

친구 관계를 이용하여 어떤 한 사람이 직접 또는 간접으로 아는 모든 친구를 출력하는 알고리즘을 생각해보자.

리스트 g와 문자열 변수 start를 매개 변수로 받아 자신의 친구를 모두 출력하는 함수 print_all_friends을 작성하세요.

 

풀이

1. 앞으로 처리할 사람을 저장할 큐(qu) 생성
2. 이미 큐에 추가한 사람을 저장할 집합(done) 생성
3. 검색의 출발점이 될 사람을 큐(qu)와 집합(done)에 추가
4. 큐에 사람이 남아 있다면 큐에서 처리할 사람을 꺼내기
5. 꺼낸 사람을 출력
6. 꺼낸 사람의 친구들 중 아직 큐(qu)에 추가된 적이 없는 사람을 골라 큐(qu)와 집합(done)에 추가
7. 큐에 처리할 사람이 남아 있다면 4번 과정부터 다시 반복

from collections import deque

def print_all_friends(g, start):
    qu = deque()  # 처리할 사람을 저장하는 큐
    done = set()  # 이미 큐에 추가한 사람을 저장하는 집합

    qu.append(start)
    done.add(start)

    while qu:
        person = qu.popleft()
        print(person)

        for friend in g[person]:
            if friend not in done:
                qu.append(friend)
                done.add(friend)

# 친구 관계 리스트
fr_info = {
    'Summer': ['John', 'Justin', 'Mike'],
    'John': ['Summer', 'Justin'],
    'Justin': ['John', 'Summer', 'Mike', 'May'],
    'Mike': ['Summer', 'Justin'],
    'May': ['Justin', 'Kim'],
    'Kim': ['May'],
    'Tom': ['Jerry'],
    'Jerry': ['Tom']
}

print("All friends of Summer:")
print_all_friends(fr_info, 'Summer')
print()

print("All friends of Jerry:")
print_all_friends(fr_info, 'Jerry')

---

3) 모든 친구를 찾아서 친밀도를 계산하는 알고리즘

예를 들어, A와 B가 친구이고 B와 C가 친구라고 가정해 보자 (A−B−C)

A를 기준으로 B의 친밀도는 1, B를 기준으로 C의 친밀도는 1입니다.

한편, A와 C는 B를 통해 친구의 친밀도가 되었으므로 A를 기준으로 C의 친밀도는 2라는 것을 쉽게 알 수 있다.

일반적으로 A라는 사람과 X라는 사람의 친밀도가 n이면 X의 친구 Y는 A와 친밀도가 (n+1)이 된다.

이 성질을 이용하여 어떤 사람의 친구들을 큐에 넣을 때 친밀도를 1씩 증가시키면 된다.

위 알고리즘을 참고하여 친구 리스트에서 자신의 모든 친구를 찾아 친밀도까지 출력하는 프로그램을 작성해 보자.

 

풀이

from collections import deque

def print_all_friends(g, start):
    friend_distances = {}  # 친밀도를 저장하는 딕셔너리
    queue = deque([(start, 0)])  # 시작 노드와 친밀도 0을 큐에 추가

    while queue:
        person, distance = queue.popleft()

        # 만약 이미 친밀도가 계산된 사람이라면 무시하고 다음 사람을 처리
        if person in friend_distances:
            continue

        # 현재 친구의 친밀도를 저장하고, 모든 친구들을 큐에 넣어 친밀도를 1 증가
        friend_distances[person] = distance
        for friend in g[person]:
            queue.append((friend, distance + 1))

    # 결과 출력
    for person, distance in friend_distances.items():
        print(f"{person} {distance}")


# 주어진 친구 정보로 테스트
fr_info = {
    'Summer': ['John', 'Justin', 'Mike'],
    'John': ['Summer', 'Justin'],
    'Justin': ['John', 'Summer', 'Mike', 'May'],
    'Mike': ['Summer', 'Justin'],
    'May': ['Justin', 'Kim'],
    'Kim': ['May'],
    'Tom': ['Jerry'],
    'Jerry': ['Tom']
}

print_all_friends(fr_info, 'Summer')
print()
print_all_friends(fr_info, 'Jerry')

---

3. 사용된 자료 구조 개념

딕셔너리는 정보를 찾는 기준이 되는 키(key)와 그 키에 연결된 값(value)의 대응 관계를 저장하는 자료 구조

 

---

4. 후기

21일동안의 엘카데미 챌린지를 마무리 하면서.

3주간의 챌린지를 하루도 빠짐없이 진행하면서 하루에 알고리즘 한 두개라도 반드시 풀이하는 습관을 가질 수 있었다.

강의 1개 무료 수강권을 받았기 때문에 그걸 활용해서 무료강의가 아닌 더 좋은 강의들도 들어볼 예정이다.

3주간 SQL 레벨 테스트부터 시작해서 자바스크립트 문법 정리, 자바 알고리즘 풀이, 파이썬 알고리즘 풀이까지 알차게 학습하였던 것 같다. 포스팅은 계속 이어나갈 것이고, 다음에 또 좋은 기회가 있으면 하는 바람이 있다.