코테스터디 2022
-
[Python] 알고리즘 : 탐욕법 (Greedy Algorithm)코테스터디 2022 2022. 7. 4. 23:45
🔹 그리디 알고리즘(탐욕법) 선택의 순간마다 가장 좋은 것(최적)이라 생각되는 것을 선택하는 알고리즘. 각 순간에 대해서는 최적일 수 있으나, 최종적인 해답이 모든 경우의 수에서 최적이라는 보장이 없다. 그러나 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다는 장점도 존재. 그리디 알고리즘이 적용가능한 문제인지 판단 필요 🔹 파이썬에서의 구현 예제 - 동전 문제 가치의 합이 K인 동전을 가장 최소한의 개수로 만드려면, 가치가 가장 큰 동전부터 개수를 세어 나가면 된다. 590원을 세 종류의 동전으로 만들면, 가장 큰 단위인 100원 다섯 개, 50원 한 개, 10원 네 개로 총 10개의 동전이 필요하다. https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째..
-
[Python] 알고리즘 : 해시 테이블(Hash Table)코테스터디 2022 2022. 6. 26. 01:44
🔹 해시테이블이란? key-value 로 이루어진 자료 구조 내부적으로 배열을 사용하여 데이터를 저장하며 입력 키 값으로부터 얻은 해시값을 인덱스로 사용하기 때문에, 데이터를 빠른 속도로 검색하거나 처리한다. 평균 시간복잡도 : O(1) 🔹 해시란? 해시 : 해시 함수 또는 해시 알고리즘(임의 길이의 데이터를 고정된 길이의 데이터로 매핑)에 의해 얻어지는 값(위키백과) 해시 충돌 : 해시 함수가 서로 다른 두 입력값에 대해 동일한 출력을 만듦. 즉, 두 개 이상의 다른 KEY가 동일한 인덱스로 매핑될 경우 해시 충돌이 발생, 해시 테이블의 성능을 저하 방지하기 위한 해시충돌 알고리즘이 있다. 🔹 파이썬에서의 구현 파이썬에서는 key-value의 형태로 이루어진 dictionary 자료 구조가 해시 테이블..
