Algorithm/개념 (12) 썸네일형 리스트형 [Algorithm] Depth-first-search (깊이 우선 탐색) 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 출처 : 위키백과 https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89 깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를.. [Algorithm] 동적 계획법 (Dynamic Programming) 동적 계획법이란? - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. - 각 하위 문제를 해결 & 계산한 뒤 저장한다. - 후에 같은 문제가 나왔을 때 계산하지 않고 저장한 값을 사용한다. - 대표적인 예로 피보나치 수열을 구할 때 사용한다. 예) 피보나치 수열 - 첫째 및 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 피보나치 수열을 구하는 함수를 fib()라고 정의하고, 피보나치의 다섯번째 항을 구한다고 하면, 계산은 다음과 같다. 값이 계속해서 중복되어 계산되는 것을 볼 수 있다. 하위 값을 계산하면서 미리 저장해놓으면 fib(5)는 앞의 두 값만 더하면 구할 수 있다. [Algorithm] 정렬 - 계수 정렬 (Counting Sort) 계수 정렬(Counting Sort)이란? - 데이터 값을 직접 비교하지 않고, 단순하게 개수를 세어 기록하고 정렬하는 방식이다. - 값 비교가 일어나지 않기 때문에 속도가 매우 빠르다. - 하지만 개수를 저장하는 배열, 정렬할 배열을 위한 추가 공간이 필요하다. - 또한 숫자가 매우 큰 경우에는 속도가 현저히 느려질 수 있다. 작동 방식 1) 데이터 중 제일 큰 수 + 1의 크기로 카운트 배열을 만든다. (아래 예시에서는 4 = 크기가 5인 배열 할당) 2) 카운트 배열에 각 숫자가 몇 번 나타나는지 개수를 세어 해당 인덱스에 저장한다. (숫자 2는 두 번 나타나므로, 카운트 배열 인덱스 2에 2를 저장) 3) 누적합을 만든다. (이 전 숫자를 더한다.) 누적합이 의미하는 것은 정렬되는 위치이다. 0의.. [Algorithm] 정렬 - 힙 정렬 (Heap Sort) 힙 정렬(Heap Sort)이란? - 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 작동 방식 [초기 배열] 1) 배열 값 순서대로 부모노드 - 왼쪽 자식 - 오른쪽 자식 순서대로 완전 이진트리를 구성한다. 2) 최대 힙이 되도록 힙을 구성한다. - 자식 노드를 비교하여 더 큰 값을 찾는다. - 부모노드보다 큰 지 비교한 후, 부모노드보다 크면 값을 교환한다. - 루트까지 반복한다. 3) 루트와 마지막 단말 노드(자식이 없는 노드) 값을 교체한 후 노드를 제거한다. 4) 변경된 트리를 다시 최대 힙이 되도록 재구성한다. (2~3 반복) 2~3번 작업을 반복하게 되면, 최대 힙이 되도록 재구성할 때마다 루트에 최댓값이 오게 된다. 4번 작업을 통해 가장 큰 값이 배열의 가장 오른쪽 끝 인덱.. [Algorithm] 정렬 - 빠른 정렬 (Quick Sort) 빠른 정렬(Quick Sort)이란? - 피벗을 하나 정한 후 피벗을 기준으로 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬하는 방식이다. - 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. - 분할 정복 알고리즘의 하나이다. - 불안정 정렬에 속한다. * 안정 / 불안정 정렬 동일한 값에 대해 기존의 순서가 유지되는지 여부에 따라 안정 / 불안정 정렬로 구분된다. 작동 방식 1) 피벗을 정한다. 2) 데이터의 양쪽 끝 값과 피벗을 비교한다. 3) 왼쪽 값이 피벗보다 크고, 오른쪽 값이 피벗보다 작으면 두 값을 서로 교체한다. 4) 만약 왼쪽 값이 피벗보다 작거나, 오른쪽 값이 피벗보다 크면 교체하지 않는다. 5) 한차례 비교하게 되면, 피벗을 기준으로 피벗보다 작은 값들은 피벗 .. [Algorithm] 정렬 - 합병 정렬 (Merge Sort) 합병 정렬(Merge Sort)이란? - 작은 조각까지 나눠, 조각을 병합하면서 정렬하는 방식이다. - 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속한다. - 분할 정복 알고리즘의 하나이다. 작동 방식 1) 리스트를 절반으로 계속해서 나눈다. (분할) 2) 가장 작은 단위로 나눠지면, 나눠진 두 조각의 값들을 비교한다. 3) 두 리스트를 비교하면서 하나의 정렬된 리스트에 값을 정렬한다. (합병) 소스코드 #include using namespace std; int* sorted; void mergeSort(int* arr, int left, int right); void merge(int* arr, int left, int right); int main() { int N; cin >> N; s.. [Algorithm] 정렬 - 선택 정렬 (Selection Sort) 선택 정렬(Selection Sort)이란? 가장 작은 값을 찾아 앞으로 차례로 옮기는 방식이다. 예) 1) 배열의 첫번째 값을 min값으로 설정한다. 2) 두번째 값부터 마지막 값까지 비교하여, min보다 작은 값이면 그 값을 min값으로 설정한다. 3) min값을 가장 첫번째 값과 교체한다. 4) 배열의 두번째 값을 min값으로 설정한다. 5) 세번째 값부터 마지막 값까지 비교하여, min보다 작은 값이면 그 값을 min값으로 설정한다. 6) 두번째 값과 min값을 교체한다. 이 작업을 반복하게 되면 작은 값부터 차례로 정렬이 된다. 소스코드 #include using namespace std; void selectionSort(int* arr, int len); int main() { int N; .. [Algorithm] 정렬 - 거품 정렬 (Bubble Sort) 거품 정렬(Bubble Sort)이란? 앞에서부터 차례로 두 개씩 비교하여, 작은 값을 앞으로 정렬하는 방식이다. 예) 1) 맨 앞부터, 두 개의 값인 arr[0]과 arr[1]을 비교한다. 2) arr[0]값이 더 크므로 두 값을 교체한다. (작은 값을 앞으로) 3) 그 다음 두 개 값인 arr[1]과 arr[2]를 비교한다. arr[2]값이 더 크므로 교체하지 않고 넘어간다. 4) 그 다음 두 개 값인 arr[2]와 arr[3]을 비교한다. arr[3]값이 더 크므로 교체하지 않고 넘어간다. 5) 그 다음 두 개 값인 arr[3]과 arr[4]를 비교한다. 6) arr[4]값이 더 크므로 두 값을 교체한다. 이렇게 1회전을 돌면 제일 큰 값이 맨 뒤에 오게 된다. 따라서 2회전을 돌 때에는, 제일 마.. 이전 1 2 다음
