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

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명의 ..

우선 순위큐 란? 우선순위 큐는 말 그대로 들어간 순서와 상관없이 우선순위가 높은 것을 먼저 뽑아내기 위해 만들어진 자료구조이며, 힙(Heap)이라고도 한다. 만약 둘의 차이를 따져보자면, 우선 순위 큐는 우선 순위가 높은 데이커가 먼저 나오는 자료구조 형태라고 할 수 있고, 힙은 완전 이진 트리 형태이며 자식 노드의 값보다 부모노드의 값이 크거나 같은 자료구조의 형태이다. 2. 우선 순위 큐 (힙의 특징) : 완전 이진 트리 구조의 형태를 갖는다. 일반적으로 배열로 구현한다. 일종의 반 정렬 상태를 유지한다. (느슨한 정렬 상태) 모든 노드에 저장된 값( 우선 순위 )들은 자식 노드의 것보다 우선 순위가 크거나 같다. 직접 연결된 자식과 부모 노드 간의 크기만 비교하면 된다. 힙으로 우선 순위 큐를 구..

1. 지속 불가능한 사용과 전세계 인구 증가로 많은 문제들이 야기되고 있다. 지금 현재에도 전 세계적으로, 1분 마다 100만개의 플라스틱으로 만들어진 음료병이 구매되고 있으며, 매년 5조개의 일회용 봉지가 버려지고 있다. 이러한 무분별한 소비는 많은 기후 변화를 촉진하고, 아름다운 자연을 파괴하며, 지구 오염수준을 높이는데 기여하는 상황이다. 또한, 우리 사회는 현재, 한 경제가 소비 수요를 충족하기 위해 직접 사용하는 1인당 자원 소비량은 2000년 부터 2017년도까지 무려 8.7톤애서 12.2톤 가량으로 40% 이상 증가했다. 이렇게 빠르게 증가하는 천연자원 소비율은 우리의 자원을 더 빠르게 고갈시킬 것이다. 그러므로, 우리는 탄소 배출의 감소와 자원효율성 향상 및 지속 가능한 생활 방식을 적극적..