[TIL_Carrotww] 53 - 22/11/16

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 가장 먼 노드 Level 3
3레벨 치고는 쉽다. bfs가 이제는 제일 쉬운 것 같다.

• 풀이

from collections import deque, defaultdict
import math

def solution(n, edge):
    path = defaultdict(list)

    for a, b in edge:
        path[a].append(b)
        path[b].append(a)

    far = {x:math.inf for x in range(1, n + 1)}

    far[1] = 1
    queue = deque([1])

    while queue:
        cur_node = queue.popleft()
        cur_far = far[cur_node]
        for i in path[cur_node]:
            if cur_far + 1 < far[i]:
                far[i] = cur_far + 1
                queue.append(i)

    return list(far.values()).count(max(far.values()))

far 이라는 딕션어리를 만들어서 key 값에 n 만큼 넣어주고 value에 무한대 값을 준 다음 방문 시 거리가 작을때 갱신 하는 식으로 DP 느낌으로 풀어졌다.
far 가 리스트로 되어있을때는 엄청 느렸는데 dict로 바꾸고 나니 10배는 빨라졌다.

return 값에 count 를 써주었는데 for문을 한 번 더 쓰는게 싫어서 저렇게 써주었다. list로의 변환도 있어서 어떤 방식이 더 빠른지는 모르겠지만 생각나는 대로 일단 써봤다.
나쁘지 않은 것 같다.

count() 함수는 리스트에서만 먹는데 far.values() 가 리스트 형식으로 나와서 type이 리스트 인 줄 알았는데 count가 안되어서 저렇게 바꾸어 주었다.

test = {x:x+1 for x in range(1, 10)}

print(type(test.values())) #<class 'dict_values'>

<class 'dict_values'> 라고 나온다.

🧲 데이터 딕셔너리 란?

🔍 데이터 딕셔너리

• 데이터 베이스 자원을 효율적으로 관리하기 위해 정보를 저장하는 시스템 테이블이다.
• 사용자가 테이블을 생성하거나 변경하는 작업을 할 때, 데이터베이스 서버에 의해 자동으로 갱신되는 테이블이다.
• 사용자는 데이터 딕셔너리를 직접 수정, 삭제 할 수 없다.
• 데이터 딕셔너리는 시스템이 관리하는 테이블이기 때문에 사용자가 봐도 암호기호만 보여져서 알 수 없다.

🔍 데이터 딕셔너리 뷰

• 데이터 딕셔너리의 내용을 사용자가 이해할 수 있는 내용으로 변환하여 제공한다.