유블로그

서로소 집합 중복 포함된 원소가 없는 집합. 집합에 속한 하나의 특정 멤버인 '대표자'로 집합 구분 연결리스트 or 트리로 표현 서로소 집합 연산 Make-Set(x) : 유일한 멤버 x 포함하는 새로운 집합 생성 Find-Set(x) : x 포함하는 집합 찾기 Union(x, y) : x와 y 를 포함하는 두 집합을 통합하는 연산. x와 y 중 x를 대표자로 설정한다면 x는 y의 부모가 됨. 하나의 집합 = 하나의 트리 자식 노드가 부모 노드 가리킴. 루트 노드가 대표자 대표자 노드는 자기자신을 가리킴. Rank 사용 : 각 노드는 자신을 루트로 하는 subtree의 높이를 Rank로 저장 Path Compression : Find-Set 할 때 만나는 모든 노드들이 직..

그래프는 아이템들과 이들 사이의 연결 관계 표현 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 |V| : 정점의 개수, |E| : 그래프에 포함된 간선의 개수 |V|개의 정점을 가지는 그래프는 최대 |V| ( |V| - 1 ) / 2 간선 가능 -> 무향 그래프에 해당 무향 그래프 (양방향) 유향 그래프 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 모든 노드가 연결되어 있는 그래프 부분 그래프 트리는 싸이클이 없는 무향 연결 그래프이다. 두 노드 사이에는 유일한 경로 존재 각 노드는 최대 하나의 부모 노드가 존재할 수 있다. 각 노드는 자식 노트가 없거나 하나 이상이 존재할 수 있다. 인접(Adjacency) 두 개의 ..

- 선형구조 : 자료 간의 관계가 1:1 관계, 스택과 큐가 선형구조에 해당됨. 비선형구조의 예는 트리. - 스택 후입선출(LIFO, Last-In-First-Out) : 마지막에 삽입한 자료를 가장 먼저 꺼냄 연산 : push(삽입), pop(삭제), isEmpty(비어있는지), peek(top 원소값 보기) 맨 위 원소 top이라고 함 Java 는 java.util.Stack 사용 - 후위 표기법 : 연산자가 뒤에 있는 수식 표기법 ex) (6+((5*(2-8))/2)) -> 6528-*2/+ - 큐 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만, 큐의 앞에서는 삭제만 선입선출(FIFO, First-In-First-Out) : 먼저 삽입된 원소가 먼저 삭제됨 저장된 원..

import java.util.Arrays; import java.util.Scanner; public class CombinationTest { private static int N = 3, R = 2;// N: 총 숫자 개수, R: 뽑을 숫자 개수 private static int[] numbers;// 조합 저장 배열 private static int[] input;// 입력된 숫자 배열 public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); numbers = new int[R];// 0으로 초기화 input = new int[N]; for(int i ..

import java.util.Arrays; import java.util.Scanner; // 입력받은 N개의 숫자 중 R개를 선택하는 순열 public class PermutationInputTest { private static int N = 3, R = 2;// N: 총 숫자 개수, R: 뽑을 숫자 개수 private static int[] numbers;// 순열 저장 배열 private static int[] input;// 입력된 숫자 배열 private static boolean[] isSelected; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.ne..

완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-Force 혹은 generate-and-test 기법이라고도 불린다. 모든 경우의 수를 테스트한 후 최종 해법 도출한다. 경우의 수가 상대적으로 작을 떄 유용하다. 상대적으로 빠른 시간안에 알고리즘 설계를 할 수 있다. 전형적으로 순열, 조합, 부분집합 과 같은 조합적 문제들과 연관된다.

private static int Fibonnaci(int n) { if(n>=2) { if(arr[n] != -1) return arr[n]; } return Fibonnaci(n-1) + Fibonnaci(n-2); } public static void main(String[] args) { arr[0] = 0; arr[1] = 1; System.out.println(Fibonnaci(10)); }

private static int factorial(int n) { if(n