CS/Algorithm4 [Python] 소수 판별(IsPrime) 알고리즘 / 에라토스테네스의 체, 나누기 소수(Prime Number)란? 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 나누기를 통해 정의에 의해 나누기를 사용하여 구현할 수 있다. n이라는 수가 소수인지 판별하는 코드를 구현해보자. 1은 소수가 아니다. 시간 복잡도를 위해 $\sqrt(n) + 1$까지만 탐색한다. def isPrime(n): if n == 1: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True print(isPrime(1)) # False print(isPrime(11)) # True print(isPrime(12)) # False print(isPrime(13)) # True 에라토스테네스의 .. 2023. 5. 12. 10진수 n진수 변환, n진수 10진수 변환 진수 문제가 나오면 항상 내장 함수를 찾느라 시간이 좀 걸렸다..! 해당 내용을 정리해보기로 한다 ! 10진수에서 n진수 변환 10진수 > 2진수, 8진수 16진수 python에서는 2진수, 8진수, 16진수 변환을 위한 bin, oct, hex 메서드를 지원한다. 주의할점은 앞 두 글자는 진법 표시를 위해 있다는 점 ! bin(11)[2:] 와 같이 얻을 수 있다. print(bin(11)) print(oct(11)) print(hex(11)) # 0b1011 # 0o13 # 0xb 10진수 > n진수 혹은 함수작성을 통해 원하는 진법으로 변환이 가능하다. def convert(n, base=2): T = '0123456789ABCDEF' q, r = divmod(n, base) if q == 0: r.. 2023. 5. 10. 우선순위 큐(Priority Queue)가 뭔데 ! https://www.youtube.com/watch?v=AjFlp951nz0 우선순위 큐 (Priority Queue) 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 큐를 구현 하는 방법 리스트를 이용하여 구현 - 삽입: $O(1)$, 삭제: $O(N)$ 힙(heap)을 이용하여 구현 - 삽입: $O(logN)$, 삭제: $O(logN)$ Heap으로 구현하자.. N개의 데이터를 모두 힙에 넣었다가 꺼내면: $O(NlogN)$ 힙(Heap)이 뭔데.. 힙은 완전 이진 트리 자료구조의 일종 힙에서는 항상 루트 노드(root node)를 제거 최소 힙 (Min heap) 루트 노드가 가장 작은 값을 가짐 값이 작은 데이터를 우선적으로 pop !(제거) 최대 힙 (Max heap) 루트 노드가.. 2023. 4. 12. 동적 프로그래밍 (Dynamic Programming, DP) 이란? 나동빈님 유튜브 내용을 참고 하였다. 개요 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 구현 방식 Top down Bottom up 특정 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 예제. 피보나치 수열 피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산 가능 점화식으로 표현할 수 있다. 점화식을 재.. 2023. 3. 14. 이전 1 다음
