Daily Log

우선순위큐 - 맥스힙 구조 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

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