[TIL] 2주차_Day4: 자료구조/알고리즘 풀기(4)

💡Today I Learned

• 자료구조/알고리즘에 대한 네 번째 이론 및 실습 강의를 진행했습니다.
• 코딩테스트 연습 _ 프로그래머스 코딩테스트 연습 문제 풀이
• 해시, 그리디, 정렬 알고리즘을 사용하는 대표 문제 풀이

 

---

 

1. 해시(Hash)

- [key: value] pair → hash function을 통해 → hash table의 각각의 칸(hash bucket)에 저장

- hash collision(해시 충돌): 두 개 이상의 서로 다른 key가 서로 같은 bucket에 hash될 때(=사상될 때)

- 파이썬의 dictionary가 해시로 구현 → dict 아이템에 접근 → O(1) 상수 시간에 이뤄짐

- #완주하지 못 한 선수 → O(N)

 

2. 탐욕법(Greedy)

- 알고리즘 각 단계에서, 그 순간(현 단계)에 최적이라고 생각되는 것을 선택

- 앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality)에 영향을 주지 x

- #체육복 (데이터 개수에 따라 '정렬' 이용해서도 풀이 가능) → O(N)

- #큰 수 만들기 → O(N)

 

3. 정렬(Sort)

 - sorted, sort() 함수 → O(N*logN)의 시간복잡도

- #가장 큰 수 → O(N*logN)

 

---

 

📒 Furthermore

• #체육복 → 탐욕법(O(N)) 대신 정렬 알고리즘(O(KlogK)) 이용해서 풀이
  • → N의 수가 크고 K(여벌 체육복 수 or 체육복 도난 수)가 작을 때 O(K*logK) 알고리즘이 더 효과적일 수도