[Algorithm] 백준 1058

---

문제

솔직히.. 문제 이해하는데만 오백년 걸리는거 같다.
나는 친구 따로따로 구해서 풀고 있었는데 아니었슴 ㅠㅠㅠ
아니 친구 왤케 많냐ㅋ

풀이

내가 생각한 알고리즘

이 코드는 주어진 입력에 대해 친구 관계를 나타내는 테이블을 생성하고, 각 사용자별 최대 친구 수를 찾는 알고리즘을 구현합니다.

1. 사용자의 수를 입력받습니다.
2. 사용자별로 친구 관계를 나타내는 테이블을 만듭니다. 이 테이블은 각 사용자의 번호를 키로 가지고, 해당 사용자가 친구인 다른 사용자의 번호를 값으로 갖는 딕셔너리입니다.
3. 각 사용자별로 최대 친구 수를 찾는 함수 find_friend를 정의합니다.
   • 함수는 한 사용자의 번호를 인자로 받습니다.
   • 해당 사용자와 친구인 모든 사용자를 포함한 집합을 만듭니다.
   • 이후, 각 친구의 친구도 추가합니다.
   • 자기 자신을 제거하고, 친구 수를 계산합니다.
   • 이 과정을 반복하여 최대 친구 수를 찾습니다.
4. 각 사용자별로 find_friend 함수를 호출하여 최대 친구 수를 찾습니다.
5. 최종적으로 최대 친구 수를 출력합니다.

이 알고리즘은 주어진 친구 관계를 테이블로 나타내고, 각 사용자별로 최대 친구 수를 찾는 것으로써 친구 관계의 네트워크에서 가장 밀접한 관계를 찾는 데 사용될 수 있습니다.

코드

n = int(input())
table = {}
for i in range(n):
    table[i] = set()  # 각 요소 초기화
    s = input()
    for j in range(0, len(s)):
        if s[j] == 'Y':
            table[i].add(j)

final_max_friend = 0
def find_friend(i):
    max_friend = len(table[i])
    temp = set()
    temp.update(table[i])
    for f in table[i]:
        temp.update(table[f])
        temp.remove(i)

        max_friend = max(max_friend, len(temp))
    return max_friend

for i in range(0, n):
    final_max_friend = max(final_max_friend, find_friend(i))

print(final_max_friend)
    

주어진 코드의 시간복잡도와 공간복잡도를 구해보겠습니다.

1. 시간복잡도(Time Complexity):

   • 테이블 초기화: (O(n))
   • find_friend 함수 호출: (O(n^2))
     • 각 사용자마다 find_friend 함수를 호출하므로 (O(n))의 시간이 걸리고, 안쪽 반복문에서 각 사용자의 친구들을 확인하므로 추가적으로 (O(n))의 시간이 소요됩니다.
   • 따라서 전체 시간복잡도는 (O(n^2))입니다.

2. 공간복잡도(Space Complexity):

   • 테이블: (O(n))
   • temp 변수: (O(n))
   • 따라서 전체 공간복잡도는 (O(n))입니다.

이 코드의 시간복잡도는 (O(n^2))이므로 입력 크기가 커질수록 실행 시간이 크게 증가할 수 있습니다. 따라서 더 효율적인 알고리즘을 고려하는 것이 좋습니다.

개선

이 코드에는 몇 가지 개선할 부분이 있습니다:

1. 불필요한 집합 초기화: temp 집합은 매 반복마다 초기화됩니다. 이것은 비효율적입니다. 대신 temp 집합을 find_friend 함수 외부에서 초기화하고 사용하는 것이 좋습니다.

2. 친구 관계 확인 방법: 친구 관계를 확인할 때 temp 집합에 현재 사용자와 그 친구들의 모든 친구를 추가하고 있습니다. 이것은 중복된 작업입니다. 대신에 각 사용자의 친구들만 확인하여 temp 집합에 추가할 수 있습니다.

3. remove 함수 사용: remove 함수는 요소를 직접 제거하므로, 반복문 내에서 사용하는 것은 효율적이지 않습니다. 대신 temp 집합에서 해당 요소를 제거할 필요 없이, 현재 사용자와 그의 친구들만 집합에 추가하면 됩니다.

다음은 개선된 코드입니다:

n = int(input())
table = {}
for i in range(n):
    table[i] = set(input().strip())  # 입력을 직접 집합으로 변환하여 저장

def find_friend(i):
    max_friend = len(table[i])
    temp = set(table[i])  # temp 집합을 복사하여 초기화
    for f in table[i]:
        temp.update(table[f])  # 현재 사용자와 그의 친구들의 친구를 모두 추가
    max_friend = max(max_friend, len(temp) - 1)  # 자기 자신은 제외
    return max_friend

final_max_friend = max(find_friend(i) for i in range(n))  # 모든 사용자에 대해 최대 친구 수를 찾음

print(final_max_friend)

이 코드는 불필요한 작업을 줄이고, 효율적으로 최대 친구 수를 계산합니다.

오호 이런 방법이..

Lesson Learn

딕셔너리

파이썬의 딕셔너리(dictionary)는 키-값(key-value) 쌍을 저장하는 자료구조입니다. 이를 통해 특정 키에 대응하는 값을 빠르게 찾을 수 있습니다. 딕셔너리는 중괄호 {}로 표현되며, 각각의 키-값 쌍은 콜론(:)으로 구분됩니다.

예를 들어, 다음과 같이 딕셔너리를 정의할 수 있습니다:

my_dict = {'apple': 2, 'banana': 3, 'orange': 5}

위의 예제에서 'apple', 'banana', 'orange'는 각각 키이고, 2, 3, 5는 각각 해당 키에 대응하는 값입니다.

딕셔너리에서 특정 키에 대응하는 값을 가져오려면 해당 키를 인덱스로 사용하여 접근합니다. 예를 들어, 위의 딕셔너리에서 'banana'에 대응하는 값을 가져오려면 다음과 같이 합니다:

print(my_dict['banana'])  # 출력 결과: 3

딕셔너리에서 키는 고유해야 하므로 중복된 키를 사용할 수 없습니다. 하지만 값은 중복되어도 상관없습니다.

딕셔너리에 새로운 키-값 쌍을 추가하거나 이미 존재하는 키에 대한 값을 업데이트할 수 있습니다. 이를 위해서는 해당 키를 지정하고 대응하는 값을 할당하면 됩니다. 예를 들어, 위의 딕셔너리에 'grape'에 대응하는 값을 추가하려면 다음과 같이 합니다:

my_dict['grape'] = 4

딕셔너리는 유용한 자료구조로, 특히 다양한 종류의 데이터를 빠르게 검색하고 관리할 때 사용됩니다. 그러나 딕셔너리는 순서가 보장되지 않으므로 순서가 중요한 경우에는 주의해야 합니다.

딕셔너리에 set이나 list를 저장할 수 있는가?

네, 파이썬의 딕셔너리(dictionary)는 키(key)와 값(value)의 쌍으로 데이터를 저장하는 자료구조입니다. 딕셔너리를 사용하면 특정 키를 사용하여 해당 키에 연결된 값을 빠르게 찾을 수 있습니다.

딕셔너리를 사용하는 방법은 다음과 같습니다:

1. 키와 값의 쌍으로 데이터 저장: 딕셔너리에 데이터를 저장할 때는 중괄호 {}를 사용하고, 각 항목은 쉼표로 구분됩니다. 각 항목은 키와 값의 쌍으로 이루어집니다. 키와 값은 콜론 :으로 구분됩니다. 예를 들어, {'apple': 3, 'banana': 5, 'orange': 2}와 같이 저장할 수 있습니다.

2. 키를 사용하여 값에 접근: 딕셔너리의 값을 가져오거나 수정하려면 해당 키를 사용하여 접근합니다. 대괄호 [] 안에 키를 넣어서 해당 키에 연결된 값을 가져올 수 있습니다. 예를 들어, fruits['apple']은 'apple' 키에 연결된 값을 가져옵니다.

3. 딕셔너리의 길이 확인: len() 함수를 사용하여 딕셔너리의 길이(키-값 쌍의 개수)를 확인할 수 있습니다.

4. 키의 중복: 딕셔너리의 키는 고유해야 하지만, 값은 중복될 수 있습니다. 즉, 동일한 키가 딕셔너리에 두 번 이상 나타날 수 없습니다.

5. 값으로는 임의의 데이터형 가능: 딕셔너리의 값으로는 모든 종류의 객체를 사용할 수 있습니다. 정수, 문자열, 리스트, 집합, 다른 딕셔너리 등 어떤 객체도 값으로 사용할 수 있습니다.

딕셔너리는 매우 유연하고 강력한 자료구조로, 다양한 용도로 사용됩니다. 리스트나 집합 등과 함께 사용하여 데이터를 구조화하고 관리하는 데 유용합니다.
다음은 단일 요소, 리스트 및 집합을 딕셔너리에 저장하고 접근하는 예제 코드입니다:

# 단일 요소, 리스트, 집합을 저장하는 딕셔너리 생성
data_dict = {
    'single': 42,
    'list': [1, 2, 3, 4, 5],
    'set': {1, 2, 3, 4, 5}
}

# 딕셔너리에 저장된 값에 접근
single_value = data_dict['single']
list_value = data_dict['list']
set_value = data_dict['set']

print("단일 요소:", single_value)
print("리스트:", list_value)
print("집합:", set_value)

# 리스트 내의 특정 요소에 접근
list_element = list_value[2]  # 인덱스 2에 있는 요소에 접근
print("리스트 내의 특정 요소:", list_element)

# 집합 내의 요소에 접근 (집합은 인덱스로 접근할 수 없으므로 반복문을 사용하여 집합 내의 요소에 접근)
print("집합 내의 모든 요소:")
for element in set_value:
    print(element)

위 코드는 단일 요소, 리스트 및 집합을 저장하는 딕셔너리를 생성하고, 각 요소에 접근하는 방법을 보여줍니다. 딕셔너리의 각 키를 사용하여 해당 값을 가져올 수 있으며, 리스트나 집합 등에서는 인덱스를 사용하여 특정 요소에 접근할 수 있습니다.