아무것도 모르는 공대생의 지식 탐험기

1. Solve the exercise problem 14 of the chapter 7. 합병정렬 알고리즘은 분할정복(divide and conquer) 방식을 사용하여 리스트를 반으로 나눈 후, 각각을 재귀적으로 정렬하고 다시 합병(merge)하는 과정을 반복하여 정렬을 수행합니다. 합병하는 과정에서 레코드를 비교하고 저장하게 되는데, 두 개의 리스트를 비교하면서 작은 값을 새로운 리스트에 저장하는 것을 반복합니다. 이때 레코드의 저장 횟수는 입력 크기 n에 비례합니다. 따라서, 합병정렬 알고리즘의 시간 복잡도는 두 개의 리스트를 합병하는 과정에서 레코드를 저장하는 횟수인 2n에 로그를 씌운 nlgn이 됩니다. 따라서, T(n) = 2nlgn으로 나타낼 수 있습니다. 파이썬에서 구현된 합병정렬 알고리..

1. 선형 시간 복잡도를 갖는 중앙값 찾기 알고리즘은 다음과 같이 작동합니다. 배열을 크기가 5인 부분배열로 분할합니다. 각 부분배열의 중앙값을 찾아 새로운 배열에 추가합니다. 위 과정을 반복하여 크기가 5보다 작은 부분배열이 생길 때까지 수행합니다. 새로운 배열에서 중앙값을 재귀적으로 찾습니다. 이 알고리즘의 시간 복잡도는 각 부분배열에서 중앙값을 찾는데 O(1)의 시간이 소요되므로, 분할된 부분배열의 개수에 비례하는 O(n)의 시간이 소요됩니다. 따라서 전체적인 시간 복잡도는 O(n)입니다. 파이썬으로 구현한 코드는 다음과 같습니다. def linear_median_find(arr): n = len(arr) if n == 1: return arr[0] medians = [] i = 0 while i ..

1. n개의 노드를 가진 어떤 트리라도 가장 작은 높이는 Ω(lg n) = -1 + lg(n+1)임을 증명하시오. 우선, 높이가 h인 이진 트리(binary tree)의 최대 노드 수는 2^(h+1) - 1이 됩니다. 이를 반대로 바꾸면, 높이가 h인 이진 트리는 적어도 (2^h - 1)개의 노드를 가진다는 것을 알 수 있습니다. 이제 n개의 노드를 가진 트리 T를 생각해보겠습니다. 이 트리의 높이를 h라고 가정하면, T는 높이가 h인 이진 트리보다는 많은 노드를 가지고 있을 것입니다. 따라서 다음과 같은 부등식이 성립합니다. n > 2^h - 1 이 부등식을 해결하면 다음과 같습니다. n + 1 > 2^h lg(n + 1) > h 즉, 트리 T의 높이는 lg(n + 1)보다 작습니다. 따라서 모든 n개..

34번 문제 해설 : 해당 문제를 파이썬 코드로 나타내면 아랴와 같습니다. for i in range(1, n+1, 2): for j in range(1, n+1, 2): # some constant number of operations 여기서 range(1, n+1, 2)는 1부터 n까지 2씩 증가하는 값을 가지는 리스트를 생성합니다. 즉, 외부 루프는 i가 2씩 증가하면서 최대 log₂n번 반복됩니다. 내부 루프도 마찬가지로 j가 2씩 증가하면서 최대 log₂n번 반복됩니다. 따라서, 이중루프의 시간복잡도 T(n)은 O(log₂n) 입니다. 코드에서 상수 시간으로 수행되는 연산이 있을 수 있으나, 시간 복잡도에서는 무시됩니다. 2. 생일 문제에 대한 각각의 정렬 1) 버블 정렬(Bubble Sort)..

⊙ 알고리즘 생일 문제를 파이썬을 통해 풀어보도록 하겠습니다 ! 풀기 위한 과정을 먼저 쉽게 설명해보자면 아래와 같습니다. 생일 데이터 파일을 다운로드하고 파이썬으로 읽습니다. 이를 위해 Pandas 라이브러리를 사용할 수 있습니다. 같은 생일을 가진 학생 쌍을 찾습니다. 이를 위해 생일 정보를 사용하여 데이터를 그룹화하고 각 그룹의 크기를 계산할 수 있습니다. 그런 다음, 그룹 크기가 2 이상인 그룹을 찾아 해당 그룹 내의 학생 쌍을 확인할 수 있습니다. k 명의 학생이 있는 반에서 적어도 두 명의 학생이 같은 생일을 가질 확률을 계산하는 코드를 작성합니다. 이를 위해 이항분포 확률을 계산할 수 있는 함수를 만들거나, Monte Carlo 시뮬레이션 방법을 사용할 수 있습니다. 만약 교실에 100명의 ..