728x90 반응형 Algorithm7 [Algorithm] 이진 검색 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 이진 검색으로 검색하는 과정을 일반적인 방법으로 표현하겠습니다. 검색 범위 맨 앞 인덱스 pl, 맨 끝은 pr, 중앙 인덱스를 pc로 지정, 검색을 시작할 때 pl =0, pr = n - 1, pc = (n - 1)/2로 초기화합니다. 이진을 검색을 한번 할 때마다 값을 못찾으면 범위가 반으로 줄어 듭니다. 검색할 요소가 해당 단계에서 다음에 검색할 범위의 준간 지점으로 단숨에 이동합니다. public class BinSearch { //요소수가 n인 배열 a에서 key와 같은 여소를 이진 검색합니다. static int binSearch(int[] a, int n, int key){ int pl = 0; //검색 범위의 첫번째 인덱스 .. 2023. 12. 8. [Algorithm] 보초법 선형검색은 반복할 때마다 종료 조건 2가지 (검색 값 발견할 경우, 못 할 경우)를 모두 판단하는데 이 검사 비용을 반으로 줄이는 방법이 보초법입니다. 검색하기 전에 검색하고자 하는 키 값을 맨 끝 인덱스에 저장합니다. 이때 저장하는 값을 보초(sentinel)라고 합니다. 이렇게 하면 찾는 값이 배열에 존재하지 않아도 맨 끝 인덱스까지 검색하면 종료 조건이 성립합니다.(찾으려는 값과 같은 요소 발견, 단, 발견한 것은 보초) 또한 원하는 키 값을 찾지 못한 종료조건까지도 성립할 수 있습니다. 그렇기 때문에 반복문의 종료 판단 횟수를 2회에서 1회로 줄여줍니다. //선형검색 - 보초법 public class SeqSearchSen { //요소수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검.. 2023. 12. 8. [Algorithm] 선형 검색 요소가 잭선 모양으로 늘어선 배열에서의 검색은 워하는 키 값을 갖는 요소를 만날 때까지 맨앞부터순서대로 요소를 검색하는 방식을 선형 검색(Linear Search) 또는 순차 검색(Sequential Search)이라는 알고리즘 입니다. //선형검색 public class SeqSearchFor { static int seqSearch(int[] a,int n, int key){ for(int i = 0; i < n; i++){ if(a[i] == key) return i; //검색 성공(인덱스 반환) } return -1; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print.. 2023. 12. 8. [Algorithm] 기수 변환 //기수변환 메서드 //정수 x를 r진수로 변환하여 배열 d에 아랫자리부터 넣어두고 자릿수를 반환합니다. static int cardConvR(int x, int r, char[] d){ int digits = 0; // 변환 후의 자릿수 String dChar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; do{ d[digits++] = dChar.charAt(x % r); //r로 나눈 나머지를 저장 x /= r; }while (x != 0); return digits; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int no, cd, dno, retry; char[] cno.. 2023. 12. 6. 이전 1 2 다음 728x90 반응형 LIST
