[Section2] 자료구조/알고리즘 (알고리즘)

dohyoungK·2023년 5월 24일

자료구조/알고리즘 (알고리즘)

의사 코드(pseudocode)

: 프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 작성하는 것
- 의사 코드의 장점
1. 시간 단축 : 문제가 복잡해질수록 생각을 먼저 의사 코드로 작성해 놓는 것이 시간 낭비가 없다.
2. 디버깅에 용이 : 오류가 발생 시, 디버깅을 할 때 일상 언어로 작성된 의사 코드를 확인하면 로직에만 신경을 쓸 수 있기 때문에 문제 원인 파악이 쉽다.
3. 프로그래밍 언어에 익숙치 않은 사람과도 소통 가능하다.
시간 복잡도(Time Complexity)

: 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는지를 나타낸 것
- 시간 복잡도 표기법
1. Big-O(빅-오) : 시간 복잡도를 최악의 경우를 고려해 나타낸 것
2. Big-Ω(빅-오메가) : 시간 복잡도를 최선의 경우를 고려해 나타낸 것
3. Big-θ(빅-세타) : 시간 복잡도를 평균의 경우를 고려해 나타낸 것
- Big-O(빅-오) 표기법의 종류
  : 최악의 경우도 고려해 대비하는 것이 바람직하므로 다른 표기법보다 Big-O를 많이 사용한다.
1. O(1) : 입력값이 증가하더라도 시간이 늘어나지 않는다.
```
public int O_1_algorithm(int[] arr, int index) {
   return arr[idx];
}
```
2. O(n) : 입력값이 증가함에 따라 시간도 같은 비율로 증가하는 것
```
public void O_n_algorithm(int n) {
   for(int i = 0; i < n; i++) {
      ...
   }
}
```
3. O(log n) : 입력값이 증가함에 따라 시간이 log만큼 짧아지는 것
4. O(n^2) : 입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가하는 것
```
public void O_quadratic_algorithm(int n) {
   for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
         ...
      }
   }
}
```
5. O(2^n) : 입력값이 증가함에 따라 시간이 2의 n의 제곱수 비율로 증가하는 것
```
public int fibonacci(int n) {
   if(n <= 1) return 1;
   return fibonacci(n - 1) + fibonacci(n - 2);
}
```
탐욕 알고리즘(Greedy Algorithm)

: 선택의 순간마다 그 때의 최적의 상황을 선택해 최종 해답에 도달하는 알고리즘
- 탐욕 알고리즘의 단계
1. 선택 절차(Selection procedure): 현재 상태의 최적 해를 선택한다.
2. 적절성 검사(Feasibility Check): 선택한 해가 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 다시 선택 절차로 돌아간다.
완전 탐색 알고리즘(Bruth Force Algorithm)

: 모든 가능성을 시도해 문제를 해결하는 방법. 하지만 문제의 복잡도를 고려하지 않으므로 데이터의 범위가 커질수록 비효율적이다.
- 순차 검색 알고리즘(Sequential Search)
  : 배열 안에 특정 요소가 있는지 처음부터 끝까지 차례로 검색
- 문자열 매칭 알고리즘(Bruth Force String Matching)
  : 길이가 n인 전체 문자열이 길이가 m인 문자열 패턴을 포함하는지 검색
- 선택 정렬 알고리즘(Selection Sort)
  : 전체 배열을 검색하여 첫 요소부터 차례로 현재 요소를 나머지 요소 중 최소값이나 최대값과 비교해 교환하며 정렬
이진 탐색 알고리즘(Binary Search Algorithm)

: 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘
- 이진 탐색 알고리즘의 단계
1. 정렬된 배열의 가장 중간 인덱스를 지정한다.
2. 찾고자 하는 값이 중간 인덱스의 값이라면 탐색 종료한다.
3. 아니라면 찾고자 하는 값이 중간 인덱스의 값보다 큰 지, 작은 지 확인한다.
4. 값이 있는 부분에서 1번 단계부터 반복한다.