알고리즘/기초수학3 점화식과 재귀함수, 지수와 로그, 복잡도 □ 점화식 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식 ex) 피보나치 수열 // 일반적인 방법 int n = 4; // 4번째 수를 구한다고 가정 int result = 1; for(int i = 0; i< n; i++) { if(i == 0) { result = 1; } else { result *= 3; } } //1, 1, 2, 3, 5, 8, 13, ...의 n번째 수 int n = 6; int result = 0; int a1 = 1; int a2 = 1; if(n < 3) { result = 1; } else { for(int i = 2; i < n; i++) { result = a1 + a2; a1 = a2; a2 = result; } } □ 재귀함수 어떤 함수가 자신을 다시.. 2022. 8. 21. 순열, 조합 □ 팩토리얼 ! 1에서 n까지 모든 자연수의 곱 (n!) □ 순열 : 순서를 정해서 나열 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 X) ex) 5명을 3줄로 세우는 방법, 서로 다른 4명중 반장과 부반장을 뽑는 방법 nPr = n! / (n-r)! // 5(n)명을 3(r)줄로 세우는 경우의 수 for(int i = n; i>= n - r + 1 ; i-- { result *= i; } ■ 중복 순열 서로 다른 n개 중게 r개를 선택하는 경우의 수 (순서 O, 중복 O) ex) 서로 다른 4개의 수 중 2개를 뽑는 방법(중복 허용), 후보2명과 유권자가 3명일 때 기명 투표 방법 nπr = n^r // 서로 다른 4(n)개의 수 중 2(r)개를 뽑는 경우의 수(중복 O) for(.. 2022. 8. 19. 집합, 경우의 수 □ 집합 - HashSet 특정 조건에 맞는 원소들의 모임 HashSet a = new HashSet(Arrays.asList(1,2,3,4,5)); HashSet b = new HashSet(Arrays.asList(2,4,6,8,10)); // 일반적으로 구현 ArrayList list = new ArrayList(); // 밑에서 구현 // 중복X 원소 추가 public void add(int x) { for(int item : this.list) { if(item == x) { return; } } this.list.add(x); } ■ 교집합 : 두 집합이 공통으로 포함하는 원소로 이루어진 집합 a.retainAll(b); public MySet retainAll(MySet m) { MySet .. 2022. 8. 19. 이전 1 다음