오늘의 학습 키워드

그래프

DefaultDict

• 사전에 기본값을 설정해줘야 할 때
• defaultdict 클래스의 생성자로 기본값을 생성해주는 함수를 넘기면, 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정

from collections import defaultdict

def count_letters(word):
    counter = defaultdict(int)
    for letter in word:
        counter[letter] += 1
    return counter

• defaultdict 클래스의 생성자로 int 함수를 넘긴 이유는 int()는 0을 리턴하기 때문

from collections import defaultdict

def count_letters(word):
    counter = defaultdict(lambda:0)
    for letter in word:
        counter[letter] += 1
    return counter

• int 함수 대신에 lambda: 0를 넘겨도 동일

데이터를 특정 기준에 의해 카테고리로 묶는 경우

from collections import defaultdict

def group_words(words):
    grouper = defaultdict(list)
    for word in words:
        length = len(word)
        grouper[length].append(word)
    return grouper

• 기본값은 Empty List

Q : 만일 중복되지 않은 단어만 필요

from collections import defaultdict

def group_words(words):
    grouper = defaultdict(set)
    for word in words:
        length = len(word)
        grouper[length].add(word)
    return grouper

• list 대신 set으로 초깃값을 설저
• append 대신 add 로 값 추가

참고한 블로그

• https://www.daleseo.com/python-collections-defaultdict/

공부한 내용 본인의 언어로 정리하기

리트 코드 399. Evaluate Division

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

• 입력으로 equations가 주어지고, 해당 값들을 /한 결과 값이 values 가 주어진다.
• 이 식을 통해 값을 유추해 queries 들의 값을 return 하는 함수 작성

어떤 문제가 있었고, 나는 어떤 시도를 했는지

아이디어

• 만들 수 있는 모든 식을 만드는 것 -> 비효율적
• 모든 관계를 식으로 표현하는 것 ...
• 이 문제를 그래프와 어떻게 관련지어 구현할지 모르겠어서 Hint 참고

제출 코드 및 설명

class Solution(object):
    def calcEquation(self, equations, values, queries):
        G = collections.defaultdict(dict)
        for (x,y) ,v in zip(equations, values):
            G[x][y] = v
            G[y][x] = 1/v
        
        def bfs(src, dst):
            # 출발점이나 목적지가 그래프에 없는 경우
            if src not in G or dst not in G:
                return -1.0
            
            # 큐 초기화: (현재 노드, 현재까지의 계산된 값)
            queue = collections.deque([(src, 1.0)])
            visited = set()  # 방문한 노드를 추적하기 위한 집합

            while queue:
                current_node, current_value = queue.popleft()

                # 목적지에 도달한 경우
                if current_node == dst:
                    return current_value
                
                visited.add(current_node)

                # 현재 노드와 연결된 모든 이웃을 확인
                for neighbor, weight in G[current_node].items():
                    if neighbor not in visited:
                        queue.append((neighbor, current_value * weight))
            
            # 경로를 찾지 못한 경우
            return -1.0
        return [bfs(s, d) for s, d in queries]

아이디어

• 각 쿼리 (x,y) 를 우리가 찾으려는 path 라고 생각하면
• 방정식을 간선(edge)으로, 변수를 노드(node)로, 값을 가중치(weight)로 취급하여 가중 그래프(weighted graph)를 구성
• a -> b 간선의 가중치는 value가 되고, b -> a 간선의 가중치는 1 / value가 된다
• Python의 defaultdict(dict)을 통해 구현

쿼리 처리

• BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색)를 사용
• 경로를 따라 이동하면서 만나는 간선들의 가중치를 모두 곱한 값이 최종 답
• 경로가 없으면 -1 return

코드 설명

1. equations, values 로 G(그래프) 생성
2. queries 에서 하나씩 s,d(출발점,도착점)을 가져와서 bfs 실행
3. 만약에 src, des 이 graph 에 없으면 return -1
4. queue , set 초기화
5. queue 가 있는 동안 pop 해서 현재 노드가 도착점과 맞는지 확인
6. 도착점이 아니라면 visted 에 추가하고 , G.items()로 현재 노드와 연결된 다른 노드들을 불러와서 방문했는지 체크, 없으면 append

무엇을 새롭게 알았는지

• bfs/dfs + 그래프의 결합은 너무 생소하고 어려운 것 같다
• bfs/dfs 로 풀수 있다는 것을 몰랐다

학습할 것은 무엇인지

• deque 에 대한 이해 부족
• 그래프에 대한 이해가 부족한 것 같다
• 리트코드가 아직 어려움..