04.13 데이터 엔지니어링 4일차 - 코딩테스트 실전풀이

문제를 만났을 때 첫인상이 굉장히 중요! -> 어떤 알고리즘을 적용할지, 어떤 제약이 존재하는지, 문제의 지문으로부터 찾을 수 있어야 함

자료구조(와 알고리즘)의 선택

만약 이름 대신 번호가 주어졌다면? -> 선형 배열 (linear array)

번호 말고 다른 것(ex. 문자열)으로 접근할 수 잇는 좋은 자료 구조는 없는가?

해시 (Hash)

• 임의의 크기를 가진 데이터(key)를 고정된 크기의 데이터(value)로 변화시켜 저장하는 것
• 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array
• 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이 때 사용하는 함수를 해시함수라 함
• 해시값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠름

탐욕법 (greedy)

• 현재 상황에서 가장 좋은 것을 고르는 알고리즘

 

참고 : https://power-overwhelming.tistory.com/42

[자료구조/알고리즘] 해시(Hash) 란?