[데이터 엔지니어링 데브코스 2기] TIL-2주차-파트04 자료구조와 알고리즘

0. 강의 내용

1. 해쉬(hash)를 이용한 코딩테스트 문제 풀이
2. 그리디(greedy) 코딩테스트 문제 풀이

본 강의에서는 개념적인 내용보다는 실전 문제 풀이에 대한 내용이 대부분이었다. 따라서 저작권 상, 문제 및 코드를 올리지 못하여 내용이 짧다.

1. 해시(Hash)

Hash Table에 key를 mapping시키는 구조이다. 즉, key -> bucket(value)라고 표현할 수 있다. 다만, 주의할 점이 있는데, 만약 서로 다른 key가 같은 hash budket을 가리킨다면 이는 collision(충돌)이 일어난 경우이다. 따라서, 이와 같은 경우에 대한 보완책이 필요하다.

Hash에 대한 접근은 O(1)으로 상수 시간에 접근이 가능하다.

2. Greedy

현재의 선택이 나중의 선택의 최적성에 대한 영향을 끼치지 않을 경우에 유용하다.

3. 코딩테스트 문제 풀이 시 고려 사항

1. 문제의 요구 사항을 파악한다.
2. 문제의 제약 조건을 확인한다.
3. 문제에 대한 알고리즘을 구현한 후, 해당 알고리즘의 시간복잡도를 고려한다.

결과가 같게 나오더라도 알고리즘마다의 시간 복잡도를 고려하여 최적의 알고리즘을 선택하는 것이 중요하다.