ㅇㅅㅎ

[ 해시 테이블 ] : 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응 👀 구현 방식 1. 연결리스트와 해시코드함수 : 탐색 시간 O(1) 더보기 ✔️ 키와 값 삽입법 키의 해시 코드 계산 키의 자료형은 보통 int 혹은 long인데, 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있습니다. 해시 코드를 이용하여 배열의 인덱스 계산 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있습니다. 키와 값을 해당 인덱스에 저장 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재합니다. 충돌에 대비해서 반드시 연결리스트를 이용해야합니다. ⭐ 충돌 : 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 서..

👀 뫼비우스 함수 : 정수가 제곱인수가 없는 정수인지 여부에 따라 분류하는 곱셈적 함수. 기호 : μ(n) 예) μ(1) = 1, μ(7) = -1, μ(30) = μ(2×3×5) = (-1)^3 = -1 ✔️ 뫼비우스 함수 ⭐ 약수 구하기와 소수 판별하기 응용 def mobius(n): d = divisors(n) for i in d: if i**2 in d: return 0 return (-1)**(sum([is_prime(i) for i in d])) def divisors(n): result = set() for i in range(2, int(n**0.5)+1): if n%i == 0: result.add(i) result.add(n//i) return sorted(result) + [n] de..

👀 소인수분해 : 자연수를 소인수의 곱으로 나타낸 것 예) 10을 소인수분해 : 10 = 2×5 ⭐ 소인수 : 자연수의 인수 중 소수 ⭐ 소수 : 약수가 1과 자기 자신 뿐인 자연수 ✔️ 소인수분해 함수 입력 n이 2이상일 때 {소수1: 갯수1, 소수2: 갯수2, ...}형태로 반환. def factorization(n): a, result = 2, {} while n>1: while not n%a: if not a in result.keys(): result[a] = 1 else: result[a] += 1 n //= a a += 1 return result

👀 소수 : 약수가 1과 자기 자신 뿐인 자연수. ⭐ 약수 : 어떤 수를 나누어 떨어지게 하는 0이 아닌 정수 예) 2, 3, 5, 7, 11, .... ✔️ 소수를 판별하는 함수 입력 n이 소수일 경우 True 반환. 소수가 아닐 경우 False 반환. def is_prime(n): return n > 1 and all(n % i != 0 for i in range(2, int(n ** 0.5) + 1))

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 프로세서 구조 컴퓨터 구조의 발전 인텔 8086 (1981): 5 MHz (IBM PC에 처음 사용됨) 인텔 80486 (1989): 25 MHz (숫자를 상표로 사용할 수 없다는 법원 판결 때문에 i486이 됨) 펜티엄 (1993): 66 MHz 펜티엄 4 (2000): 1.5 GHz (약 30단계의 깊은 파이프라인) 펜티엄 D (2005): 3.2 GHz (이후 클럭 속도의 증가가 멈춤) 쿼드코어 제온 (2008): 3 GHz (하나의 칩의 코어 수가 성능의 주요 요소) 병렬 알고리즘의 문제점 프로세서는 계산할 데이터를 필요로 하나 SRAM은 4개보다 많은 메모리 요청을 병렬적으로 처리 불가합니다. ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 정의 P : 다항 시간에 풀 수 있는 모든 문제들의 집합 예시) 음수 가중치 사이클 탐지 ∈ P EXP : 지수 시간에 풀 수 있는 모든 문제들의 집합. 예시) n×n 체스 ∈ EXP 그러나 ∈/(속하지 않음) P → n×n 체스 주어진 보드 배열에서 누가 이기는가? R : 유한 시간에 풀 수 있는 모든 문제들의 집합 예시) 테트리스 ∈ EXP 그러나 ∈ P 인지는 모름 → 주어진 보드와 조각들에서 살아남기 정지 문제 : 컴퓨터 프로그램이 주어졌을 때, 그것이 한 번이라도 정지하는가? 계산 불가능 (∈ / R):이것을 푸는 알고리즘은 없다 (모든 입력값에 대해 유한 시간에 맞게 푸는 것) 결정 문제: 답..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습 ⁉️ 동적 프로그래밍의 5단계 하위 문제 정의하기 ⇒ 하위 문제의 개수 세기 (해법의 일부분을) 추측하기 ⇒ 선택지의 개수 세기 하위 문제의 풀이 연관짓기 ⇒ 하위 문제당 시간 계산 재귀+기억 또는 DP 테이블을 상향식으로 만들기 ⇒ 시간 = 하위 문제당 시간·하위 문제의 개수 하위 문제가 비순환적인지/위상학적 순서인지 확인하기 원래 문제 풀이 ⇒ 추가 시간 필요 : 하위 문제의 풀이 또는 하위 문제들로 조합하여 풀기 ✔ 2종류의 추측 2&3단계에서 어떤 하위 문제를 사용할지 추측 (피보나치를 제외하고 모든 동적 프로그래밍에서 사용) 1단계에서 정답 구조에 대해 더 많은걸 기억하거나 추측하기 위해 ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습 ⁉️ 동적 프로그래밍의 5단계 하위 문제 정의하기 ⇒ 하위 문제의 개수 세기 (해법의 일부분을) 추측하기 ⇒ 선택지의 개수 세기 하위 문제의 풀이 연관짓기 ⇒ 하위 문제당 시간 계산 재귀+기억 또는 DP 테이블을 상향식으로 만들기 ⇒ 시간 = 하위 문제당 시간·하위 문제의 개수 하위 문제가 비순환적인지/위상학적 순서인지 확인하기 원래 문제 풀이 ⇒ 추가 시간 필요 : 하위 문제의 풀이 또는 하위 문제들로 조합하여 풀기 ⁉️ 텍스트 정렬, 블랙잭은 시퀀스와 관련있습니다.(단어, 카드의 시퀀스) ⁉️ 문자열/시퀀스 x에 대해 유용한 문제들 ✔ 괄호 묶기 : A[0] · A[1]···A[n − 1]를 계..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 동적 프로그래밍 * DP ≈ “세심한 무차별 대입법” * DP ≈ 추측 + 재귀 + 메모이제이션 * DP ≈ 문제를 합리적인 개수의 하위 문제로 나누고 해를 비순환적으로 연관 짓습니다. 보통 해의 일부를 추측합니다. * time = #subproblems x time/subproblem → 근본적으로 분할 상환합니다. 각 하위 문제를 한 번만 셉니다. → 메모이제이션을 통해 처음 이후에는 O(1) 시간이 걸립니다. * DP ≈ DAG에서의 최단 경로 ⁉️ 동적 프로그래밍의 "간단한" 5단계 * 반드시 순차적인 것은 아닙니다. 하위 문제를 정의합니다. ⇒ 하위 문제의 개수를 셉니다.(#subprobs) 해..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 동적 프로그래밍(DP) 강력한 알고리즘 디자인 기법 보기에는 지수 시간이 걸리는 많은 문제도 DP를 사용하면 (사용해야지만) 다항 시간에 풀 수 있음 특히 최적화 문제(최소화/최대화)에 쓰임(최단 경로 문제) * DP ≈ “세심한 무차별 대입법” * DP ≈ 재귀+ 재사용 ✔ 피보나치 수 ⁉️ 목표 : n번째 피보나치 수를 계산하는 것 ⁉️ 단순 알고리즘(재귀 정의) def fib(n): if n