CS/알고리즘 (19) 썸네일형 리스트형 깊이우선탐색 & 너비우선탐색 (백준 1260번 문제 java풀이) [Silver II] DFS와 BFS - 1260 https://www.acmicpc.net/problem/1260 분류 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 .. DP(동적 프로그래밍) 동적 프로그래밍은 하위의 작은 문제들을 풀고 이를 이용해서 더 큰 문제를 풀어나가는 방법입니다. 모든 동적 프로그래밍 알고리즘은 격자(grid)로부터 시작합니다. 동적 프로그래밍의 특징 모든 답안에는 격자가 있습니다. 격자의 각 칸에는 최적화하고자 하는 값을 적습니다(최대화 또는 최소화). 배낭 문제의 경우에는 모든 물건의 총 가치를 썼습니다. 각 칸은 원래 문제에 대한 하위문제이고, 다른 문제를 하위문제로 가질 수 있습니다. 원래의 문제를 어떻게 하위문제로 나눌 수 있을지 생각해야합니다. 그러면 각각의 축이 어떻게 되어야 하는지 알아내는 데 도움이 됩니다 대표적인 문제로는 배낭채우기 문제가 있습니다. 물건이 3개일 때, 스테레오 $3000 4kg 노트북 $2000 3kg 기타 $1500 1kg dp[].. BFS(너비우선탐색) - 최단 경로 문제를 푸는 알고리즘 최단경로,즉 가장 짧은 것을 찾는 문제. 예를 들어 여러분이 친구 집까지 가는 최단 경로일 수도 있고, 체스 게임에서 체크 메이트를 만드는 데 필요한 최소한의 수 일수도 있습니다. 이렇게 최단 경로 문제를 푸는 알고리즘을 너비 우선 탐색이라고 합니다. 문제를 풀기 위해선 다음과 같은 절차가 필요합니다. 문제를 그래프로 모형화한다 너비 우선 탐색으로 문제를 푼다 너비 우선 탐색은 다음과 같은 두 가지 종류의 질문에 대답하는 데 도움이 됩니다. 유형 1. 정점A에서 정점B 로 가는 경로가 존재하는가? 유형 2. 정점A에서 정점B로 가는 최단 경로는 무엇인가? BFS는 Queue를 이용합니다. 망고 판매상을 찾는다고 가정할 경우 나->1촌->2촌->3촌->... 1촌관계인 모든 사람중에서 찾는다 -> 목록에 .. 두 수의 최대공약수는 유클리드 호제법 유클리드 호제법은 다음과 같이 정리할 수 있습니다. 정수 X와 Y(X>=Y)가 주어졌을 때 X를 Y로 나눈 나머지를 R이라고 하면, X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다. 그러나 X와 0이 남았을 경우 최대공약수는 X로 한다. 이를 활용해서 126과 90의 최대 공약수를 구해보자 126(X)와 90(Y)의 나머지 값은 36(R), 90(X) 와 36(Y) 의 나머지 값은 18 (R) , 36(X) 와 18(Y) 의 나머지 값은 0 (R) 따라서 126과 90의 최대공약수는 18이 된다. 참고도서 : 그림으로 배우는 알고리즘 basic - 스기우라 켄 도수 정렬 도수정렬은 요소의 대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다. 데이터를 비교,교환하는 작업이 필요 없어 매우 빠르다. 하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고있을 경우에만 사용할 수 있다. public class CountingSort { public static void main(String[] args) { System.out.println("도수정렬"); System.out.println("요솟수: 7 "); int nx = 7; int[] x = new int[]{22,5,11,32,120,68,70}; int max = x[0]; for (int i = 1; i max) max = x[i]; } count.. 힙 정렬 힙 정렬은 선택 정렬을 응용한 알고리즘이다. 힙을 사용하여 정렬한다. 여기서 '힙'은 '부못값이 자식값보다 항상 크다'라는 조건을 만족하는 완전이진트리이다. 모든 부모와 자식의 관계는 항상 부모값>= 자식값 힙정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘이다. - 힙에서 가장 큰 값인 루트를 꺼냅니다 - 루트 이외의 부분을 힙으로 만듭니다 이 작업을 반복한다. import java.util.Arrays; public class HeapSort { static void swap(int[] a, int idx1, int idx2){ int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t; } public static void main(String[] a.. 병합정렬 병합 정렬 알고리즘 배열의 요솟수가 2개 이상인 경우 배열의 앞부분을 병합 정렬로 정렬합니다 배열의 뒷부분을 병합정렬로 정렬합니다 배열의 앞부분과 뒷부분을 병합합니다 배열 병합의 시간복잡도는 O(n), 병합정렬까지 생각하면 전체 시간복잡도는 O(n log n). + 안정적인 정렬방법이다. 실습 public class MergeSort { static int[] buff; // 작업용 배열 // a[left] ~ a[right] 를 재귀적으로 병합정렬 static void __mergeSort(int[] a, int left, int right){ if(left < right){ int i; int center = (left + right) / 2; int p = 0; int j = 0; int k = l.. 퀵정렬 퀵정렬은 요솟수가 많은 배열을 정렬하는 경우 효과적이다. O(n log n) ~ O(n²)의 시간복잡도를 가진다. 재귀적인 퀵 정렬 구현 left < pr, pl < right 는 모두 그룹의 요솟수가 1개일때는 성립하지 않는 조건임. 이 조건은 요솟수가 2개 이상인 그룹을 나눌 때 필요하다. import java.util.Scanner; public class QuickSort { static void swap(int[] a, int idx1, int idx2){ int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t; } // 나눌 구간의 맨 앞 요소(left), 맨 뒤 요소(right) static void quickSort(int[] a ,int left, int r.. 이전 1 2 3 다음