개발 공부 - 선형 검색

* 공부용의 자유로운 글씨😀

『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.

선형 검색 : 임의의 배열에서 원하는 데이터를 찾는 것

배열 a 의 요소값 합계를 구해 변수 sum 에 저장하는 알고리즘을 슈도코드로 작성해 보면 아래와 같다.

이걸 자바로 짜면 이렇게 된다.

사실 의사코드 대로 똑같이 안 짠다면 아래와 같다.

이렇게 배열 a 의 값이 변화하지 않고 변수 sum 과 변수 i 만 변하는 것을 확인 할 수 있다.

이 Java 코드에 추적을 위한 코드를 추가할 수 있는데, 디버깅 외에 sysout을 사용해서 찍어보라고 한다.

선형 검색은 '임의의' 배열에서 원하는 데이터를 찾는 알고리즘인데, 정렬되지 않은 배열을 뜻한다. (만약 정렬이 됬으면 이진 검색을 사용하는 것이 효율적이니까)

교재에서 선형 검색의 알고리즘을 의사 코드로 작성하고 있다.

이걸 자바로 짜면 아래와 같다.

이렇게 선형 검색을 효율화하는 기술로, 보초법이라는 것을 쓰는데, 

이것은 보초병의 개념을 이용하는 것으로, 대상 데이터를 뜻한다.

배열의 끝에 보초법의 값에 해당하는 데이터를 추가한 후, 검색 횟수를 줄여서 값을 빠르게 찾을 수 있는데, 배열에서 만약 66이라는 값을 찾을 경우에는 보초법 값 자체를 66으로 하면 된다.

그러면 만약에 한 바퀴 돌아서 66이 없을 경우에도 반드시 66이 있기 때문에, 배열 끝 부분을 확인 할 필요가 없다.  (66이 있으면 있는거고, 없으면 끝에 넣은 66이 있으니까)

여기서 추적 코드를 넣어보면, 아래와 같다.

반복 횟수를 세는 변수는 루프 카운터이다.

의사 코드로 ■ i : 0, i<10, 1 이라는 반복을 마지막까지 수행하면, 변수 i 값은 9가 되지 않는다.

변수에 초기값을 대입하는 것을 초기화라고 부른다.

선형 검색에서도 정렬된 배열을 탐색할 수 있다.

의사코드 i<10 and pos = -1 이라는 조건으로 반복 실행을 할 경우, pos가 -1이 아닌 값으로 변경되면 반복이 종료된다.

단원 종료 시 배열의 최댓값과 최솟값을 구하는 문제가 있다.

이 문제의 포인트는 i를 1부터 시작하는 것이다.

이유는 최대값, 최소값의 값을 i[0] 부터 시작했기 때문에, 반복문에서 반복할 필요가 없다.

* 배열의 첫 번째 요소만 별도 취급하는 알고리즘의 일환이다.