2021.03.31
13일차
입사 24일차.
어느 대기업에 최종면접을 볼 기회가 있었다. 당시 면접질문의 내용을 모두 적을수는 없지만, 이진탐색에 관련된 내용이 있었다.
긴장 + 화상면접으로 진행하다보니 면접질문을 제대로 이해하지 못하고 이진트리에서의 탐색으로 이해하고 답변했었는데 괜찮은 대답으로 면접관님들이 받아주신 기억이 있어 정리해보려고 한다.
0. 이진탐색의 특징
① 정렬되어 있는 데이터에서만 사용가능하다.
② 탐색속도가 빠르다.
1. 이진탐색이 어렵다면 이진트리에 대입해보면 쉽다
① 이진탐색은 임의의 가운데값 ( Ex. 8 )을 지정한 후, 찾는 값이 큰지, 작은지를 판단하며 진행하는 탐색방법이다.
| 15 | 13 | 11 | 8 | 5 | 3 | 2 |
② 이 리스트를 이진트리로 변환해본다.
③ 11이라는 값을 찾는다면 2번의 탐색을 거치게 된다.
위의 구조는 Level = 2, 자식노드의 수 = 2인 이진트리다.
이진탐색은 임의의 가운데값을 지정해서 찾는값의 범위를 반으로 줄이는 과정이 진행되기 때문에
탐색의 횟수는 height( level - 1 ) 가 된다.
④ 따라서, 탐색시간은 노드 전체 갯수( N ) * ( 1/2 )^height 이 된다.
2. 이진탐색으로 찾은 데이터를 배열로 차례대로 저장할 수 있을까?
① 동적배열로 저장한 뒤에 Java의 Arrays.sort()같은 메소드를 이용해서 정렬하는 법을 제외한다.
② 동적배열의 경우, 아래의 코드처럼 index를 건너뛰면서 저장하게 되면 IndexOutofBoundsException을 발생시킨다.
| public static void main(String[] args) { List<String> list = new ArrayList<String>(); list.add(0, "0"); // list.add(1, "1"); list.add(2, "2"); System.out.println( list ); } |
| [console] Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 1 at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:665) at java.util.ArrayList.add(ArrayList.java:477) at Main.main(Main.java:18) |
③ 고정배열은 배열선언과 동시에 크기도 선언하기 때문에 고정배열은 크기를 늘릴 수 없다.
( 이진탐색을 수행하는 리스트의 크기를 모른다는 것이 전제 )
댓글