728x90 ALGORITHM/BAEKJOON42 [BOJ/Python] 1197. 최소 스패닝 트리 📌 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 📌 문제 접근 방법 크루스칼 알고리즘을 사용해서 구현하였다. 가중치를 기준으로 오름차순 정렬한 후, 정렬된 순서대로 간선을 선택하여 사이클이 만들어지지 않는다면 (간선에 연결된 노드 2개가 같은 집합이 아니라면) 노드를 연결하고 가중치를 total에 더해준다. 📌 코드 # 백준 1197 최소 스패닝 트리 def find_set(x): if x.. 2021. 10. 21. [BOJ/Python] 1717. 집합의 표현 📌 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 📌 문제 접근 방법 상호배타 집합의 find_set연산과 union연산을 구현해서 풀이하였다. 시간초과가 났는데, 해결을 위해서 재귀 깊이를 설정해주고 input을 sys.stdin.readline으로 바꿔줬다. 최대 재귀 깊이는 어떻게 계산해야 하는지 궁금해졌다! 지금까지는 아무거나 큰 값으로 넣어줬는데 어떻게 계산해야하지? 📌 코드 # 백준 1.. 2021. 10. 21. [BOJ/Python] 17144. 미세먼지 안녕! 📌 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 📌 문제 접근 방법 단순 구현 문제! 문제가 시키는 대로 따라서 구현하면 된다. spread 함수를 만들어서 미세먼지가 퍼지도록 한다. dust라는 배열을 따로 만들어서 각 위치의 먼지 변화량을 저장하고 원래 배열과 더해준다. clean 함수를 만들어서 공기청정기를 가동시킨다. 공기청정기의 위치와 방향을 매개변수로 받아서 해당하는 방향대로 값을 swap해준다. 2, 3의 과정을 T번만큼.. 2021. 10. 20. [BOJ/Python] 14981. 톱니바퀴 📌 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 📌 문제 접근 방법 톱니바퀴의 상태를 deque을 이용해서 받아서 원형큐라고 생각하고 코드를 구현했다. 시계방향으로 회전일 경우, 맨 마지막 원소를 빼서 맨 첫 번째에 삽입해줬다. 반시계방향으로 회전일 경우, 맨 첫 번째 원소를 빼서 맨 마지막에 삽입해줬다. 그리고 회전이 일어나는 경우, 앞 뒤 바퀴와 원소를 비교해서 맞물린 부분이 다르면 해당 바퀴도 재귀로 회전을 시켜줬다. 이 때,.. 2021. 10. 14. 이전 1 2 3 4 5 6 7 ··· 11 다음 728x90