[CS/Algorithm이론]

재귀함수란 어떤 함수 내부에서 한 번 이상 자신의 함수를 호출하는 경우에 그 함수이다. 이때 함수를 '알고리즘'으로 바꿔 이해할 수도 있다. 예1: 1+2+3+ + N 1부터 n까지 더하는 문제가 있다고 하면, sum(n) = sum(n-1) + n : n-1까지 더하

1부터 n까지의 합을 계산해보자루프를 활용한 방법🔽 재귀적으로 작성하는 법🔽 sum(n) = sum(n-1) + n 의 점화식이며, 바닥조건은 sum(1) = 1 이다. 따라서 코드는 으로 나타낼 수 있다. 수행시간 역시 재귀적으로 정의한 다음 > Big O 를 계

복잡~하다

A,B,C (기둥)과 n개의 원판이 이 주어진 경우.1\. 위부터 n-1개를 B로 옮긴다. : A(n-1) > B2\. 가장 큰 것을 C로 옮긴다. : n > C3\. B의 n-1개를 C로 옮긴다. : B(n-1) > C2번은 1번의 연산이며, 1,3 번은 재귀연산이다

a. 루프를 활용한 방법b. 재귀적으로 작성 n까지의 합은 n-1까지의 합에 n을 더한 것과 같다. c. 수행시간 루프를 활용한 경우 매번 상수번의 기본 연산만 수행했으므로 O(n) 재귀함수의 경우 T(n) = T(n-1) + 1, T(1) = 1 d. 점화식 T(n)

선택 문제의 공통적인 구조를 알아보자. a. 입력: 리스트에 n개의 수와 1과 n사이의 자연수 값 k가 주어진다.b. 출력: 입력으로 주어지 수 중 k번째로 작은 수를 찾아 리턴한다.c. 목표: 비교 횟수를 최소화하자 a. 다음 코드를 보자. 시작 최대값은 A0 으로

원래 문제를 풀 수 있을 정도의 작은 크기의 부분 문제로 분할해 각각 해결 한 후, 부분 문제의 해답을 잘 모아 원래의 해답을 얻는 방법. 크기가 작아질 뿐 문제 자체는 변하지 않음 > 재귀적인 분할재귀적인 분할이므로 수행시간 T(n) 은 점화식으로 표현 Selecti

리스트에 저장된 값들을 크기 순서에 따라 재배열하는 문제.비교횟수와 자리바꿈 횟수를 최소로 하는 것이 목표. python 에서 제공하는 정렬함수는 Tim sort 이다. a.sort() 또는 b = sorted(a) 를 이용하자. a. 기본 정렬 알고리즘(단순하지만 느

1\. 재귀 알고리즘재귀적으로 중복 호출되어 매우 느리게 실행된다. (지수 시간이 필요) 따라서 피보나치 수를 계산 후 기록해놓고 - 필요할 때 재사용하자는 아이디어를 제시한 것!2\. 기록 + 재사용 재귀 알고리즘(memoization)fibo(k) 값은 처음 게산이

음수를 포함한 숫자 리스트 A가 주어질 때, 구간을 마음대로 설정해서 합이 최대가 되는 구간을 구한다고 하자. 이를 어떻게 DP 로 구할 수 있을까? 예시 배열은 A = -2, 0, -1, 3, 2, -1, 2, -2 이다. Sol1) 모든 구간 (i,j) 에 대해 합

📚 목차 1\. LCS 문제 2\. 편집거리3\. 행렬 곱셈 4\. LIS LCS 란 Longest Common Subsequence 의 약자로 주어진 문자열 2개가 주어질 때 두 문자열 내의 문자를 뽑아 만들 수 있는 최장 길이의 공통 부문자열, 길이를 반환하는 문

➡️ 객관적, 단순한 전략으로➡️ 알고리즘 정확성에 대한 증명이 필요1원, 5원, 10원, 100원이 주어지고689원을 개수 최소로 지불하는 방법을 고민해보자. = 100 6 + 10 8 + 5 1 + 1 4 => 총 19개의 동전을 지불해야 한다. 이게 정말

그리디 알고리즘 중 허프만 코드 문제가 있었고, 1\. Decode Tree 를 통해 prefix-free code 를 만족시키며2\. 비용 = 빈도수 비트 수 = f(x) depth(x) 를 최소로 하기 위해 빈도수가 높으면 루트와 가깝게, 빈도수가 낮으면 루트와

입력 A = {8, 6, 7, 5, 3, 10, 9} 가 주어지고, S = 15 합이 주어질 때, A의 Subset 중 합이 S가 되는 부분집합이 존재하면 True, 존재하지 않으면 False 를 리턴하는 문제. (Decision Problem 문제) 쉽게 생각할 수

Knapsack 은 Non-Polynomial 한 문제로 (왜? 가짓수만 해도 2^n이기 때문이다.) 어려운 문제에 속한다. 대표적인 다른 Non-Polynomial 로는 Subset이 있다.Knapsack 을 푸는 크게 두 가지 알고리즘을 생각해봤다. 0/1 로 풀기