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

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..

* 문제 N개의 원소로 구성된 자연수 집합이 주어짐 이 집합을 두개의 부분집합으로 나눔 ex. 1 3 5 6 7 10 을 1 3 5 7 과 6, 10 으로 그리고 두 부분집합의 합이 같은 경우가 존재하는지 확인 부분집합의 합이 같은 경우가 있다면 YES 출력 아니면 NO 출력 단, 입력에서 원소는 중복되지 않는다. * 풀이 - 재귀함수를 돌리면서 부분집합을 구함 - 남아있는 원소들 즉, 사용하지 않은 부분집합도 만들어짐 - total에다가 입력받은 원소를 다 더함 - 재귀로 부분집합을 만들어서 합을 만듬 sum - 남아 있는 원소들의 합은 total - sum 이 같으면 두 부분집합이 같은 것임 - 두 부분집합의 합은 같아야 하기 때문에 한쪽의 부분집합의 합이 절반이상이면 항상 NO됨 (다른 한쪽이 작아..

문제: 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 재귀를 이용한 완전탐색을 하며, 이진트리 전위순회 방식으로 출력하시오. 단 공집합은 출력X 입력 3 출력 1 2 3 1 2 1 3 1 2 3 2 3 *풀이 : 전위순회: 루트가 가장먼저 순회되는 것 => 왼쪽자식 => 오른쪽자식 - LEVEL 1 2 3 4로 두기 => L로 컨트롤하기 - ch 배열은 0으로 초기화 - 왼쪽으로 자식함수 넘어갈때는 체크 1, 오른쪽은 체크 0하면서 호출한다. - ch의 인덱스번호를 원소값으로 보자. - if(L == n+1) 종료지점, 여기서 ch배열을 찍어준다. 1 2 3 - D(3)으로 다시갔다가 D(4)로 갈때 ch[L] = 0을 넣는다 L은 이때 3임 -..