푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 기본적인 위상 정렬 문제이고 문제에서 주어진 "가능하면 쉬운 문제부터 풀어야 한다"의 조건을 주의해야 합니다. 문제의 숫자가 높아질수록 난이도가 올라가므로 우선순위 큐를 오름차순으로 정렬해서 큐를 돌려주면 됩니다. ✏️ 문제 코드 #include #include #include using namespace std; ve..

Algorithm 공부 #18 - 그래프(최소 신장 트리) 최소 신장 트리(minimum spanning tree) ● 그래프에서 모든 노드를 연결할 때 사용한 에지들의 가중치의 합을 최소로 하는 트리 ● 사이클이 포함되면 최소 가중치를 계산할 수 없으므로 사이클을 포함시키지 않는다 ● N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 N-1개 ● 최소 신장 트리 구현 방법 1. 에지 중심으로 저장하므로 에지 리스트로 그래프 표현, 사이클 표현을 위해 유니온 파인드도 함께 사용 2. 그래프를 가중치를 기준으로 오름차순 정렬 3. 가중치가 낮은 에지부터 연결하기(이때 바로 연결하지 않고 두 노드의 사이클 여부를 판단해야 함) 4. 사이클이 생성되지 않는다면 두 노드를 연결, 사이클이 생기면 연..

Algorithm 공부 #16 - 다익스트라 알고리즘  ✏️ 다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프 상에서 한 정점에서 다른 정점들간의 최단 거리를 구할 수 있는 알고리즘이다.즉 도착 정점 뿐만 아니라 모든 다른 정점가지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다.매번 최단 경로의 정점을 선택해 탐색을 반복한다고 생각하면 될 것 같다.시간복잡도는 O(ElogV)이며 이때 특징으로는 에지값이 모두 양수여야 한다.최단 거리 알고리즘은 이외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있는데 이 알고리즘들은후에 포스팅을 할 예정이다.  ✏️ 구현 방법출발 노드와 도착 노드를 설정'최단 거리 테이블'을 초기화(출발 지점을 0으로, 나머지는..

✏️ 문제 링크 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 큐 중에서도 우선순위 큐를 이용해서 푸는 문제 우선순위 큐를 생성하고 compare구조체를 만들어서 조건에 맞게 출력하도록 해야함 1. x가 0인 경우 if(큐가 비어있지 않다면) 절댓값이 가장 작은 값을 => 같은 게 있다면 음수를 출력 그리고 그 값을 제거 if(큐가 비어있다면) 0을 출력 2. x가 0이 아닌 경우 : x를..