Dalin's Archive

문제 보러 가기! 접근 전에 트리를 배우고 이 문제도 풀고 싶었다.. 문제는 간단하지만 어떻게 풀지 몰랐다가 스터디에서 이 문제를 다뤘다. 트리의 지름을 찾고 싶으면, 임의의 정점 x를 잡고 거기에서 가장 먼 정점 y를 찾으라고 했다. 그리고 y에서 가장 먼 정점 z가 있을 텐데, y와 z 사이의 거리가 트리의 지름이라고 하셨다. 뭔가 수학적으로도 설명해주셨고 쉽게 원그림으로도 설명해주셨다. 원 안의 어떤 점 x를 잡고 거기에서 젤 먼 점 y를 잡으면 어떻게 될까? x에서 원의 중심을 지나서 원의 호가 y가 될 것이다. 그리고 y에서 가장 먼 점 z를 찾으면, 원의 어떤 호에서 중심을 지나서 다른 호로 갈 것이다. 그럼 그게 원의 지름이 된다. 이 아이디어를 구현해봤다! 코드 import sys inpu..

문제 보러 가기 접근 일단 인접한 노드들을 저장해주었다. 어디가 부모인지, 어디가 자식인지 모르니까 일단은 방향 없이 모두~ 그리고 루트를 1로 삼고 거기에서부터 쭉~ 자식을 보러 갔다. 부모를 저장하는 리스트를 만들어서 부모 노드가 몇번 노드인지 저장해줬다. 인접한 노드들을 쭉~ 보되 이미 방문 체크가 되었다면 보지 않았다. 이미 방문 체크가 되었다면, 자식이 아니라 부모라는 뜻이니까.. 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 5) N = int(input()) adj = [[] for _ in range(N + 1)] for _ in range(N - 1): a, b = map(int, input().split()) ..

트리.. 몇 번 들어본 것 같기는 한데, 잘은 모르고 있었다. 이번에 싸피에서도 트리를 배웠는데, 마침 스터디 과제로도 이 문제가 있어서 반가웠다 ㅎㅎ 접근 🤔 맨 처음에는 한 명의 직속 상사가 여러 명의 직속 부하가 있는 걸 생각 못해서 틀렸다. 그 다음에는 칭찬을 받을 때마다 쭉 ~ 내려 보내서 시간 초과가 나왔다. (칭찬 받을 때마다, 그 칭찬받은 당사자를 루트 삼아서 쭉 트리를 순회하면서 직속 부하, 그 직속 부하, 그 직속 부하...에게 compliment 리스트에 칭찬의 수치를 더해줬다.) 그래서 일단은 칭찬이 입력될 때, 칭찬 받은 그 당사자만 칭찬을 받게 했다. (compliment 리스트에 더해서) 그 후에 트리를 1부터 전위 순회했다. 그러면서 직속 상사가 칭찬 받은 걸 더해서 받게 했..

문제 보러 가기! 트리 순회를 구현하는 문제! 숫자가 아니라 알파벳으로 들어와서, 그걸 숫자로 바꿔주는 것만 신경쓰면 될 것 같다! N = int(input()) # 노드의 개수 tree = list([0] * 2 for _ in range(N + 1)) # 왼쪽 자식, 오른쪽 자식 def pre_order(node): # 전위 순회 if node: print(chr(node+64), end='') # 할 일 pre_order(tree[node][0]) # 왼쪽 자식 pre_order(tree[node][1]) # 오른쪽 자식 def mid_order(node): # 중위 순회 if node: mid_order(tree[node][0]) # 왼쪽 자식 print(chr(node+64), end='') #..

문제 보러 가기! 아이디어 라고 할 것도 없는 것 같다. 다익스트라로 풀었다.. 다익스트라..는 전에도 들어는 봤지만, 딱히 공부하지는 않았었다. 이번 기회에 다익스트라를 공부할 수 있었다! 참고한 자료 안경잡이 개발자님의 글과 레드캐럿님의 벨로그 포스팅!!. 안경잡이 개발자님은 영상으로도 있어서, 다익스트라가 뭔지 이해하는 데 도움이 되었고, 레드캐럿님의 벨로그 포스팅은 파이썬 코드라서 코드 구현을 어떻게 해야 할지 알 수 있었다!! 또 플로이드워셜과의 차이점도 궁금했는데, 잘 설명해주셔서 좋았다 ㅎㅎ 코드 👩‍💻 import heapq import sys input = sys.stdin.readline V, E = map(int, input().split()) # 노드 개수, 간선 개수 start =..