분류 전체보기445 Solving Skill ] 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍(DP) "한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘" ✔ 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법. ✔ 코테에서는 간단한 형태로 출제됩니다. ✔ 다음 조건을 만족할 때 사용이 가능합니다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 🤡 퀵 정렬의 분할 정복과의 차이점 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있습니다. 퀵 정렬의 pivot 원소가 자리를 잡으면 기준 원소의 위치는 더 이상 바뀌지 않습니다. 🌈 2가지 방식 - Bottom up (상향식) : 반복문 이용 & 전형적인 DP 방식(성능이 좋을 때가 多) - Top down (하향식) (= 메.. 2021. 3. 16. 이진탐색 ] 🔁유형 2 - 떡볶이 떡 만들기 **** 보호되어 있는 글 입니다. 2021. 3. 10. 이진탐색 ] 유형 1 - 부품 찾기 (* 계수 정렬 or 이진 탐색 적용) 보호되어 있는 글 입니다. 2021. 3. 10. Solving Skill ] 이진 탐색 이진 탐색(Binary Search) "탐색의 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘" * 탐색 범위가 큰 상황에서 탐색을 해야 할 때 사용하는 것이 좋다. 더보기 ✔ 순차 탐색 (혹은 선형 검색 알고리즘) 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 알고리즘 - 시간 복잡도 평균 : Θ(n) 최악 : Θ(n) - 예시( C언어 ) int sequentialSearch(int array[], int n, int m, int value) { // Starts from n to m int i; for (i = n; i value) return BinarySearch(v, value, low, middle - 1); else if (v[middle] < value) retu.. 2021. 3. 10. 이전 1 ··· 15 16 17 18 19 20 21 ··· 112 다음
