키리Kirri's IT노트

: 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. (LIFO, Last Input First Out) *푸시(push): 스택에 데이터를 넣는 작업 *팝(pop): 스택에서 데이터를 꺼내는 작업 ・스택 만들기 1. 생성자 IntStack : 스택 본체용 배열을 생성하는 등 준비 작업 수행 1 2 3 4 5 6 7 8 9 public IntStack(int capacity) { ptr = 0; max = capacity; try { stk = new int[max]; } catch(OutOfMemoryError e) { max = 0; } } 2. 푸시 메서드 push : 데이터를 푸시하는 메서드 1 2 3 4 5 public int push(int x) th..

: 데이터가 키 값으로 이미 정렬(sort)되어 있을 때, 선형 검색보다 빠르게 검색 가능 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 ・이진 검색 알고리즘의 종료 조건 ① a[pc]와 key가 일치하는 경우(검색 성공): 대략 ⌈log(n-1)⌉회 비교 ② 검색 범위가 더 이상 없는 경우(검색 실패): ⌈log(n+1)⌉회 비교 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 static int binSearch(int[] a, int n, int key) { int pl = 0; int pr = n - 1; do { int pc = (pl + pr) / 2; // 중앙 요소의 인덱스 if(a[pc] == key) return pc; else if(a[..

: 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘. 배열에서 순서대로 검색하는 유일한 방법이기도 하다. 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)라는 알고리즘이다. ・검색의 종료 조건 ① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(검색 실패) ② 검색할 값과 같은 요소를 발견한 경우(검색 성공) -while문 사용 1 2 3 4 5 6 7 8 9 10 11 12 static int seqSearch(int[] a, int n, int key) { int i = 0; while(true) { if(i == ..

: 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘 키: 검색을 수행할 때 주목하게 되는 특정 항목 1. 국적이 한국인 사람을 찾는다. 2. 나이가 21세 이상 27세 미만인 사람을 찾는다. 3. 찾으려는 이름과 가장 비슷한 이름의 사람을 찾는다. 1. 키 값과 일치하도록 지정(한국) 2. 키 값의 구간을 지정(21세 이상 27세 미만) 3. 키 값과 비슷하도록 지정(발음이 가장 비슷한 이름) 1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행 2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색 수행 3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색 수행 - 체인법: 같은 해시 값의 데이터를 선형 리스트로 연결 - 오픈 주소법: 데이..

: 임의의 데이터형을 자유로이 조합해 만들 수 있는 자료구조 class XYZ { int x; long y; double z; } 클래스 XYZ 3개의 데이터 요소(필드) XYZ a; a = new XYZ(); OR XYZ a = new XYZ(); 클래스형 변수 사용: 인스턴스 생성 필요 ・클래스 간략 개념 1. 클래스 본체에서는 다음과 같은 내용을 선언할 수 있다. - 멤버(필드/메서드/중첩(nested) 클래스/중첩 인터페이스) -클래스 초기화/인스턴스 초기화 -생성자 2. 필드/메서드/생성자를 선언할 때 public/protected/private을 지정할 수 있다. 3. 메서드/생성자는 다중으로 정의(오버로드)할 수 있다. 4. final로 선언한 필드는 한 번만 값을 대입할 수 있다. 5. 생..