[알고리즘][코딩 인터뷰 완전 분석 정리] 01 배열과 문자열

해시 테이블 

• 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킴.
• 해시테이블 구현방법 
  1. 연결리스트(linked list)와 해시코드(hash code function)함수 같이 사용.
     • 키(문자열 혹은 다른 어떤 자료형도 가능)와 값을 해시테이블에 넣을때 과정
       • 처음엔 키의 해시코드를 계산. 키의 자료형은 보통 int 혹은 long. 키의 갯수는 무한한데 반해 int의 개수는 유한하기 대문에 서로 다른두개의 키가 같은 해시 코드를 가리킬수 있다.
       • 그다음엔 hash(key) % array_length와 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다.
       •  배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장. 충돌에 대비해서 반드시 연결리스트를 이용해야한다. 
  2. 균형 이진 트리 탐색(balanced binary search tree)를 사용
     • 이경우 탐색 시간은 O(log N)
     • 장점 : 크기가 큰 배열을 미리 할당하지 않아도 되기때문에 잠재적으로 적은 공간을 사용함. 키의 집합을 특정 순서로 차례대로 접근 가능. 

ArrayList와 가변 크기 배열

• 특정 언어에선 배열(종종 리스트..)의 크기를 자동으로 조절. 즉, 데이터를 덧붙일 때마다 배열혹은 리스트의 크기가 증가함.
• 하지만 자바 같은 언어에서는 크기가 고정되어 있음. 이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야 함.
• 동적 가변크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 대는 보통 ArrayList를 사용함. 
• ArrayList는 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근시간을 유지.
• 통상적으로 배열이 가득 차는 순간, 배열의 크기를 두 배를 늘림. 크기를 두 배 늘리는 시간은 O(n)이지만, 자주 발생하지 않아 여전히 O(1) 접근시간을 유지.

 

StringBuilder

• 문자열의 리스트
• 문자열의 갯수가 x개일대, 문자열을 하나로 이어 붙일때 수행 시간은 O(xn^2)
• why? 문자열을 이어붙일 대마다 두 개의 문자열을 읽어 들인 뒤 문자를 하나하나 새로운 문자열에 복사해야하기 때문
• 예를들어 처음에는 x개, 두 번째는 2x개, 세번째는 3x개.... n 번째는 nx개..! 모두 더하면(x+ 2x+ 3x+ .... + nx) => xn^2