문제를 만났을 때 첫인상이 굉장히 중요! -> 어떤 알고리즘을 적용할지, 어떤 제약이 존재하는지, 문제의 지문으로부터 찾을 수 있어야 함
자료구조(와 알고리즘)의 선택
만약 이름 대신 번호가 주어졌다면? -> 선형 배열 (linear array)
번호 말고 다른 것(ex. 문자열)으로 접근할 수 잇는 좋은 자료 구조는 없는가?
해시 (Hash)
- 임의의 크기를 가진 데이터(key)를 고정된 크기의 데이터(value)로 변화시켜 저장하는 것
- 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array
- 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이 때 사용하는 함수를 해시함수라 함
- 해시값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠름
탐욕법 (greedy)
- 현재 상황에서 가장 좋은 것을 고르는 알고리즘
참고 : https://power-overwhelming.tistory.com/42
[자료구조/알고리즘] 해시(Hash) 란?
Hash개념임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 asso
power-overwhelming.tistory.com
반응형
