[07-3] 해시 테이블을 활용해보자

이번에는 해시 테이블을 어떻게 활용하면 좋을지, 언제 활용하면 좋을지 알아보자.

 

특징:

1. "key:value" 쌍으로 저장

2. O(1)의 시간 복잡도로 복잡도가 낮음

3. in 을 활용할 수 있음

4. 추가, 수정, 불러오기 기능이 탁월

 

이러한 특징을 고려했을 때, 해시 테이블의 활용도는 정말 무궁무진하다.

 

1. 검증할 때

⇒ 있는지, 해당 부분이 있는지, 맞는지 이렇게 검증할 때 쓸 수 있다.

이 부분이 가장 강력하다. 해당 부분을 '검증' 이란 키워드로 표현해서 이해하기 어려울 수 있는데 쉽게 설명하면 다음과 같다.

2. 리스트를 쓸 수 있지만, 시간 복잡도를 고려해야할 때

 

배열 중 2개의 숫자를 더해서 M가 만들어지면 True, 아니면 False를 출력해라

의 문제에서 포인터를 쓸 수도 있고, for 문을 반복해서도 가능하다.

하지만 복잡도의 문제가 만만치 않아진다. 특히 배열이 길어질수록.

 

하지만 이것도 결과적으로 M가 되는지 '검증' 하는 문제기 때문에 딕셔너리로 쓸 수 있다.

딕셔너리의 key를 활용하면 되는데 예를 들어서 배열[i] + b = M일 경우, b가 딕셔너리에 있니?

라고 코드를 구현하면 매우 간단하고 빠르게 해결할 수 있다.

 

딕셔너리는 if, while을 써도(코드를 적절하게 작성한다면) O(n)의 시간 복잡도로 복잡한 문제를 해결할 수 있다.

리스트를 썼다면 전체를 봤을 걸, 딕셔너리로 짧게 가능하다는 것이다.

 

그러기 위해선, 문제를 잘 정의해야한다.

문제를 보고 답을 구하기 위해서 '조건'을 어떻게 구성할 것인가? 에 대해 꼼꼼하게 생각해야한다.

코드는 쉽게 말하면 1/2 이다.

여기에 있으면 하고, 없으면 말고. 제거하거나, 추가하거나.

이렇게 이분법적이다. 물론 가지치기를 할 수 있지만

 

내가 하고 싶은 말은, 처음에 코드를 구현할 때 애를 먹는게 이 조건이다. 어떻게 이 생각을 하지? 어떻게 이걸 이렇게 구현했지? 하는 생각이 들텐데 이럴 때 쉽게 생각하자

yes or no 로 나눌 수 있는 조건을 만들어보면 된다. 그렇게 조건을 추가하고 추가하면 된다.

사람인지라 우리 머리속에서는 이미 많은 단계의 연산이 거쳐서 그 행동을 하는 것이지만, 코드는 그렇지 않다. 그 사소한 행동을 모두 하나씩 적어야 하기 때문에 어렵게 생각하지 말고 조건을 하나씩 만들어서

큰 형태에서 작은 형태로 만들어 나간다! 는 느낌으로 조건을 생각하면 된다.

 

예를 들어서,

리스트에서 연속된 숫자가 몇개인지 구하고 싶을 때, 머리속에서는 쉽게 눈으로 따라가지만 코드는 그렇지 못하다.

따라서 하나의 스텝씩 밟아보자.

1. 정렬을 한다.

2. 앞에 숫자 + 1이 뒤의 숫자인지 확인한다.

3. 맞으면 계속 진행, 틀리면 다시 리셋

 

이런식으로 한 스텝씩 생각하면 문제를 해결하는데 도움이 된다!

더 나아가서는 예외처리(0일 땐 어떻게?)도 해야하지만..

우선은 하나씩 스텝을 밟아나가면서 코드를 구현해보자.