자료구조&알고리즘/Basic6 부분 집합 (Sub Set) 부분 집합 (Sub Set) $2^n$ 의 경우의 수를 갖는다. 소스 코드 import java.io.*; import java.util.ArrayList; import java.util.List; public class SubSet { public static void subSet(List list, int n, int depth) { if (depth == n) { System.out.println(list); return; } list.add(depth); subSet(list, n, depth + 1); list.remove(list.size() - 1); subSet(list, n, depth + 1); } public static void main(String[] args) throws IOE.. 2022. 2. 21. 조합 (Combination) 조합 (Combination) 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 서로 다른 n개 중 r개를 택하는 조합의 경우의 수는 아래와 같다. 소스코드 import java.util.Arrays; public class Combination { public static void combination(int[] arr, int n, int r, int depth, int idx) { if (depth == r) { System.out.println(Arrays.toString(arr)); return; } for (int i = idx; i < n; i++) { arr[depth] = i; combination(arr, n, r, depth + 1, i + 1); } } public static.. 2022. 2. 20. 순열 (Permutation) 순열 (Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열의 경우의 수는 아래와 같다. nPr = n * (n - 1) * ... * (n - r + 1) n이 12 이상일 경우부터 시간 복잡도가 급격히 상승한다. 소스코드 import java.util.Arrays; public class Permutation { public static void permutation(int[] arr, boolean[] selected, int depth) { if (depth == selected.length) { System.out.println(Arrays.toString(arr)); return; } for (int i = 0; i < sele.. 2022. 2. 20. 재귀 알고리즘 재귀란? : 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다. 예시) 팩토리얼 구하기 package chap05; import java.util.Scanner; // 팩토리얼을 재귀적으로 구현 class Factorial { // 양의 정수 n의 팩토리얼을 반환합니다. static int factorial(int n) { if (n > 0) return n * factorial(n - 1); else return 1; } public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); System.out.print("정수를 입력하세요.："); int x = stdIn.nextInt().. 2021. 5. 16. 꼭 필요한 자료구조 기초 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 오버플로우(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 언더플로우(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로우가 발생한다. 스택 선입후출(First In Last Out)구조 또는 후입선출(Last In First Out)구조 e.g. 쌓아올린 박스를 연상 큐 선입선출(First In First Out) 구조 e.g. 놀이공원 줄을.. 2021. 5. 2. 시간 복잡도와 공간 복잡도 출처 : 이것이 코딩 테스트다 도서 Chapter 01 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 시간 복잡도 빅오 표기법을 사용 * 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법 빅오 표기법 명칭 O($1$) 상수 시간(Constant time) O($logN$) 로그 시간(Log time) O($N$) 선형 시간 O($NlongN$) 로그 선형 시간 O($N^2$) 이차 시간 O($N^3$) 삼차 시간 O($2^n$) 지수 시간 N이 1,000일 때의 연산 횟수 O($N$) 1,000 O($NlongN$) 10,000 O($N^2$) 1,000,000 O($N^3$) 1,000,000,000 시간 제한이 1초인 문제에 대한 예.. 2020. 10. 31. 이전 1 다음 반응형
