💻 컴퓨터

고전적 암호화 방법과 한계 일반적인 과정 암호화 복호화 예 Caesar Cipher 영문과 숫자를 일대일 대응 평문에 등장하는 모든 알파벳을 동일한 칸수만큼 미는 방식으로 암호화 알파벳이 총 26종류이므로, 26으로 나눈 나머지만을 생각 Affine Cipher 평문(Plaintext-P)와 암호문(Ciphertext-C)에 대하여 암호화 C = K_1 P + K_2 (mod 26) k1과 k2를 기준으로 함수를 계산 고전적 암호 체계에 대한 Brute-Force 공격 무차별 대입공격으로 무력화될 수 있음 소인수분해 기반 암호 체계 Euler Phi Function 자연수 n에 대해 n보다 작으면서 n과 서로소인 자연수의 개수를 파이(n)으로 정의 파이(p) = p-1임은 자명 ⇒ 성질 자연수 m과 n이..

동적계획의 이해와 구현 Dynamic Programing 복잡한 꼴을 가진 문제를 보다 단순한 여로 문제로 쪼개어 해결 ‘과거에 계산하였던 결과를 확인’ ‘점화식을 세워 문제를 해결하는’ 형태로 활용 ex - a(n+1) = a(n) + 2 와 같은 식 ⇒ 불필요한 반복적인 행위를 최소화하는 것이 목표 ( Memoization or Tabulation - 중간값 기록 ) Memoization 예) 피보나치 수열 def ex_func(N): if (fibo_list[N] != -1): return fibo_list[N] else: fibo_list[N] = ex_func(N-1) + ex_func(N-2) return fibo_list[N] N = int(input()) fibo_list = [-1 for..

재귀적 접근의 원리와 실제 Recursion 재귀적 호출 분활정복 패러다임 구현에 많이 쓰임 bottom-up과 top-down으로 구분 가능, 재귀는 top-down에 해당 분활정복의 이해 풀고자 하는 문제를 작은 크기로 분활 충분히 문제가 작아진 경우 → 정복 작은 개별 문제들에 대한 해를 통합하는 과정을 거듭하여 최종 해 도출 Sequential Search - 무대뽀 Binary Search - ‘분활정복 패러다임’에 속함 n → logn으로 줄이는 방법도 있음 (지수를 쪼개면서) 분활정복을 이용한 정렬 Merge Sort 수열이 주어질 때, 수열을 절반으로 쪼개는 과정 반복 더이상 쪼갤 수 없는 경우, 이미 쪼개진 수열을 순서에 맞춰 합치는 과정 수행 계속 쪼개는 과정 진행 이후 순서를 맞추며 ..

정렬의 성능과 시간복잡도 Heap sort Max Heap 자료구조를 이용 비어있는 Heap에 주어진 원소를 순서대로 삽입, 그래도 Heap 성질이 유지되도록 Heap 최상단에는 최댓값이 존재함이 보장, 수열의 맨 끝에 Heap 최상단 값을 위치 Heap 최상단 원소를 제거한 후, Heap 성질을 유지하며 동일한 과정 반복 즉, N개 원소 삽입 - Heap이 다시 빌 때까지 데이터 N개 제거 (nlogn - 노드의 높이가 중요함) Heap 구성하는 시간 복잡도 - log1 ~ logn 제거하며 정렬하는 시간복잡도 -logn ~ log1 → log(n!) 빅 O 방법을 통해서 T(n)이 nlogn보다는 작다는 걸 알 수 있음 빅 오메가 방법을 통해서 T(n)이 nlogn보다는 크다는 걸 알 수 있음 빅 O..

순차 탐색과 이진 탐색 순차탐색 첫 번째 원소부터 순차적으로 확인 이진탐색 (정렬이 이미 이루어진 경우) 중앙을 기준으로 반으로 쪼개어 대소를 비교하여 원하는 수가 속한 부분을 확인 Log_2 (n)의 수를 가짐 nubers = [15, 19, 22, 33, 44, 55, 66, 77, 88, 99] target = 33 left = 0 right = len(nubers) - 1 while (1): mid = (left + right) // 2 if nubers[mid] == target: print("find it") break elif nubers[mid] > target: right = mid - 1 else: left = mid + 1 if left > right: print("not find")..

이 시리즈는 고려대학교 정보대학 '유용재 교수님'의 수업을 듣고 정리한 자료입니다. 개인적으로 굉장히 존경하는 분이며, 더 알아보고 싶으신 분은 아래 링크를 참고해주세요. https://yooy.mystrikingly.com/ 시간복잡도, 공간복잡도 알고리즘 주어진 문제를 해결하기 위한 단계적 절차 혹은 방법 모호성이 없고 실행 가능하며 종결이 이루어지는 절차의 집합 시간복잡도 어떤 프로그램이 소요하는 시간을 나타내는 개념 시간복잡도(TC) = (컴파일 시간) c + (실행 시간) T(n) 프로그램 분석에서 일반적으로 ‘실행 시간’이 ‘컴파일 시간’보다 중요 공간복잡도 돌리는데 필요한 자원(리소스) 시간 > 공간 (중요성) ‘연산 횟수’가 중요 반복이 아닌 단순 변수 선언 등은 무시 실질적으로 나누거나 ..