[코딩 인터뷰]자료구조 - 배열과 문자열

[ 해시 테이블 ]

: 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응

 

👀 구현 방식

1. 연결리스트와 해시코드함수 : 탐색 시간 O(1)

✔️ 키와 값 삽입법

1. 키의 해시 코드 계산
    키의 자료형은 보통 int 혹은 long인데, 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있습니다.
2. 해시 코드를 이용하여 배열의 인덱스 계산
    서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있습니다.
3. 키와 값을 해당 인덱스에 저장
    배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재합니다. 충돌에 대비해서 반드시 연결리스트를 이용해야합니다.

⭐ 충돌 : 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말합니다.

 

✔️ 키에 상응하는 값 찾기

1. 주어진 키로부터 해시 코드 계산
2. 해시 코드를 이용하여 인덱스 계산
3. 키에 상응하는 값을 연결리스트에서 탐색
4. 1~3번 반복

---

 

2. 균형 이진 탐색 트리 : 탐색 시간 O(logN)

✔️ 장점

• 잠재적으로 적은 공간을 사용
• 키의 집합을 특정 순서로 차례대로 접근

---

 

 

[ ArrayList와 가변 크기 배열 ]

 특정 언어에서는 배열의 크기를 자동으로 조절할 수 있지만 Java 같은 언어에서는 배열의 길이가 고정되어 있습니다.

→ 이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야합니다.

⭐ Java에서 배열 예시

int[] num = new int[3];
for(int i = 0; i < num.length; i++){
    num[i] = i;
}

⭐ Python에서는 배열의 크기를 지정할 필요가 없습니다.

num = []
for i in range(3):
    num.append(i)

 

👀 ArrayList

: Java에서 동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조입니다. 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지합니다. 통상적으로 배열이 가득 차는 순간, 배열의 크기를 두 배로 늘립니다. 크기를 두 배 늘리는 시간은 O(n)이지만, 자주 발생하는 일이 아니라서 상환 입력 시간으로 계산했을 때 여전히 O(1)이 됩니다.

⇒ 상환 입력 시간은 왜 O(1)이 되는가요?

 N개의 원소를 삽입하기 위해서 복사해야 하는 원소의 총 개수는 [N/2+N/4+N/8+...+2+1]로 N보다 작습니다.

 N개의 원소를 삽입할 때 소요되는 작업은 O(N)이 됩니다. 배열의 상황에 따라 최악의 경우에 O(N)이 소요되는 삽입 연산도 존재하지만 평균적으로 각 삽입은 O(1)이 소요됩니다.

⭐ ArrayList 예시

import java.util.ArrayList;
ArrayList<Integer> num = new ArrayList<Integer>();
num.add(1);        # ArrayList 끝에 값 추가
num.add(2);        # ArrayList 끝에 값 추가
num.add(0, 100);   # 0번 인덱스에 값 추가. 나머지 값들 1칸씩 밀림
num.set(0, 0);     # 0번 인덱스 값 변경
num.remove(2);     # 값이 2 삭제
num.clear();       # 전체 삭제

⭐ Java에서 String[] 형식인 두 문자열 ArrayList로 병합하는 함수

import java.util.ArrayList;
ArrayList merge(String[] words1, String[] wrods1){
    ArrayList sentence = new ArrayList();
    for (String w : words1) sentence.add(w);
    for (String w : words2) sentence.add(w);
    return sentence;
}

 

 

[ StringBuilder ]

 Java에서는 문자열의 리스트가 주어졌을 때 이 문자열들을 하나로 이어 붙일 때 다음과 같습니다. 아래와 같이 코드를 사용할 때 총 수행시간은 O(n^2)이 됩니다.

String joinWords(String[] words){
    String sentence = "";
    for (String w : words){
        sentence = sentence + w;
    }
    return sentence;
}

 

👀 StringBuilder

:  String은 불변 객체로 두 개의 객체를 더하는 행위는 메모리 할당과 해제를 발생시키며 더하는 연산이 많아진다면 성능적으로 좋지 않습니다. String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르며 상대적으로 부하가 적습니다.

import java.lang.StringBuilder;
String joinWords(String[] words){
    StringBuilder sentence = new StringBuilder();
    for (String w : words){
        sentence.append(w);
    }
    return sentence.toString();
}

 

👀 해시테이블에서 충돌을 해결하는 방법

• 연결리스트를 이용한 체이닝
   해시테이블의 각 원소가 연결리스트로 대응된 방법입니다. 해시테이블에 n개의 원소가 있을 때 최악의 경우에 O(n)시간이 걸립니다.
• 이진 탐색 트리를 이용한 체이닝
   충돌을 연결리스트에 저장하는 대신 이진 탐색 트리에 저장하는 방법입니다. 최악의 경우에 수행 시간이 O(log n)이 걸립니다.
• 선형 탐사법을 이용한 개방 주소법
  충돌이 발생했을 때 비어있는 인덱스를 찾을때까지 다음 인덱스로 이동하는 방법입니다. 하지만 클러스터링 문제가 발생할 수 있습니다.

👀 Rabin-Karp 부분 문자열 탐색 알고리즘

 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘입니다.

예제

 

 

이전 글 참고하기!

https://onlab94.tistory.com/418

[MIT] 파이썬을 이용한 알고리즘의 이해 - 해싱 1