Computing

MatrixChainAlgorithm

m(i,j)과 s(i,j) 어떤 정수 k (i≤kA_i A_(i+1)…A_j는 A_i…A_k와 A_(k+1)…A_j 의 곱으로 나누어 생각할 수 있으며 곱셈 연산 횟수는 다음과 같은 수식으로 나타낼 수 있다. m(i,j) = m(i,k) + m(k+1,j) + p_(i-1) p_k p_j m(i,j)과 s(i,j) 이때, 정수 k (i≤km(i,j)를 최소로 만드는 k 값을 s(i,j)에 저장한다. 즉, 곱셈 횟수 m은 n×n사이즈 테이블에 채워질 value 값이며 각각의 경우에 대한 k 값을 나타내는 s는 역추적을 할 때 사용하기 위한 테이블에 채워질 값이다. PRINT-OPTIMAL-PARENS (s, i, j)if i = j then Ai 를 출력 else “ ( ” 를 출력 PRINT-OPTIMA..

알고리즘

1.시간복잡도 1. n ≥ n0인 모든 n에 대하여 f(n) ≤ c · g(n)을 만족하는 양의 상수 c, n0이 존재하 면 f(n) = O(g(n))이다.(점근적 상한) 2. n > n0인 모든 n에 대하여 f(n) ≥ c · g(n)을 만족하는 양의 상수 c, n0이 존재 하면 f(n) = Ω(g(n))이다.(점근적 하한) 3. n > n0인 모든 n에 대하여 c1 · g(n) ≤ f(n) ≤ c2 · g(n) 을 만족하는 양의 상수 c1, c2, n0 이 존재하면, 즉 f(n) = Ω (g(n)) = O(g(n))이면 f(n) = Θ (g(n))이다. 2.알고리즘에서 중요순위 1. 정확성 2. 유효성 3. cpu 효율 time confidence 4. 메모리 사용량 space confidence3...

자료구조 정렬

시간복잡도1. n ≥ n0 인 모든 n 에 대하여 f(n) ≤ c · g(n)을 만족하는 양의 상수 c, n0 이 존재하 면 f(n) = O(g(n))이다.(점근적 상한) -최악의 경우이기 때문에 많이사용 2. n > n0 인 모든 n 에 대하여 f(n) ≥ c · g(n)을 만족하는 양의 상수 c, n0 이 존재 하면 f(n) = Ω(g(n))이다.(점근적 하한) -최선의경우 3. n > n0 인 모든 n 에 대하여 c1 · g(n) ≤ f(n) ≤ c2 · g(n) 을 만족하는 양의 상수 c1, c2, n0 이 존재하면, 즉 f(n) = Ω (g(n)) = O(g(n))이면 f(n) = Θ (g(n))이다. -평균적 경우 실행시간 O(n^2) 1.bubble sort-거품처럼 최댓값/최솟값을 밀어보낸..

자료구조 collection

*컬렉션:효율적인 접근을 위해 원소들을 관리하는 일반적 자료구조 리스트:리스트 원소는 배열처럼 0 1 2 등 번호를 부여함배열처럼 리스트는null참조를 가질 수 있다 *리스트:Array,LinkedArrayList list= new ArrayList( );리스트 부르기 .add .get등이 있음 1.ListArray/List 장단점비교검색우위-arraylist/verctor삽입삭제-LinkedlistList list=new LinkedList();vector v-v.capacity() ->size()-v.add() 2.Set/Map Set-Set은 순서가없는 집합 -중복허용을안함.-중복허용하지않는 데이터를 저장할때 유용함 .-메소드 add, size();ex)HashSet set=new HashSet()..