백준
2213_트리의 독립집합
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 문제에 나온 트리는 1번을 루트노드라고 생각한다면 위와 같은 구성을 가지게 된다. 그렇다면 어떻게 하면 가중치를 더해갈 수 있을지 생각해보자. 먼저 자식부터 검사를 하는 것이 좋을 것이다. 5->4->3->7->6->2->1 순서로 탐색을 한다. 어떤부분을 탐색할때 자식노드와 부모 노드가 있다고 생각하면, 부모노드가 독립집합 안에 속해있다면 자식노드는 속할 수 없고..
15681_트리와쿼리
https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리 구조를 받아온 후에, dfs로 노드를 후위순위하면서 뒤에서부터 서브트리의 개수를 더해주면 된다. 각 자식트리의 서브트리를 더해주는 형태라고 생각하면 된다. 처음에 bfs를 사용해서 그때 그때 개수를 구했는데그러며 시간초과가 나니 생각해두면 될 것 같다. import sys from collections import deque sy..
17472_다리만들기2(Python,설명) 반례...?
https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 삼성A형 기출문제라서 살짝 긴장하고 풀었다. 어려운 문제였다... 시간도 많이 걸렸지만 스스로 풀어서 되게 뿌듯한 문제였다. 아래와 같은 과정으로 순서대로 해결하여 접근하였다. 1. 문제에서 입력으로 준 지도를 2차원 리스트에 저장 2. 각 좌표를 트리구조처럼 만들기 위해 부모 배열을 만든다. 이때 부모배열또한 2차원으로 자신을 가르키도록 만든다. 3. 해당 구조에 맞는 fi..
1774_우주신과의 교감
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 이전 문제와 비슷하게 풀 수 있다. 1. 각좌표 받기 2. 연결되어 있는부분 노드 받기 3. 각 노드들간 거리를 계산해놓는 배열 만들기 [ (1,2,거리), (1,3,거리),(1,4,거리).... (n-1,n,거리) ] 로 만들어야 한다. 이때 1번 부터 시작인걸 생각하고 만들어야 한다. 4. 배열을 거리순으로 오름차순 정렬 ( 가까운 순서대로 ) 5. 부모 배열 만들기..
4386_별자리만들기
https://www.acmicpc.net/status?user_id=supersfel&problem_id=4386&from_mine=1 채점 현황 www.acmicpc.net 이역시 유니온파인드를 활용한 크루스칼 알고리즘을 활용하여 해결하였다. 처음에 각 별들의 좌표를 받는데, 이를 활용해서 각 별간의 거리를 모두 저장해주었다. 각 별들에게 1번,2번 .... 이름을 붙여주고 1-2 간의 거리 1-3번간의 거리... 를 반복해서 n-1,n번과의 거리까지 구해준다. 그 후 거리순으로 배열을 정렬해준 후에, 부모가 같지 않으면 두 집합을 합쳐준다. import sys input = sys.stdin.readline n = int(input()) star=[] for _ in range(n): x,y = m..
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 최소 스패닝 트리는 간선의 합이 가장 적은 트리이다. 이를 위해서는 아래와 같이 해결하면 된다. 먼저 가중치를 기준으로 해서 간선의 정보를 정렬한다. 만약 1 2 3 2 3 2 1 3 1 와같이 입력이 들어온다면 1 3 1 2 3 2 1 2 3 과 같이 가중치가 작은 순으로 정렬을 해준다. 그 이후, 간선들과 연결된 노드들이 같은 트리에 있는지 확인한..