[CodingInterview] 01 배열과 문자열(hashtable, vector)

안녕하세요 감자코딩입니다.

코딩인터뷰 완전분석에 대한 정리글을 포스팅을 꾸준히 진행해보려고합니다. 그러면 바로 진행하겠습니다

 

# 해시테이블

 

해시테이블은 효율 탐색을 위한 자료구조로서 키(key) 값(value)에 대응된다.

해시테이블을 구현하기 위해서는 연결리스트(Linked list)와 해시코드함수(hash code function)만 있으면 된다. 키(문자열 혹은 다른 어떤 자료형도 가능하다)와 값을 해시테이블에 넣을 때는 다음의 과정을 거친다.

 

# 해시테이블의 과정

1. 키의 해시코드 계산

키의 자료형은 보통 int,long이 된다. 키의 개수는 무한, int의 개수는 유한하기 때문에 서로 다른  두 개의 키가 같은 해시 코드를 가리킬 수 있음.

2, hash(key) % array_length와 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다.

3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다.(충돌 대비를 위해 연결리스트 사용)

 

# 키에 상응하는 값을 찾기위한 과정

주어진 키로부터 (1)해시코드 계산, (2)이 해시코드를  이용해 인덱스를 계산한다. 그 다음에는 (3)키에 사응하는 값을 연결리스트에서 탐색한다.

시간복잡도: 최적의 경우 O(1)

 

# 또 다른 구현 방법?

균형 이진 탐색 트리(balanced binary search tree)를 사용한다. 이 경우 최적의 경우는 O(logN)이 된다. 이 방법은 크기가 큰 배열을 미리 할당 안해도 되므로, 잠재적인 적은 공간을 사용한다.

 

사실 이 해싱(hashing) 부분의 정리는 이전 포스팅에서 정리한적이 있기 때문에 간략하게 정리하고 넘어가겠습니다.

조금 더 해싱에 대한 정확한 이해를 원하시는 분은 

https://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%B1Hashing-%EC%A0%95%EB%A6%AC%ED%95%98%EA%B8%B0

[알고리즘] 해싱(Hashing) 정리하기

 

참고하시면 되겠습니다.

 

# ArrayList와 가변배열

 C++ 로 알고리즘 테스트를 진행하고 있기때문에 ArrayList와 유사한 가변 크기 배열중 하나인 Vector에 대해서 설명하고 넘어가겠습니다.

 

Vector란 무엇일까요?

벡터(std::vector)는 동적 배열 구조를 C++ 로 구현한 것이다. 이것은 C의 배열(빠른 랜덤 접근이 가능한)처럼 행동하지만 자동으로 배열의 크기 조절과 객체의 추가와 삭제가 가능하다.

벡터는 C++ 표준 템플릿 라이버러리 중의 하나인 템플릿 클래스이다. 어떤 타입이라도 저장할 수 있지만, 한 번에 한 타입만 저장이 가능하다. 요소에 접근하거나, 앞 또는 뒤에 요소를 추가하거나 삭제할 수 있고 크기를 알 수 있는 멤버 함수를 제공하고 있다.

 

배열과의 차이점은 무엇일까요?

C++의 배열은 메모리에서 연속적이다. 이것은 하나의 타입을 가지는 블록이 여러 개가 붙어 있는 것처럼 생각할 수 있다. 배열의 모든 요소는 같은 타입을 가져야만 한다. 벡터는 무조건 데이터를 선형적으로 만들려고 한다. 만약 저장 공간보다 많은 양의 데이터를 추가시킬 경우에는, 현재 보유하고 있는 메모리의 두 배만큼을 할당하기 때문에 단순한 추가 할당으로는 선형적인 공간을 만들어내지 못하는 경우가 있을 수 있다. 이럴 때는 선형적인 다른 공간에 모든 원소를 하나하나 복사하기 때문에 속도가 느려진다.

삽입삭제가 많이 일어나는 Vector는 특정 원소를 탐색할 때 매우 비효율적으로 동작합니다.

따라서, 삽입 삭제가 많이 일어나는 경우에는 리스트를 사용하는 것이 효율적입니다.

 

Vector 멤버함수

 

 

• size(); 요소 개수를 반환한다
• max_size(); 벡터의 최대 크기를 반환한다.
• capacity(); 할당된 요소의 개수를 반환한다.
• resize( int n ); 벡터의 크기를 n으로 할당하고, 모두 0으로 초기화한다.
• resize( int n, int value ); 벡터의 크기를 n으로 할당하고, 모두 value로 초기화한다.
• reserve( int n ); 벡터의 크기를 n으로 할당한다. 초기화하지 않는다.
• clear(); 벡터의 요소를 모두 삭제한다.
• empty(); 벡터가 비어있는지 조사하여, 비어있다면 true, 아니라면 false를 반환한다.
• begin(); 벡터의 처음 주소를 반환한다.
• end(); 벡터의 마지막 요소의 다음 주소를 반환한다.
• front(); 벡터의 첫번째 요소를 반환한다.
• back(); 벡터의 마지막 요소를 반환한다.
• at( int n ); 벡터의 n번째 요소를 반환한다.
• assign( 주소1, 주소2 ); 주소1부터 주소2까지의 값을 벡터에 대입한다. 이미 있던 값은 소멸한다.
• push_back( int value ); 벡터의 마지막에 value 값을 가진 요소를 넣는다.
• pop_back(); 벡터의 마지막 요소를 삭제한다.
• insert( 주소, 값 ); 해당 주소에 '값'을 가진 요소를 하나 끼워넣는다.
• erase( 주소 ); 해당 주소의 요소를 삭제한다.
• swap( 벡터 ); 해당 벡터와 현재 백터의 요소를 모두 교환한다.

 

Vector 예제 코드

코드에 대한 설명으로 벡터를 배워보도록하겠습니다.

//
//  벡터.cpp
//  beakjoon_algorithm
//
//  Created by kgh on 03/07/2019.
//  Copyright © 2019 kgh. All rights reserved.
//
#include <bits/stdc++.h>
//#include <stdio.h>
using namespace std;
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> v1(3,5);        // {5,5,5}
    cout << v1.size() <<'\n';   // {3}
    v1.push_back(7);            // {5,5,5,7}
    
    // v1 i = 0 ~ 2^32-1 까지 돌게되는데, 여기서 vector는 unsigend int와 연산결과는 unsinged int 형변환이 일어나므로 -1을 빼주지말아야한다. -1을 빼주게 된다면 비어있는값이 있는경우 심각한 결과를 일으키게 한다.
    for(int i=0; i<v1.size(); i++){
        cout << v1[i];
    }
    cout << "\n";
    vector<int> v2(2);          // {0,0}
    cout << v2.size() << '\n';  // {2}
    v2.insert(v2.begin()+1, 3);    // {0,3,0}
    
    vector<int> v3 = {1,2,3,4};     // {1,2,3,4}
    v3.erase(v3.begin()+2);         // {1,2,4}  3만 삭제
    vector<int> v4;
    v4 = v3;
    
    cout << v4[0] << ' ' << v4[1] << ' ' << v4[2] << '\n';
    v4.pop_back();
    v4.clear();
}

 

#1 vector<int> v1(3,5); 

 

3개의 5라는 value를 vector에 int형으로 저장하게 됩니다.

5

5

5

 

#2 cout << v1.size() <<'\n'; 

 

vector에 할당된 vector size를 반환 받습니다. 값은 3이 나오겠죠"?

 

#3  v1.push_back(7); 

vector에 할당된 값뒤에 7이라는 값을 넣습니다.

5

5

5

7

 

#4  for(int i=0; i<v1.size(); i++){   cout << v1[i];    }

vector에 할당된 모든 원소를 뽑아냅니다.

 

#5 vector<int> v2(2);          

#1과 다르게 #5는 값을 지정하지 않으면 2개의 공간에 0이라는 값을 할당시킵니다. 

0

0

#6 vector<int> v3 = {1,2,3,4};   

v3 라는 vecotr 변수에 1,2,3,4 라는 값을 할당합니다

 

1

2

3

4

 

#7 v3.erase(v3.begin()+2);        

 

1(begin()+0)

2(begin()+1)

3(begin()+2)  ●(Pointer)

4 (begin()+3)

현재 begin() 함수를 호출하면서 첫번째 vector의 포인터점을 가져옵니다. 하지만 ,저는 begin() + 2의 포인터로 이동시켰으니, 위로 지금 표시한 것과 같이 3이라는 값에 pointer를 가지고 있습니다. 따라서 3이라는 값을 erase() 함수를 이용하여 원소의 값을 삭제시킵니다.

↓

 

1

2

4

3이라는 원소를 erase()함수를 통한 삭제 결과입니다.

 

#8 v4.pop_back();

위에 v4 = v3;이부분을 생략하였습니다. 결국 v4라는 벡터에 v3의 원소가 할당되었다는 뜻이고, 

v4.pop_back(); 이라는 함수를 호출 하게 되면 

1

2

4

 

↓

 

1

2

으로 원소가 빠져나오게 되는것을 확인 하실수 있습니다.

 

#9 v4.clear();

 

vector의모든 원소를 초기화 시킵니다.

 

clear()

 

더 자세한 사항은 전 포스팅에 Vector에 대한 자세한 설명과 예제코드를 Iterator를 사용하여 구현해놓았습니다. 참고하시면 되겠습니다.

 

https://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-C-STL-Vector%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

[알고리즘] C++ STL Vector에 대해 알아보자

 

이상 코딩인터뷰 다음장에서는 문자열 STL중 가장 많이 쓰이는 String에 대한 정리를 하겠습니다.