⏱️ 파이썬의 set 함수와 list 함수의 in 함수 사용 시 시간복잡도 in 함수 사용 시 set 함수: 평균 O(1) dict 함수 : 평균 O(1) list 함수: 평균 O(n) set 함수는 내부적으로 해시 테이블을 사용하여 데이터를 저장하기 때문에 in 연산을 평균 O(1)의 시간 복잡도로 수행할 수 있습니다. 반면에 list 함수는 내부적으로 동적 배열을 사용하여 데이터를 저장합니다. 이때, in 연산은 리스트를 처음부터 끝까지 순차적으로 탐색해야 하므로, 평균 O(n)의 시간 복잡도를 가지게 됩니다. 즉, 리스트의 크기가 커질수록 in 연산의 속도는 느려질 수밖에 없습니다. 테스트 결과 test=1000000 set_func=set() for i in range(test) : set_fun..

🤔 그리디 알고리즘이란? 그리디 알고리즘(Greedy Algorithm)은 최적해를 구하는 데 사용되는 알고리즘 중 하나입니다. 최적해란? 주어진 문제에서 가장 최소 또는 최대 값을 구하는 것 그리디(greedy) 알고리즘은 말그대로 탐욕스럽게 미래를 생각하지 않고 현재에서 매 순간 최선의 선택을 하면서 답을 구하는 알고리즘입니다. 💡 그리디 알고리즘의 예시 거스름돈 문제 예를 들어, 1원, 5원, 10원, 50원, 100원의 종류의 동전이 있다고 가정해보겠습니다. 거슬러줘야 할 금액이 230이라면, 그리디 알고리즘을 사용하여 동전의 개수의 총합을 적게 줄 수 있다. 가장 큰 동전부터 거슬러주면 된다. 100원짜리 동전 2개 거슬러 주기 10원짜리 동전 3개 거슬러 주기 총 5개의 동전을 사용하여 거슬러..

에라토스테네스의 체와 제곱근 방식은 소수를 구하는 알고리즘 중 가장 대표적인 방식입니다. 대략적으로 어느 정도 차이난다는 거는 구글링으로 알긴했는데 귀찮지만 직접 구현해 보았습니다... start! ⚙️ 동작 방식 제곱근: N이 소수인지 판별하기 위해, N보다 작거나 같은 자연수 중 가장 큰 수인 sqrt(N)까지만 확인하는 방식입니다. 에라토스테네스의 체: 범위 안에서 소수를 찾는 방식으로, 2부터 시작하여 배수들을 지워나가는 방식입니다. 물론 제곱근도 사용하고 제곱근 안의 배수들을 사용해서 시간을 줄입니다. ⏱ 시간 복잡도 제곱근: O(sqrt(N)) 에라토스테네스의 체: O(NloglogN) 🚀 구현 import time def find_primes(start, end): # 에라토스테네스의 체 알..

동적프로그래밍은 처음 들어보는 사람들에게는 어려울 수 있지만, 실제로 코드를 작성해보면 그리 어렵지 않습니다. 아래 예제는 대표적인 동적프로그래밍 문제 중 하나인 피보나치 수열을 살펴보지만, 피보나치하면 재귀를 생각하시는데 결론은 dp를 사용할때 재귀를 사용하지않고도 반복문과 배열만을 이용해서도 가능하다 입니다. 동적프로그래밍의 기본 개념과 적용 방법을 알아보겠습니다. 아래에는 1)일반적인 피보나치와, 2)TOP-DOWN 방식과 3)BOTTOM-UP 방식으로 구현한 피보나치 수열 코드가 있습니다. 코드를 따라해보면서, 동적프로그래밍의 장점과 효율성을 알아보겠습니다 💻 🔍 피보나치 수열과의 비교 동적프로그래밍의 개념을 이해하기 위해 가장 대표적인 예시인 피보나치 수열을 살펴보겠습니다. 피보나치 수열은 첫번..

🧬 이진 탐색 알고리즘 이진 탐색은 정렬된 배열에서 특정 값을 찾는 데에 사용되는 검색 알고리즘입니다. 이진 탐색의 핵심은 배열이 정렬되어 있다는 것입니다. 배열이 정렬되어 있기 때문에, 배열을 반씩 나누어서 탐색 범위를 줄일 수 있습니다. 이진 탐색은 배열의 중간 값(mid)을 선택하고, 찾으려는 값이 중간 값보다 작으면 배열의 왼쪽 반쪽을, 찾으려는 값이 중간 값보다 크면 배열의 오른쪽 반쪽을 탐색합니다. 이러한 과정을 반복하여 원하는 값이 나올 때까지 탐색합니다. 이진 탐색은 탐색 범위를 반으로 나누기 때문에, 최악의 경우에도 탐색 시간이 O(log n)으로 매우 빠릅니다. 이진 탐색을 사용하여 정렬된 배열에서 값을 찾을 때, 선형 탐색을 사용하는 것보다 훨씬 효율적입니다. 아래 그림은 이진 탐색 ..