본문 바로가기

프로그래밍/백준

 (146)
백준 1949 우수마을 - 파이썬 문제. 풀이. dp[i]0는 i를 포함한 집합 가중치의 최댓값, dp[i][1]을 i를 포함하지 않은 부분 집합 가중치의 최댓값으로 지정하고 dfs를 이용하여 최댓값을 찾아주면 된다. 소스코드.
백준 15681 트리와 쿼리 - 파이썬 문제. 풀이. dfs를 루트노드부터 시작해서 각각의 서브트리의 갯수를 계산하면된다. 소스코드.
백준 2887 행성 터널 - 파이썬 문제. 풀이. 입력을 받고 좌표마다 거리를 구해서 풀었는데 메모리 초과가 나왔다. 그래서 x, y, z를 따로 입력받아서 각각 인덱스마다 최소거리를 구한다음에 크루스칼 알고리즘을 실행하면된다. 소스코드.
백준 1774 우주신과의 교감 - 파이썬 문제. 풀이. https://turret1234.tistory.com/182 백준 4386 별자리 만들기 - 파이썬 문제. 풀이. 크루스칼 알고리즘을 이용해서 풀었다. https://turret1234.tistory.com/181 백준 1197 최소 스패닝 트리 - 파이썬 문제. 풀이. 크루스칼 알고리즘 이용하여 풀었다. https://ko.wikipedia.org/wiki/.. turret1234.tistory.com 풀이랑 거의 똑같은데 이미 이어져있는 점의 입력이 들어올때 미리 union 연산을 해주면 된다. 소스코드.
백준 4386 별자리 만들기 - 파이썬 문제. 풀이. 크루스칼 알고리즘을 이용해서 풀었다. https://turret1234.tistory.com/181 백준 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 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과.. turret1234.tistory.com 랑 거의 유사한 문제이다. 입력 값 대로 거리를 계산해서 그래프를 만드는 부분을 제외하면 똑같다. 소스코드.
백준 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 이므로 사이클이 완성됐다. 소스코드.

티스토리툴바