IT 복수전공 일기장

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 결과를 저장하여 동일한 부분 문제를 여러 번 풀지 않도록 하는 알고리즘 기법입니다. 이는 특히 중복 계산을 피함으로써 효율성을 크게 향상시키며 주로 최적화 문제에서 사용됩니다.동적 프로그래밍의 사용 조건1. 최적 부분 구조(Opptimal Substructure):큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복 부분 문제(Overlapping Subproblems):동일한 작은 문제를 반복적으로 해결해야 한다동적 프로그래밍은 메모이제이션(Memoization)과 타뷸레이션(Tabulation) 두 가지 접근 방법으로 구현될 수 ..

병합 정렬(Merge Sort)은 분할 정복(divide and conquer) 방식을 사용하는 정렬 알고리즘입니다. 이 방식은 큰 문제를 작은 문제로 나눈 뒤, 각각 해결한 다음 그 해결된 작은 문제들을 다시 합쳐서 원래의 문제를 해결하는 방식입니다. 병합 정렬은 주로 리스트를 반으로 계속 나누고, 나누어진 각 부분을 정렬한 다음에 다시 합치는 과정을 반복합니다.  병합 정렬의 과정:병합 정렬은 크게 두 가지 주요 단계로 나누어집니다: 분할(divide)과 정복(conquer) 단계입니다. 1. 분할 단계: - 주어진 리스트를 반으로 계속 나눕니다. 각 부분이 충분히 작아질 때까지 나누는데, 보통 하나의 원소만 남을 때까지 나눕니다. - 하나의 원소만 있는 리스트는 자연스럽게 정렬된 것으로 간주할 수..

삽입 정렬(Insertion Sort)은 매우 직관적인 정렬 방법 중 하나로, 카드 게임을 할 때 카드를 정렬하는 방법과 비슷합니다. 삽입 정렬의 기본 아이디어는 현재 정렬된 리스트에 새로운 원소를 그것이 들어갈 적절한 위치에 삽입하는 것입니다. 작지만 정렬된 배열에서 주로 사용합니다. 정렬된 배열의 크기를 하나씩 늘려가면서 진행합니다. 삽입 정렬 과정:1. 리스트의 두 번째 원소부터 시작합니다.2. 해당 원소를 이전의 원소들과 비교하여 적절한 위치에 삽입합니다.3. 이 과정을 리스트의 모든 원소에 대해 반복합니다. 예를 들어, 숫자 리스트가 다음과 같다고 해봅시다:[4, 3, 5, 1, 2]- 첫 번째 원소 (4)는 이미 정렬된 것으로 간주합니다.- 두 번째 원소 (3)을 적절한 위치, 여기서는 (4 ..

1. 다음의 recurrence를 solving 하고 과정을 설명하라2. 아래 수식을 증명하라   3. supersequence의 길이문자열 Z가 X의 subsequences 일때, X를 문자열 Z의 super sequence라고 합니다. 예를 들어, 문자열 X = algorithmisboring 는 Z = algibing의 super sequence입니다. 두 문자열 X와 Y가 주어졌을 때, X와 Y 두 문자열이 모두 문자열 Z의 supersequence 이면 Z를 X와 Y의 common supersequence라고 합니다. 우리는, 두 문자열 X와 Y가 주여졌을 때, X와 Y의 the shortest common supersequence Z와 Z의 길이를 찾으려고 합니다. input: Strings ..