개발일기🌷

1. 그래프 탐색 알고리즘 : DFS / BFS
- 탐색(Search)은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- DFS와 BFS는 대표적인 그래프 탐색 알고리즘 

2. DFS(Depth-First Search, 깊이우선 탐색)
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- Stack 자료구조(후입선출방식) 혹은 재귀함수를 이용

2-1. DFS 동작과정
① 탐색 시작 노드를 스택에 삽입하고 방문 처리
② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
③ 더 이상 위 과정을 수행할 수 없을 때까지 반복

3. BFS(너비 우선 탐색)
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- Queue자료구조(선입선출방식)를 이용

3-1. BFS 동작과정
① 탐색 시작 노드를 큐에 삽입하고 방문 처리
② 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
③ 더 이상 위 과정을 수행할 수 없을 때까지 반복

1. 탐욕 알고리즘(greedy algorithm)

• 매순간 최적인 답을 선택하는 과정을 반복해 결과를 도출
  → 정당성 분석, 최적의 해를 구할 수 있는지 검토하는 것이 중요
• 만족하는 적합한 해를 찾는 방법
  → 최적의 해를 찾는 방법은 아님
• 동적 프로그래밍 중 지나치게 많은 일을 한다는 것에 착안해 고안된 알고리즘

2. 탐욕 알고리즘의 한계

최적의 해에 가까운 값을 구하는 방법으로 근사치 추정에 활용한다.

예를들어 '시작' 노드에서 시작해서 가장 작은 값을 찾아 leaf node 까지 가는 경로를 찾을 때

• Greedy 알고리즘 적용시 시작 -> 7 -> 12 를 선택하게 되므로 7 + 12 = 19 가 됨
• 하지만 실제 가장 작은 값은 시작 -> 10 -> 5 이며, 10 + 5 = 15 가 답

1. 순열 Permutation

• 길이가 n개인 배열에서 r개의 요소를 차례로 뽑아 새로운 배열을 만들었을 때 가능한 모든 배열(중복제외)
  → 순열, 중복 순열, 조합, 중복조합 모두 n개에서 r개를 뽑는다는 점에서 동일
• 순열의 정의에서는 정렬.  순서가 있다는 것이 특징

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r){
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, out, visited, depth+1, r);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], new boolean[arr.length], 0, r);
    }
}

→ 결과 :  1 2 / 1 3 / 2 1 / 2 3 / 3 1 / 3 2

2. 중복 순열

• 서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수
• 순서가 있다는 점에서 순열과 동일. 같은 원소를 중복해서 뽑을 수 있다는 점에서 차이
  → 순열 코드에서 중복방지를 위해 사용했던 visited 부분을 제거하면 된다.

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, int depth, int r){
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=0; i<arr.length; i++){
            out[depth] = arr[i];
            permutation(arr, out, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], 0, r);
    }
}

→ 결과 :  1 1 / 1 2 / 1 3 /  2 1 / 2 2 / 2 3 / 3 1 / 3 2 / 3 3

3. 조합 Combination

• 서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수(중복제외)
  →[1, 2] 와 [2, 1]을 같은 것으로 취급 ▷ 이 경우 [1, 2]만 카운팅
• 순서 상관이 없고, 중복도 없기 때문에 선택된 원소를 따로 저장하지 않고, 
  원소들과 visited만 이용하여 방문한 원소들을 순서대로 확인하면 곧 선택된 조합

public class AlgorithmStudy {
    public static void combination(int[] arr, boolean[] visited, int start, int depth, int r){
        if(depth == r){
            for(int i=0; i<arr.length; i++){
                if(visited[i]) System.out.print(arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(arr, visited, i+1, depth+1, r);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new boolean[arr.length], 0, 0, r);
    }
}

→ 결과 : 1 2 / 1 3 / 2 3

4. 중복 조합

• 서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수
• 순서 없이 뽑는 조합과 동일하지만, 중복이 가능하다는 점에서 차이(즉, 이미 뽑은 것을 또 뽑을 수 있음)
  → 조합 코드에서 중복방지를 위해사용했던 visited 부분을 제거하면 된다.
  → 중복이 가능하므로 선택한 원소를 저장하는 배열 필요

public class AlgorithmStudy {
    public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int num : out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            out[depth] = arr[i];
            combination(arr, out, i, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new int[r], 0, 0, r);
    }
}

결과 → 1 1 / 1 2 / 1 3 / 2 2 / 2 3 / 3 3

1. 투포인터(Two Pointers)

• 정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 
  타겟 값과 같을 때까지 포인터를 조작하는 기법이다.
  → 보통 l(left), r(right) 또는 s(start), e(end) 같은 식으로 포인터의 이름을 붙임.
• 정렬되어있는 두 리스트의 합집합에도 사용
• 합병정렬의 counquer 영역의 기초가 되기도 함
• 시간 단축

1-1. 포인터 방식

• 맨 처음 두 포인터는 0에서 시작, start <= end 를 만족해야함.
• 부분합 배열의 합 < 구해야하는 값
  → end를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 증가시킴
• 부분합 배열의 합 >= 구해야하는 값
  → start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 감소시킴
• 위 과정을 start 인텍스가 (리스트 크기-1)이 될때까지 반복

2. 투포인터 예제 및 풀이(백준 2003번 : 수들의 합2)

public class Main {
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열 
        int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다.
        
        int count = twoPointers(arr, m);
    }
    
    private static int twoPointers(int[] arr, int m) {
        int sum = 0, count = 0;
        int left = 0, right = 0;
        
        while (true) {
            if (sum > m) { // 1. left를 우측으로 옮기는 경우 
                sum -= arr[left++];
            } else if (right == arr.length - 1) { 
			// right를 우측으로 옮기기 전에 배열의 끝을 가리키는지 확인한다.
                break;
            } else { // 2. right를 우측으로 옮기는 경우 
                sum += arr[right++];
            }
            
            if (sum == m) count++;
        }
        
        return count;
    }
}

1. 퀵정렬(Quick Sort) 알고리즘

• 분할 정복 알고리즘을 사용, 일정하지 않은 형태로 분할. 수행속도 빠름
  → 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 피봇(pivot)이라 부르는 배열 원소를 기준으로 피봇보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 위치하도록 분할.
  이 과정을 통해 분할된 왼쪽 배열과 오른쪽 배열에도 동일한 과정을 수행. 이를 반복하면 정렬되는 방식.
  → 주의 : 피봇은 분할된 왼편이나 오른편에 포함되지 않음.

1-1. 퀵정렬의 피봇 선정방법

• ① 랜덤하게 선정하는 방법
• ② 3개의 숫자의 중앙 값으로 선정하는 방법
  → 가장 왼쪽 숫자 / 중간숫자 / 가장 오른쪽숫자 중에서 중앙값으로 피봇을 정함
• ③ Median-of-Medians
  → 배열을 3등분 후, 각 부분에서 가장 왼쪽 숫자 / 중간 숫자 / 가장 오른쪽 숫자 중에서 중앙값을 찾은 후,
       세 중앙값들 중에서 중앙값으로 피봇을 정함

2. 퀵정렬 알고리즘의 구현

# include <stdio.h>
# define LEN 7
 
void quickSort(int arr[], int L, int R) {
      int left = L, right = R;
      int pivot = arr[(L + R) / 2];    // pivot 설정 (가운데) 
      int temp;
      do
      {
        while (arr[left] < pivot)    // left가 pivot보다 큰 값을 만나거나 pivot을 만날 때까지 
            left++;
        while (arr[right] > pivot)    // right가 pivot보다 작은 값을 만나거나 pivot을 만날 때까지 
            right--;
        if (left<= right)    // left가 right보다 왼쪽에 있다면 교환 
        {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            /*left 오른쪽으로 한칸, right 왼쪽으로 한칸 이동*/
            left++;
            right--;
        }
      } while (left<= right);    // left가 right 보다 오른쪽에 있을 때까지 반복 
 
    /* recursion */
    if (L < right)
        quickSort(arr, L, right);    // 왼쪽 배열 재귀적으로 반복 
 
    if (left < R)
        quickSort(arr, left, R);    // 오른쪽 배열 재귀적으로 반복 
}
 
int main(){
  int i;
  int arr[LEN] = {5,1,6,3,4,2,7};
  printf("정렬 전 : ");
  for(i=0; i<LEN; i++){
    printf("%d ", arr[i]);
  }
  printf("\n");
    
  quickSort(arr, 0, LEN-1);
  
  printf("정렬 후 : ");
  for(i=0; i<LEN; i++){
    printf("%d ", arr[i]);
  }
  
  return 0; 
}

3. 퀵정렬 알고리즘의 특징

3-1. 장점

• 커다란 크기의 입력에 대해서 가장 좋은 성능
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음

3-2. 단점

• 불안정 정렬이다.
• 정렬된 배열에 대해서는 퀵정렬의 불균형 분할에 의해 수행시간이 오히려 더 많이 걸림