기초적인 자료구조

집합

-특정 조건에 맞는 원소들의 모임

 

집합 표현 방법

 

-원소나열법

A={1,2,3,4,5} B={2,4,8,6,10}

 

-조건 제시법

A={A | A는 정수, 1<=A<=5}

B={2B | B는 정수, 1<= B <= 5}

 

-벤 다이어그램

 

경우의 수

 

경우의 수

-어떤 사건에서 일어날 수있는 경우의 가짓수

 

합의 법칙

-사건 A와 사건B의 합의 법칙: n(A B)

 

곱의 법칙

-사건 A와 사건 B가 동시에 일어날 경우의 수

 

기초수학

순열

 

팩토리얼

1에서 n까지 모든 자연수의 곱

 

순열

순서를 정해서 나열

서로 다른 n개 중에 r개를 선택하는 경우의 

 

중복 순열

-서로 다른 n개 중에 r개를 선택하는 경우의 수

 

원 순열

-원 모양의 테이블에 n개의 원소를 나열하는 경우의 수

 

점화식과 재귀함수

 

점화식

-어떤 수열의 일반항을 그 이전의 항들을 이요하여 정의한 식

-예시>피보나치 수열

1,1,2,3,5,8,13.... 

 

재귀함수

-어떤 함수가 자신을 다시 호출하여 작업을수행하는 방식

 

지수와 로그

 

제곱

-같은 수를 두 번 곱함

-거듭 제곱 : 같은 수를 거듭하여 곱합

 

제곱근

-a를 제곱하여 b가 될 때 a를 b의 제곱근이라고 함

 

로그

loga b

-a가 b가 되기 위해 제곱해야 하는 수

 

알고리즘 복잡도

 

복잡도

-알고리즘 성능을 나타내는 척도

-시간 복잡도 : 알고리즘의필요 연산 횟수

-공간 복잡도 : 알고리즘의 필요 메모리

-시간 복잡도와 공간 복잡도는 Trade-off 관계

 

시간 복잡도

-어떤 문제를 해결하기 위한 알고리즘의필요 연산 횟수

-빅오(Big-O) 표기법을 통해 나타냄

빅오 표기법	설명
O(1) 입력값이몇 이든 연산 1번만 계산	상수 시간
O(log N) 입력값 N에 대해  N번 만큼	로그 시간
O(N) 입력값이 N개이면 연산도 N번 만	선형 시간
O(N log N) N X log N	로그 선형 시간
O(N²)	이차 시간
O(2ⁿ)	지수 시간

 

공간 복잡도

-어떤 문제를해결하기 위한 알고리즘의필요 메모리 사용량

-빅오 표기법을 통해 나타냄 : 일반적으로 메모리 사용량 기준은 MB단위

 

int[] a= new int[1000];  //4KB

int[][] a = new int[1000][1000]  //4KB