📌 Memoization vs Recursive Qustion - Momoization과 Recursive을 성능, 가독성 측면에서 비교하고 피보나치 수를 DP와 Recursive을 이용해서 구현하고 테스트하여라. f(1), f(100), f(10000) 📍 What is? Recursive Recursive은 자신을 정의할 때 자신을 다시 참조하는 것을 의미한다. Memoization Memoization은 주어진 입력값에 대한 결과를 저장하여 같은 입력값이 주어졌을 때 다시 계산하는 것을 방지하는 개념니다. 가장 대표적인 예시가 피보나치 수열이다. 피보나치 수열에서 n번째 수를 구하는 함수를 f(n)이라고 해보자. n = 10 일 때 f(10) = f(9) + f(8) 이다. 근데 f(9) = f(8) + f(7) 이다. f(8)이 다시 계산되는 것을 확인할 수 있다. n의 값이 작을 때에는 큰 차이가

📌 Dictionary Problem Question - Direct access table의 문제점과 해당 문제를 해결하는 적절한 hashing 함수를 검색하고 적용하여라 📍 Direct Access Table What is? Direct Address Table이라고도 불리며 key 값을 주소로 사용한다. Problem key를 알고 있으면 O(1) 시간 복잡도로 접근할 수 있지만 최대 index - 1만큼의 자원을 낭비할 가능성이 있다. 예를 들어 key-value 쌍이 10-31, 11-56, 1000-137라고 했을 때 table index는 0 ~ 1000로 1001개의 공간이 있다. 하지만 3개의 데이터만 저장한 상태이기 때문에 998개의

📌 Dijkstra Algorithm 📍 What is? 그래프가 주어졌을 때, 한 정점에서 각각의 정점까지 가는 최단 겨올를 구하는 알고리즘 → 모든 그래프가 가능한 것은 아니다. → 방향이 있어야 하고 간선에 가중치가 있어야 한다. (무방향일 경우에는 양방향으로 표현) 📍 Algorithm Steps 시작점 S를 기준으로 D 배열을 초기화 D 배열에서 가중치가 가중치가 최소인 것을 선택 → X X를 기준으로 Relax 함수 수행 D배열에서 뽑힌 node를 S에 추가 S에 D배열의 모든 node가 들어있으면 종료 Code Report 참고 📌 Hash 📍 What is? Key를 통해 value를 저장하는 방법으로 데이터를 효율적으로 저장하고 탐색하는 방법이다.

📌 Max Heap Question. Max heap 알고리즘을 구현하여라 📍 Implement Code 📌 Dijkstra Algorithm Question. 다익스트라 알고리즘을 구현하고 최적 경로를 출력하고 확인하여라. 음의 가중치가 있는 경우에도 적용되는지 확인하여라 📍 Implement Graph Code Dijkstra Code 📍 Testing Graph 양의 가중치 그래프 Untitled 음의 가중치 그래프 ![Untitled](https

📌 Sortings Question. Insertion / Merge / Quick 정렬을 구현하고, 아래의 데이터를 만들어서 시간 비교 📍 Insertion Sort 📍 Merge Sort 📍 Quick Sort 📍 Performance measure 1,000 미만 1,000 10,000 100,000 1,000,000 10,000,000 📌 Heap Sorting 📍 Heap Sorting & Priority Queue Priority Queue 일반적인 Queue는 FIFO라는 특징을 가집니다. First In First Out으로 먼저 삽입된 원소가 먼저 나오는 것입니다. 여기에 우선순위를 넣은 것이 우선순위 queue 입니다. 우선순위 queue는 삽입된 순서와 상관 없이 우선순위가 높은 원소가 우

📌 Peak Finder 📍 One Dimensional Straightforward Algorithm 순차 탐색 O(N) 순차적으로 탐색하여 이전과 이후의 값이 더 크면 peak이다.하지만 O(n)이기 때문에 효율적인 방법은 아니다. 효율적인 방법 O(lgN) 📌 Sorting 📍 Insertion Sort Time Complexity : O(N²) 📍 Merge Sort Time Complexity : O(NlgN) 📍 Counting Sort Time Complexity : O(N) (제한된 입력값에 한하여 사용) Condition Array의 각 원소는 1~10 이내의 값을 가진 원소이다. Search Sequence 📍 Heap Sort Feature 힙 정렬은 삽입과 동시에 정렬이 효율적으로 이루어져야 한다. 이러