불로구

스택 - 데이터를 일시적으로 저장히기 위해 사용하는 자료구조 - 데이터의 I/O (입출력)은 LIFO( Last In First Out )구조 - 삽입(push) / 빼기(pop) 스택만들기 package 스택큐.스택; class StackEx{ private int max; //스택 용량 private int ptr;//스택 포인터 private int[] st;//스택 //기본 생성자 public StackEx(int capacity) { ptr = 0; max = capacity; try { st = new int[max]; }catch(OutOfMemoryError e) { max = 0; } } //push(삽입) public void push(int x){ if(ptr >= max) { Ove..

복잡도 - 알고리즘의 성능을 객관적으로 평가하는 기준 복잡도 종류 1) 시간복잡도 : 실행에 필요한 시간이 얼마인지? 2) 공간복잡도 : 기억 영역과 파일 공간이 얼마나 필요한지? method{ int i = 0; while(i 변수 i에 0을 대입하는 것은 한번이후 없으므로 O(1) - return의 경우도 한번만 실행하므로 O(1) - while의 조건과 if문, i++의 경우 평균횟수 n/2 -> n에 비례하는 경우의 복잡도를 O(n)으로 표기 n이 커지면 O(n)에 필요한 계산 시간은 n에 비례하여 점점 길어진다. O(1)의 경우 계산 시간은 변하지 않는다. O(f(n)) 과 O(g(n))의 복잡도 계산 - O(f(n)) + O(g(n)) = 0(max(f(n) , g(n)) - 2개 이상의 복잡..

이진탐색 - 오름차순 or 내림차순으로 정렬되어있는 배열에서 검색하는 알고리즘 -> 7찾기 step 1) start center end 5 7 9 11 13 15 17 step 2) start center end 5 7 9 - 이진탐색을 시작(0), 중앙( (배열길이 - 1 / 2) ) , 끝( 배열길이 - 1)으로 나눈다. - 찾는 값이 중앙 값 보다 작다면 -> 시작(0), 끝( 중앙-1 ), 중앙 ( (배열길이 - 1 / 2) )가 되고 - 찾는 값이 중앙 값 보다 크다면 -> 시작(중앙+1) , 끝( 배열길이 -1 ), 중앙 (배열길이 -1/2)가 된다. 종료조건 - 1) 중앙값과 key가 일치 - 2) 검색 범위에서 찾지 못함 시간복잡도 - 반복마다 검색 범위가 반으로 줄어든다 - 평균 : lo..

선형 검색이란? - 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 앞에서부터 끝까지 돌면서 찾는 검색 배열 인덱스 0 1 2 3 4 배열 요소 2 7 5 1 9 배열의 0번째 인덱스부터 -> 4번째 인덱스 까지 검색을 하는 것이다. 선형 검색의 종료 조건 1) 검색에 실패하고 배열의 끝을 지난 경우 - n+1회 2) 검색에 성공했을 때 - n회 -> 평균은 n/2회 코드 public class 선형검색 { static int seqSearch(int[] a, int n, int key) { int i=0; while(true) { if(i==n) return -1; if(a[i] == key) return i; i++; } // - for문 구현 - // int result = -1; //for(..