컴퓨터로 문제를 해결하기 위한 알고리즘

## 알고리즘 - Computer Science 는 곧 컴퓨터로 문제를 해결하기 위한 알고리즘을 공부하는 것과 같음 - 유한한 시간 내에 유한한 저장 공간, 데이터를 가지고 문제를 푸는 절차 - 명령은 **모호하지 않고(unambiguous), (컴퓨터에서) 실행 가능해야 함(feasible)** - 분석, 구체화 → 알고리즘 짜기 → 코드로 구현 → 유지보수 ## 반복문 - **Count-Controlled Loops** - 특정한 횟수만큼 반복하는 반복문 (for) - 시작하는 값으로 control 변수 초기화 - control 변수가 미리 정한 횟수와 같은지 - 아니라면 control 변수 증가 (보통 1 증가) - **Event-Cotrolled Loops** - 반복문 body 내에서 발생하는 이벤트에 의해 반복 횟수가 결정되는 반복문 (while) - 이벤트 초기화 - 이벤트 조건 확인 - 이벤트 업데이트 #### 제곱근 구하는 알고리즘 ![[square_root_pseuo_code.png|center|600]] ![[square_root_algorithm.png|center|600]] ## 배열과 구조체 - 배열(Array) - 같은 데이터 타입의**(homogenenous)** 값을 가지는 집합 - 인덱스를 통해 접근, 인덱스는 0부터 시작함 - 구조체(Records) - 다른 데이터 타입의**(heterogeneous)** 값을 가지는 집합 - 이름을 통해 접근 - 서로 관련된 데이터들을 모아서 관리하는데 유용한 자료구조 ## Searching Algorithms - Sequntial Search - 순차적으로 하나하나 다 비교해보기 - O(n) - **Binary Search** - (아이템들이 정렬되어 있는 경우) **==divide and conquer==** 를 이용함 - 중간값 K를 고른 후 내가 찾고자 하는 값보다 작으면 0~(K-1) 인덱스까지, 크면 (K+1)~N까지 다시 binary search를 수행함 → 찾고자 하는 값을 찾을 때까지 반복 - O(log n) ![[binary_search_pseudo_code.png|center|250]] ![[binary_search_sample.png|center|600]] ## Sorting Algorithms ✨ 컴퓨팅에서는 미리 정렬을 해두면 검색에 쓰이는 시간을 드라마틱하게 줄일 수 있음 #### Selection Sort(선택 정렬) ![[selection_sort.png|center|500]] - **정렬 방법** 1. 배열 순회 : 현재 순회 중인 위치부터 배열의 끝까지 중에서 가장 작은 값 찾기 2. 교환 : 찾은 최소값과 현재 순회 중인 위치의 원소를 swap 3. 다음 순회로 이동 :다음 위치로 이동하여 순회를 반복 처음 위치부터 N-1번째 위치까지 위의 과정을 반복하면 전체 배열이 정렬된다 - **시간 복잡도** - 선택 정렬의 시간 복잡도는 항상 **O(n^2)** - **특징** - 간단하게 구현 가능하지만, 배열의 크기가 큰 경우 손해 → 실제로는 잘 사용되지 않음 - in-place 정렬 : 별도의 메모리 공간을 사용하지 않음 - **슈도코드** ``` procedure selectionSort(arr: Array) n = length(arr) for i from 0 to n - 1 // 최소값을 찾기 위해 현재 위치부터 배열의 끝까지 검색 minIndex = i for j from i + 1 to n - 1 if arr[j] < arr[minIndex] minIndex = j // 최소값을 현재 위치와 교환 if i ≠ minIndex swap(arr[i], arr[minIndex]) end for end procedure ``` ![[selection_sort_pesudo_code.png]] > **XOR swap** (temp 변수를 두지 않고 swap 하기) ``` def swapWithoutTemp(a, b): a = a ^ b b = a ^ b a = a ^ b return a, b # 사용 예시 x = 5 y = 10 x, y = swapWithoutTemp(x, y) print("x =", x) print("y =", y) ``` #### Bubble Sort ![[bubble_sort.png|center|500]] - **정렬 방법** 1. **배열 순회:** 배열의 첫 번째 원소부터 시작하여 **인접한 두 원소**를 비교하기 2. **비교 및 교환:** 인접한 두 원소를 비교하여 순서가 바뀌어 있으면 교환 큰 값을 뒤로 보내는 방식이므로 오름차순 정렬의 경우에는 큰 값을 뒤로 보내는 것이고, 내림차순 정렬의 경우에는 작은 값을 뒤로 보냄 3. **반복:** 이러한 과정을 전체 배열이 정렬될 때까지 반복 한 번의 순회가 끝나면 가장 큰(또는 작은) 원소가 배열의 마지막으로 이동함 - **시간 복잡도** - 최악 O(n^2) - **특징** - 마찬가지로 배열의 크기가 커질수록 효율이 낮아짐 - **슈도코드** ``` procedure bubbleSort(arr: Array) n = length(arr) for i from 0 to n-1 // 각 순회에서 가장 큰 원소를 배열의 끝으로 이동 for j from 0 to n-i if arr[j] > arr[j+1] // 인접한 원소를 비교하여 순서가 바뀌어 있으면 교환 swap(arr[j], arr[j+1]) end if end for end for end procedure ``` ![[bubble_sort_pesudo_code.png]] #### Insertion Sort ![[insertion_sort.png|center|500]] - **정렬 방법** 1. **배열 순회**: 첫 번째 원소(인덱스 0)는 이미 정렬된 것으로 간주하고 다음 원소부터 시작 해당 원소를 이미 정렬된 부분과 비교 2. **원소 삽입**: 정렬된 부분에서 적절한 위치를 찾아 현재 원소 삽입 3. **반복**: 정렬된 부분은 계속해서 확장되며, 모든 원소가 삽입될 때까지 반복됨 - **시간 복잡도** - 최선의 경우에도 O(n^2) - **특징** - 작은 크기의 데이터나 이미 정렬된 부분이 있는 경우에 성능이 우수함 - in-place 정렬 - **슈도코드** ``` procedure insertionSort(arr: Array) n = length(arr) for i from 1 to n-1 key = arr[i] j = i - 1 while j >= 0 and arr[j] > key // 현재 원소보다 큰 원소들을 오른쪽으로 이동 arr[j + 1] = arr[j] j = j - 1 // 현재 원소를 정렬된 부분 배열에 삽입 arr[j + 1] = key end for end procedure ``` ![[insertion_sort_pseudo_code.png|center|350]] ## Recursive Algorithms **recursion** : 알고리즘이 스스로를 호출함. 일반적으로 현재 문제의 작은 버전으로 스스로를 호출함. - 재귀조건(general case)과 종료조건(base case)이 있어야 함 #### Recursive Factorial - 재귀조건(general case) : N! = N * (N-1)! - 종료조건(base case) : 0! = 1 ![[recursion_factorial_pseudo_code.png|center|500]] #### Recursive Binary Search ![[binary_search_pesudo_code.png|center|350]] ``` function binarySearch(arr: Array, target: Integer, low: Integer, high: Integer): Integer if low <= high mid = (low + high) / 2 // 중간 원소가 찾는 값인 경우 if arr[mid] == target return mid // 중간 원소보다 작으면 왼쪽 부분 배열에서 탐색 if arr[mid] > target return binarySearch(arr, target, low, mid - 1) // 중간 원소보다 크면 오른쪽 부분 배열에서 탐색 return binarySearch(arr, target, mid + 1, high) // 탐색 범위가 더 이상 없을 때 return -1 ``` - 함수의 매개변수로는 배열 `arr`, 찾고자 하는 값 `target`, 탐색 범위의 시작 인덱스 `low`, 그리고 탐색 범위의 끝 인덱스 `high`가 있음 > **Divide and Conquer (분할 정복)** > >알고리즘 설계 패러다임 중 하나로, 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결한 다음, 이 해답을 합쳐서 전체 문제를 해결하는 방법론 >이를 통해 전체적으로 문제를 해결하는 과정을 단순화하고, 재귀적으로 문제를 해결하는 특징을 갖고 있음 #### Merge Sort - **정렬 방법** 1. **분할(Divide):** 주어진 배열을 중간 지점을 기준으로 반으로 나눈다 2. **정복(Conquer):** 나뉜 각 배열에 대해 재귀적으로 합병 정렬을 수행 각 배열은 더 이상 나눌 수 없을 정도로 작아질 때까지 계속 분할하고 정렬한다 3. **합병(Merge):** 정렬된 두 개의 하위 배열을 합병하여 하나의 정렬된 배열을 만든다 이때 두 배열의 요소를 비교하여 작은 값을 새로운 배열에 차례대로 넣음 - **시간 복잡도** - 모든 경우에 대해 O(n log n) - **특징** - 안정적이지만 **추가적인 메모리 공간**이 필요함 ``` #### Quicksort ✨ ![[quicksort.png|center|400]] - **정렬 방법** 1. **피벗 선택:** 배열에서 하나의 원소를 선택하여 피벗으로 지정 피벗의 선택 방법은 다양한데, 보통은 배열의 중간 원소를 선택하거나 무작위로 선택한다 2. **파티션 분할:** 배열을 피벗을 기준으로 두 부분으로 분할 피벗보다 작은 값은 피벗의 왼쪽으로, 큰 값은 오른쪽으로 이동시킨다 3. **재귀적 정렬:** 분할된 두 부분에 대해 각각 재귀적으로 퀵소트를 수행함 이를 반복하면서 각 부분이 정렬됩니다. - **시간 복잡도** - 평균 O(n log2 n), 최악 O(n^2), - **특징** - 각 부분 배열은 이미 정렬되어 있으므로 합병 과정이 필요없음 - in-place sort - 특히 큰 데이터셋에 대해 빠른 정렬을 제공함 - 다만 입력 데이터에 따라 성능이 달라짐 (이미 정렬된 경우나 거의 정렬된 경우 성능이 떨어짐) - **슈도코드** ``` procedure quickSort(arr: Array, low: Integer, high: Integer) if low < high // 배열을 분할하고 pivot의 위치를 찾음 pivotIndex = partition(arr, low, high) // pivot을 기준으로 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬 quickSort(arr, low, pivotIndex - 1) quickSort(arr, pivotIndex + 1, high) procedure partition(arr: Array, low: Integer, high: Integer): Integer // 피벗 선택 (예: 배열의 가운데 원소) pivot = arr[(low + high) / 2] // low와 high를 가운데서 출발하여 교차할 때까지 원소를 찾아 위치 교환 while low <= high while arr[low] < pivot low = low + 1 while arr[high] > pivot high = high - 1 if low <= high swap(arr[low], arr[high]) low = low + 1 high = high - 1 return low ``` ![[quicksort_pseudo_code.png|center|400]] #### 하노이탑 문제 ``` procedure hanoi(n, 출발기둥, 목표기둥, 보조기둥): if n == 1: // 이동할 원반의 개수가 1개일 경우, 직접 이동 수행 이동(출발기둥, 목표기둥) else: // 1. n-1개의 원반을 보조기둥으로 옮김 hanoi(n-1, 출발기둥, 보조기둥, 목표기둥) // 2. 남은 1개의 원반을 목표기둥으로 옮김 이동(출발기둥, 목표기둥) // 3. 보조기둥에 있는 n-1개의 원반을 목표기둥으로 옮김 hanoi(n-1, 보조기둥, 목표기둥, 출발기둥) procedure 이동(출발기둥, 목표기둥): // 실제로 원반을 옮기는 동작을 수행하는 함수 출력("원반을", 출발기둥, "에서", 목표기둥, "으로 이동") ``` 이 함수는 4개의 매개변수를 가진다. - 이동할 원반의 개수 `n` - 출발 기둥 `출발기둥` - 목표 기둥 `목표기둥` - 보조 기둥 `보조기둥` 만약 이동할 원반의 개수가 1개라면 직접 이동을 수행하고, 그렇지 않으면 다음 세 단계를 수행한다. 1. `n-1`개의 원반을 보조 기둥으로 옮김 2. 남은 1개의 원반을 목표 기둥으로 옮김 3. 보조 기둥에 있는 `n-1`개의 원반을 목표 기둥으로 옮김 `이동` 함수는 실제로 원반을 옮기는 동작을 수행한다.