코딩성장스토리

오랜만에 문제를 풀다가 헷갈리는 부분들이 있어서 정리를 해본다.. 최소 스패팅 트리 모든 노드에서 가중치 합이 가장 작은 트리를 만드는 것 크루스칼 vs 프림 크루스칼 알고리즘 간선의 길이가 짧은 것 부터 시작해서 사이클이 생기지 않게 간선을 추가하는 방식 프림 알고리즘 한 시작 노드를 정한 후에 노드에 연결된 간선 중 최소 값을 선택하여 확장해나가는 방식 크루스칼 알고리즘 구현 // 유니온 파인트도 사이클 체크 int findparent(int x){ if(x==findparent(parent[x])){ return x; }else{ return parent[x]=findparent(parent[x]); } } void uni(int x,int y){ x=findparent(x); y=findparen..

https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 이 문제를 풀 떄 트라이라는 자료구조를 알고 풀면 더 쉽게 접근이 가능하다. 처음에는 나도 트라이라는 것이 생소해서 공부를 시작하고 풀었다. 그리고 문제를 풀때 다른 사람 코드를 참조했다...(아직 트라이는 어색하다..ㅜㅜ) 트라이란? 단순히 말해서 트리구조이다. 이걸 문자열에 특화되게 만든게 트라이 라는 것이다. (처음에는 포인터 부분이 약해 이해가 잘 안되는데 그냥 해당 노드에 ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이 문제는 다익스트라 문제이다. 하지만 ! 기존에 하던 다익스트라 방식으로는 시간초과가 난다.. 그래서 왜지... 라는 의구심을 가지고 생각을 해봤다.. 아래가 시간초과가 난 코드다 . 이 코드의 잘못된 점을 찾아보면 방문된 점의 처리가 제대로 안되어 있다는 것이다. 인접한 점의 노드의 간선들을 모두 우선순위 큐에 넣는 방식이다. 이때 이미 방문했던 노드들은 굳이..

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 이 문제는 최소신장 트리 이다. 최소 신장 트리는 크루스칼 알고리즘과 프림 알고리즘으로 풀 수 있는데 나는 BFS에 우선순위 큐만 더하면 된다고 생각해서 프림 알고리즘으로 풀었다. 프림 알고리즘은 간단하게 시작 노드에서 가중치가 작은 간선을 이어가며 구하는 것이다. 크루스칼 알고리즘은 사이클이 생성되지 않게 작은 가중치를 가진 간선을 연결하는 것이다...