공부방

재귀 함수를 이용한 피보나치 수열 package day0410_동적계획법; import java.util.Scanner; public class 피보나치 { static long callFibo1; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(fibo1(N)); System.out.println(callFibo1); }//main //재귀 함수를 이용한 피보나치 public static long fibo1(int n) { callFibo1++; if(n실행 속도 저하 또는 오버플로어가 발생할 수 있음. 동적 계획 알고리즘 그리디 알고리즘과..

순서가 있는 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘 사이클이 없는 방향 그래프(DAG)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것 진입 차수 : 특정 노드로 들어오는 간선의 개수 진출 차수 : 특정 노드에서 나가는 간선의 개수 진입 차수가 있다는 것은 선행 조건이 있다는 뜻이므로 진입 차수가 더 중요! 위상 정렬 방법(Queue 사용) 진입 차수가 0인 모든 노드들 Queue에 삽입 Queue가 공백상태가 될 때까지 반복 수행 Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. (연결된 노드의 진입 차수를 감소시킨다.) 새롭게 진입 차수가 0이 된 노드를 Queue에 삽입한다. Queue에서 꺼내지는 순서(Queue 들어온 순..

프림 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 1. ,2. 과정을 반복 반복문 package day0330_프림_다익스트라; import java.util.Arrays; import java.util.Scanner; public class 프림_반복문 { static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { //Scanner sc = new Scanner(System.in); Scanner sc = new Scanner(input..

서로소 집합 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다. 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호배타 집합을 표현하는 방법 연결 리스트 트리 상호 배타 집합 연산 Make-Set(x) : x라고 하는 원소를 대표자로 만든다. Find-Set(x) : x의 대표자 불러온다. Union(x,y) : 하나의 그룹으로 만든다. 상호 배타 집합 표현-트리 하나의 집합(a disjoint set)을 하나의 트리로 표현한다. 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 연산의 효율을 높이는 방법 Rank를 이용한 Union 각 노드는 자신을 루트로 하는 subtree의 ..

트리(그래프, 2차원 배열) 순회(탐색)은 모든 자료(노드, 정점)을 빠짐 없이 탐색하는 것을 의미한다. 깊이 우선 탐색(Depth First Search, DFS) 루트 노트(시작 정점, 출발 위치)에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드(정점)으로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문하는 순회방법 가장 마지막에 만났던 갈림길의 노드(정점)로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 자료구조인 스택 사용 재귀 함수는 시스템 스택을 이용하므로 이를 이용하여 간단하게 구현할 수도 있음. 문제 유형 경로 탐색 : 두 정점 사이의 경로..

그래프 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계 표현 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 선형자료구조(1:1)나 트리자료구조(1:N)로 표현하기 어려운 M:N관계를 표현 가중치 그래프(Weighted Graph) : 간선에 값이 있는 그래프 순환 그래프(Cycle graph): 사이클이 있는 그래프 완전 그래프 정점에 대해 가능한 모든 간선들을 가진 그래프 간선 의 수 : N(N-1)/2개 부분 그래프 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 인접 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다. 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다. 경로 간선들을 순서대로 나열한 것 간선 : (0..

부분 집합 하나하나 다 아무것도 안 고를 때부터 다 골랐을 때까지 골라줄 때 ex) 1,2,3,4,5 (),1,2,3,4,5,(1,2),(1,3),...,(1,2,3),.....,(1,2,3,4,5) package 구현; public class 부분집합 { static int N; static String ans; static String[] 재료; static boolean[] sel; public static void main(String[] args) { 재료=new String[] {"삼","단","우"}; N=재료.length; //System.out.println(N); sel=new boolean[N]; powerset(0); } private static void powerset(int n..

백트래킹 기법 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 감. 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다. 가지치기(pruning) : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다. 백트래킹을 이용한 알고리즘 상태 공간 트리의 깊이 우선 검색을 실시한다. 각 노드가 유망한지를 점검한다. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다. 단순 순열 package day0323_백트래킹; //반복문 public class 순열_1 { stati..

이진검색 재귀 자료의 중앙에 있는 원소를 고른다. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다. 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 종료한다. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다. 찾고자 하는 값을 찾을 때까지 1.~4.의 과정을 반복한다. package day0322_분할정복; public class 분할정복04_이진검색_재귀 { static int[] arr; static int key; public static void main(String[] args) { // 정렬된 상태라고 가정 arr = new int[] { 2, 4, 6, 8, 9, 17, 28 }; key ..

부분집합의 수 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다. 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다 반복문을 이용한 부분집합 구하기 package day0321_부분집합_조합; import java.util.Arrays; public class 부분집합_1 { String[] 재료 = {"참치", "우엉", "삼겹살"}; public static void main(String[] args) { //반복문을 이용해서 부분집합을 구해보자. int N = 3; int[] sel = new int[N]; for(int i = 0 ; i