이진 탐색은 일반적인 탐색 방법보다 빠르게 검색이 가능합니다. 다만 정렬이 되있어야한다는 단점을 가지고 있다. 배열안에 1부터 100까지의 숫자가 들어있다고 하자. 그리고 우리는 37이라는 숫자를 찾아야한다. 숫자 37을 찾으려면 3가지 방법이 있다. 하나는 37을 호출하는 방법 : 이 방법은 배열에 값을 넣고 그 값을 리턴 시켜주면 된다. 하지만 등차수열(일정하게 증가하는 수열) 그것도 1씩 증가하는 배열일때만 가능하다. 지금 같은 경우에는 이 방법이 가장 빠른 방법일지도 모르겠다. 시간 복잡도는 O(1) 즉, 엄청빠른 시간안에 문제를 해결할 수 있다. 두 번째 방법은 1부터 차례대로 찾는 방법이다. 이 방법같은 경우 O(n)이라는 시간이 걸린다. 여기서 n은 100까지를 말하는데, 검색해야할 숫자가 ..
[코딩 인터뷰 완전 분석] ▶ 해시 테이블 - 효율적인 탐색을 위한 자료구조로 키를 값에 대응 시킨다. 해시 테이블을 구현하기 위해서는 연결리스트와 해시코드 함수만 있으면 된다. - 키와 값을 해시테이블에 넣을때 다음의 과정을 거친다. 1. 키의 해시코드를 계산한다. ※키의 개수는 무한대인데, int나 long의 개수는 유한하기때문에 서로 다른 두 개의 키가 같은 해시코드를 가리킬 수 있다는 사실을 명심해야한다. 2. hash(key) % array_length와 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다. -> 같은 인덱스를 가르킬수 있다. 3. 배열의 각 인덱스는 키와 같은 같은 값으로 이뤄진 연결리스트가 존재한다. - 키와 값을 해당 인덱스에 저장한다. - 충돌에 대비하여 연결리스틀 이..
연결리스트 : - 차례대로 연결된 노드를 표현해 주는 자료구조 - 단방향 연결리스트에서 각 노드는 다음 노드를 가르킨다. - 양방향 연결 리스트에서 각 노드는 다음노드와 이전 노드를 가르킨다. - 배열과 달리 연결리스트는 특정 인덱스를 상수시간에 접근 할 수 없다. => k번째 원소를 찾고 싶다면, k번 루프를 돌아야 한다. 1 2 3 4 연결리스트의 장점 : 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수시간에 할 수 있다. 단 방향 연결리스트 코딩 public class Node { Node next = null; int data; public Node(int d) { this.data = d; } } 코드 : Node를 만드는 로직이 들어가있다. 이때 주의 할 점은 자기 자신을 호출..