본문 바로가기

트리

 (14)
백준 2213 트리의 독립집합 - 파이썬 문제. 풀이. https://turret1234.tistory.com/187 백준 1949 우수마을 - 파이썬 문제. 풀이. dp[i]0는 i를 포함한 집합 가중치의 최댓값, dp[i][1]을 i를 포함하지 않은 부분 집합 가중치의 최댓값으로 지정하고 dfs를 이용하여 최댓값을 찾아주면 된다. 소스코드. import sys def dfs(star turret1234.tistory.com 최대 값을 구하는 방법은 위 링크와 동일하다. 단 이 문제는 정점을 출력해야하는데, dfs를 이용하여 각 정점에서의 연산을 할 때마다, 거쳐간 정점을 기록하여주고 마지막에 정렬을하여 출력하면 된다. 소스코드.
백준 1949 우수마을 - 파이썬 문제. 풀이. dp[i]0는 i를 포함한 집합 가중치의 최댓값, dp[i][1]을 i를 포함하지 않은 부분 집합 가중치의 최댓값으로 지정하고 dfs를 이용하여 최댓값을 찾아주면 된다. 소스코드.
백준 15681 트리와 쿼리 - 파이썬 문제. 풀이. dfs를 루트노드부터 시작해서 각각의 서브트리의 갯수를 계산하면된다. 소스코드.
백준 1197 최소 스패닝 트리 - 파이썬 문제. 풀이. 크루스칼 알고리즘 이용하여 풀었다. https://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전 컴퓨터 과학에서, 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 E {\displaystyle E} , 꼭짓점의 개수를 V {\displaystyle V} 라고 하면 이 알고 ko.wikipedia.org 소스코드.
백준 9372 상근이의 여행 - 파이썬 문제. 풀이. bfs를 통해서 풀었으나, 간선의 가중치가 없고 모든 간선이 연결되어있다면 노드갯수-1을 출력해도 정답이다. 소스코드.
백준 20040 사이클 게임 - 파이썬 문제. 풀이. 유니온 파인드를 이용해서 풀면된다. 우선 생각해야 할게 유니온 연산을 하기전에 파인드 연산을 먼저해서 둘의 루트 노드가 같다면 사이클이 완성된것이다. 예를 들어 parent = [0, 1, 2, 3, 4, 5] 가 있고 이제부터 입력을 받는다고 한다면 0 1이 들어오면 둘의 파인드 연산을 했을때는 각각 루트 노드가 0 , 1이다 둘의 루트 노드가 다르니 유니온 연산을 시행한다 1, 2 입력이 들어오면 둘의 파인드 연산 결과는 0, 2 2, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 3 0, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 0 이므로 사이클이 완성됐다. 소스코드.
백준 4195 친구 네트워크 - 파이썬 문제. 풀이. 유니온 파인드를 이용해서 풀면 된다. 입력이 문자열이기때문에 딕셔너리를 통해서 풀었다. 2개의 딕셔너리를 선언하고 number 딕셔너리의 루트 노드에 친구 관계의 친구관계의 수를 저장하고 매 단계 루트노드를 출력하면된다. 소스코드.
백준 1976 여행 가자 - 파이썬 문제. 풀이. https://turret1234.tistory.com/176 백준 1717 집합의 표현 - 파이썬 문제. 풀이. 유니온 파인드의 이해가 필요하다. 유니온 파인드는 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용된다. 유니온 파인드에는 유니온 연산과 파인드 연산이 있다 1) Union -> 서 turret1234.tistory.com 위 링크랑 풀이가 거의 유사하다. 입력 조건이 조금 다르지 푸는 알고리즘은 거의 똑같다. 연결된 집합끼리 유니온 연산을 해 주고 여행 계획인 도시끼리 파인드 연산을 해서 모두 같은 집합이라면 yes 아니면 no를 출력하면 된다. 소스코드. import sys # 유니온 (집합 합치기) def union(a, b): a = find(a) b = find(..

티스토리툴바