본문 바로가기

OLD_알고리즘224

자료구조 ] Heap 자료구조 Heap "무엇인가를 차곡차곡 쌓아올린 더미" "우선 순위 queue를 구현하는 자료구조" "이진 트리이되 완전 이진 트리" "모든 노드의 값은 자식 노드의 값 =< 부모 노드의 값" 우선 순위 queue STL #include #include #include using namespace std; template void print_queue(T q) { // NB: pass by value so the print uses a copy while(!q.empty()) { cout 2021. 3. 22.
Solving Skill ] 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍(DP) "한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘" ✔ 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법. ✔ 코테에서는 간단한 형태로 출제됩니다. ✔ 다음 조건을 만족할 때 사용이 가능합니다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 🤡 퀵 정렬의 분할 정복과의 차이점 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있습니다. 퀵 정렬의 pivot 원소가 자리를 잡으면 기준 원소의 위치는 더 이상 바뀌지 않습니다. 🌈 2가지 방식 - Bottom up (상향식) : 반복문 이용 & 전형적인 DP 방식(성능이 좋을 때가 多) - Top down (하향식) (= 메.. 2021. 3. 16.
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.
Solving Skill ] 정렬 정렬(Sorting) "데이터를 특정 기준에 따라 순서대로 나열하는 알고리즘" V 이진 탐색의 전처리 과정이기도 합니다. V 다양한 정렬 알고리즘의 시간 복잡도 🍎 선택 정렬 "가장 작은 것을 선택"하는 알고리즘 ⏱ 시간 복잡도 : Θ(n^2) V 정렬 방법 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. V 예시 테이블 최솟값 0 [9,1,6,8,4,3,2,0] 0 1 [0,1,6,8,4,3,2,9] 1 2 [0,1,6,8,4,3,2,9] 2 3 [0,1,2,8,4,3,6,9] 3 4 [0,1,2,3,4,8,6,9] 4 5 [0,1,2,3,4,8,6,9] 6 6 [0,1,2,3,4,6,8,9] .. 2021. 3. 10.

티스토리툴바