Daily Log

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

* 문제 : 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

- 32번 복습하기 - 분할정복? https://kugistory.net/76 분할정복법 (Divide and Conquer) 알고리즘 영역에서 분할정복법(Divide-and-Conquer)은 말 그대로 주어진 문제를 분할하여 해결하는 방법을 말한다. 즉, 한 번에 해결하기 어려운 문제를 작은 단위의 부문제들(subproblems)로 쪼개어 해결하는 방.. kugistory.net https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html [알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io *문제 병합정렬로 주어진..

* 문제 N개의 원소로 구성된 자연수 집합이 주어짐 집합의 원소와 +, - 연산을 사용하여 특정수인 M을 만드는 경우가 몇가지 있는지 출력하시오. 각 원소는 연산에 한번만 사용한다. - 입력예제 4 12 2 4 6 8 => 원소 4개로 + -를 조합하여 12를 만드는 경우의 수는 몇가지? 경우가 없다면 -1 출력 * 문제 풀이 2를 보면 +2 -2 X 와 같은 3가지 경우 적용가능 4도 마찬가지 +4 -4 X 와 같은 3가지 경우 적용 가능 -2 +6 +8 = 12 은 어떻게 나오나? 깊이 탐색으로 모든 경우의 수 탐색해서 가능 => 완전탐색 - 레벨 5되고 종료! * 코드 구현 //61번 - 특정 수 만들기 #define _CRT_SECURE_NO_WARNINGS #include #include int..