해시의 필요성(개요)

프로그래머스에서 "완주하지 못한 선수" 문제 채점 결과 😱

처음 결과를 봤을 때는 의아했다.
왜냐면 코드 실행결과 정답은 일치했기 때문이다.
지금까지 대학교 과제를 수행하거나 개인 프로젝트를 진행할 때는 효율 보다는 "결과"를 중요시 했기 때문에 이런 일이 벌어졌다고 생각한다.😓

그래서 현재 이중 포문으로 작성 된 코드에서 반복문의 횟수를 줄이는 방식으로 코드를 작성했지만 여전히 효율성 테스트에서 막혔다. 시간 복잡도가 여전히 O(n2) 이기 때문이였다.
결국에는 반복문 하나로만 작성해서 테스트를 통과 했지만
"더 근사한 코드는 없을까??" 라고 생각하게 돼서
다른 이들의 코드를 살펴보았다.

해시를 사용해서 문제의 효율성을 깔끔하게 해결한 코드를 보고
누군가 뒷통수를 때린 느낌을 받았다.
해시에 대한 "키 : 벨류"의 개념은 알았지만 이를 코드에 녹일 생각은 1도 못했기 때문이다.
서론이 길어졌지만,, 여튼 이러한 과정을 겪으면서 해시에 대한 개념을 다시 한번 정리하기로 했다!!

해시 (개념)

해시(Hash)는 key : value 형식으로 데이터를 효율적으로 관리 및 저장한다. 그래서 데이터를 아주 빠르게 삽입하거나 가져올 때 주로 사용한다.

해시의 구조는 다음과 같다.

해쉬테이블 : Key에 Value를 저장하는 데이터 구조
해시 함수 : key에 대해 산술 연산을 이용해 데이터의 위치를 찾을 수 있는 함수

핵심은 넓은 공간을 사용해, 데이터의 저장과 검색 시 발생되는 시간을 줄이는 것이다.
저장의 경우, key 값을 넣으면 해싱 함수에서 고유한 숫자(해시)가 리턴되는데 리턴된 값을 주소로 하는 저장 공간에 value를 저장한다.
검색의 경우, 해싱함수에 key를 넣어 대응되는 것의 주소를 리턴 받아서 그 저장공간에 저장된 value 값을 읽는다.

장점👍

순서가 보장될 필요가 없는데이터를 관리할 때
검색, 삽입, 삭제할 때 O(1)으로 단시간에 처리가 가능

단점👎

키에 해당하는 주소가 동일할 경우 충돌 해결을 위한
개방 주소법, 체이닝과 같은 자료구조가 필요하다.

해시의 개념이 필요한 경우

• 집계가 필요할 때
  중복되는 원소의 개수를 셀 때 유용하다
  

• 빠른 접근,검색
  다른 자료구조에 비해 데이터에 접근하는 속도가 매우 빠르기 때문에 빠른 접근 및 검색이 필요할 때 사용한다.

• 리스트 사용이 불가능할 때
  리스트의 인덱스가 문자열이나 튜플로 사용해야 하는 경우
  해시를 사용한다.

느낀점 : 지루하게 느껴졌던 자료구조를 코드로 녹여보니깐 책으로만 봤던 내용들이 훨씬 이해가 잘 되는 느낌과 성장하는 기분이 들었다. 이러한 경험을 토대로 어떤 문제에 이 자료구조 개념이 필요할까?를 고민 하면서 자료구조 개념을 다시 한번 복기해야 겠다는 생각이 들었다.😏