Daily Log

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

* 인접행렬은 그래프를 표현하는 방법 - 정점 node / vertex - 간선 edge - 그래프는 정점과 간선의 집합 무방향그래프 인접행렬로 만드는 법 1) 5 -> 정점의 개수 6 -> 간선의 개수 - 무방향은 1->2 / 2->1 둘다 가능함 - 2차원 배열에 그래프의 연결정보를 넣어주는 것 - 2차원 배열의 행/열 번호가 정의 번호와 1:1대응임 2) 배열은 전역 변수를 잡아서 0으로 초기화 시킴 3) 1,2를 읽었으면 2차원 배열의 (2.1) , (1,2) 둘다 1을 넣어줌 4) 행이 출발 정점, 열이 도착정점 방향그래프 인접행렬로 만드는 법 1) 1->2로만 간다는 것, (1,2)만 체크함 2) 2 5 는 2->5로 가는 것, (2, 5)만 체크함 반대로 체크하게 하면 암됨! 가중치 방향그래..

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