Keep going

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 일반적인 탐색 알고리즘 문제다. 배열에 찾는 값이 있으면 1을 출력하고 없으면 0을 반환하는 이진 탐색하는 메소드를 만들었다. import java.util.*; public class SearchNumber { static int binarySearch(int[] a, int key) { int cl = 0; int cr = a.length - 1; while ..

java.util.Arrays 클래스는 배열 조작에 도움을 주는 메소드들로 채워져 있다. 이 클래스에 정의된 메소드들을 사용하면 배열의 복사, 비교, 정렬 및 탐색과 관련된 코드를 비교적 쉽게 작성할 수 있다. 배열 복사에 사용되는 Arrays 클래스의 메소드다. 모든 기본 자료형 배열에는 이 메소드가 오버 라이딩 되어있다. public static int[] copy of( int[] original, int new Length) → original에 전달된 배열을 첫 번째 요소부터 newLength의 길이만큼 복사 public static int[] copyofRange(int[] original , int from, int to) → origianl에 전달된 배열을 인덱스 from부터 to 이전 요..

이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 키를 이진 검색으로 검사하는 과정을 일반적인 방법으로 표현해 보겠습니다. 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정하겠습니다. 검색을 시작할 때 pl은 0, pr은 n-1, pc는 (n-1)/2로 초기화 합니다. 여기서 주목할 점은 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 (거의) 반으로 좁혀 진다는 것 입니다. 오름차순으로 정렬된 데..

직선 모양으로 늘어선 데이터 집합(배열, 링크드리스트) 에서 원하는 키 값을 갖는 요소를 만날 때 까지 앞부터 순서대로 요소를 검색하는 것을 선형 검색 또는 순차 검색 알고리즘이라고 한다. 구체적인 과정을 아래의 데이터 나열을 예로 들어 살펴보겠습니다. 이 배열에서 값 2의 요소를 선형 검색해보겠습니다. 6 4 3 2 1 3 6 4 3 2 1 3 6 4 3 2 1 3 6 4 3 2 1 3 (1) 첫번째 요소 6을 선택합니다. 원하는 값이 없습니다. (2) 두번째 요소 4를 선택합니다. 원하는 값이 없습니다. (3) 세번째 요소 3을 선택합니다. 원하는 값이 없습니다. (4) 네번째 요소 2을 선택합니다. 원하는 값입니다. 검색 성공!! → 이경우는 검색에 성공한 경우입니다. 그런데 키 값과 같은 값을 가..