키리Kirri's IT노트

: 데이터가 키 값으로 이미 정렬(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. 생..

・정숫값을 임의의 기수로 변환 : 10진수 정수를 n진수 정수로 변환하려면 정수를 n으로 나눈 나머지를 구하는 동시에, 그 몫에 대해 나눗셈을 반복한다. 이 과정을 몫이 0이 될 때까지 반복, 나머지를 거꾸로 늘어 놓은 숫자가 기수로 변환한 수가 된다. 1 2 3 4 5 6 7 8 9 10 11 12 static int cardConvR(int x, int r, char[] d) { int digits = 0; String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; do { d[digits++] = dchar.charAt(x % r); x /= r; } while (x != 0); return digits; } Colored by Color Scripter 1 ..