Daily Log

1. 노드 배열을 만들어서 1번 정점은 0으로 초기화하고 나머지는 무한대값(아주큰값)으로 최대한 해놓음 2. 돌면서 최솟값을 찾음 3. 1번정점 체크 4. 1번 정점에서 갈 수 있는 방향으로 다 간다. 5. dist 배열을 relax해준다. => 값이 더 좋으면 바꿔준다. 6. dist[2] 를 보면 무한대로 되어 있기 때문에 가중치값 12는 좋은 값이기에 바꿔준다 dist[2] = 12 7. 1번에서 3으로 갈 수 있다. => dist[3] = 4 로 바꿔준다. 8. 1번은 한번 사용했기 때문에 다시 사용 못함 9. 2, 3번 중 작은 값인 3번이 선택됨 => dist[3]은 체크 걸어둠. 그리고 이제 dist[3] 인 3번 정점에서 다시 감 10 .1에서 3번 정점으로 가는 최솟값인 4는 선택되었기에..

1. 먼저 간선을 가중치 값으로 오름차순으로 정렬한다. 2. 간선을 선택해가면서 싸이클이 되어버리면 선택하면 안된다! 아무리 간선 가중치 값이 적다고 해도! 3. 2번 정점과 9번 정점은 최소비용신장트리의 원소로 들어옴 => 이때 Union & Find로 집합을 만들어서 연결시켜버린다. 4. 2와 3을 연결하는 가중치값 10 인 간선 => 이 간선을 선택하느냐 마느냐에서 2번 정점을 find로 하고, find 3을 하여 둘이 서로 다른 집합이면 연결한다. 2와 3도 Union 한다. 5. 이런식으로 계속 간선값을 누적한다. 6. 이미 2번과 8번 정점은 연결되어 있는 상태이기 때문에 선택하지 않는다. => 회로가 되면 안된다! 싸이클을 피해라! 7. find 8 find 9는 이미 트리의 집합의 원소로 ..

우선순위큐 - 맥스힙 구조 STL 사용 최대힙/최소힙 관련 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html [자료구조] 힙(heap)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 최대힙 최대힙을 사용한 우선순위큐 STL 을 통해 문제를 풀어보자 // 73번 - 최대힙(priority_queue : 우선순위 큐) #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int main() { freopen("input.txt", "rt", ..

입력 - 왕자의 수 n - 특정숫자 k 출력 - 최후의 남은 왕자 풀이 - - 원탁을 Q로 생각한다. // 72번 - 공주구하기 : 큐 자료구조로 해결 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int main() { int n, k; queue Q; scanf("%d %d", &n, &k); for (int i = 1; i

* 문제 최소 몇번의 점프로 현재 위치 S에서 송아지 위치 E까지 갈 수 있는지 - 직선의 좌표점은 1부터 10000까지 - 한번의 점프로 앞으로 1 뒤로 1 앞으로 5까지 갈 수 있다. ex. 현재 위치 5에서 송아지 위치 14까지는 3번만에 갈 수 있다. 10 15 14 +5 +5 -1 어떤 정점에서 어떤 정점까지 최단거리!를 구하여라 이런 것은 BFS 사용 * 상태트리 만들기 1. 5를 만들고 5에서 한번만에 갈 수 있는 것 다 트리로 만들기 2. 각 트리에서 또 2번만에 갈 수 있는 지점 만들기 이미 큐에 들어간 자료 ex.5는 체크를 걸어서 다시는 큐에 들어가지 않게 체크를 해버린다. 큐에 넣어가며, 상태트리를 만들며 1번 만에 가는 것 보기 2번 만에 가는 것 보기 3번 만에 가는 것 보기 ...

* 문제 : 1번에서 각 정점으로 가는 최소 간선 수를 2번 정점부터 차례때로 출력하시오 - 여기서 dis 배열은 각 정점까지 가는 최소 간선의 수가 저장됨. 3번만에 2번으로 가면, 이미 체크가 되어있어서 4번만에 안감 - 1번을 큐에 넣고, 1번만에 갈 수 있는 정점을 찾음 => 3을 체크함 => 3을 큐에 넣고 => dis 배열의 3번 정점의 값을 기록한다 1번정점의 길이와 3번까지 가는 간선수 합해서 입력함 - 1번만에 갈 수 있는건 또 4번 정점 => 4번을 큐에 넣고 4번 dis배열 1 기록 // 69번 - 넓이우선탐색 BFS (큐 자료구조 구현) // 무방향 그래프리스트 #include #include #include using namespace std; int Q[100], front = ..

이진트리 넓이 우선 탐색 * 넓이우선 탐색이란? BFS = level 탐색 1번 노드를 탐색한다 - 1 level 1번 노드에서 1번만에 갈 수 있는 모두를 방문한다. - 2 level 1번 노드에서 2번만에 갈 수 있는 모두를 방문한다. - 3 level 1 2 3 4 5 6 7 * 레벨 탐색 할때 QUEUE 큐라는 자료구조를 사용한다. https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html [자료구조] 큐(Queue)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io -큐는 먼저 들어간 것이 먼저 나오는 것 FIFO - First In First Ou..

* 문제 가중치 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 최소비용을 출력하는 프로그램을 작성하세요. (!)목적지까지 가는 최소 비용은 보통 "다익스트라 알고리즘" 사용함 인접행렬 활용 // 67번 - 최소비용 DFS 인접행렬 (가중치 방향그래프) #define _CRT_SECURE_NO_WARNINGS #include int n, a, b, c, map[30][30], ch[30], cost = 999999999; //cost는 minimum value void DFS(int v, int sum) { if (v == n) { if (sum < cost) cost = sum; } else { for (int i = 1; i 0 && ch[i] == 0) { ch[i] = 1; DFS(i, s..

64번은 인접행렬로 풀었지만 66번에서는 인접 리스트로 경로를 찾아보자. 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. ▣ 입력설명 첫째 줄에는 정점의 수 N(1

64번 - 경로탐색 DFS(노드, 간선) * 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 첫째줄: 정점의 수 N(1