알고리즘

추상적이고 이상적인 절차를 기술한 것

구현에 필요한 세부 사항과 현실적인 고려 사항을 무시

알고리즘은 추상적이고 이상적인 절차를 기술한 것으로, 구현에 필요한 세부사항과 현실적인 고려사항을 무시한다. 알고리즘은 정확하고 명로한 레시피이다.

알고리즘은 결국 멈춰야 함

프로그램

실제 컴퓨터가 과제를 완료하기 위해 수행해야 하는 모든 단계를 구체적으로 서술

하나 이상의 알고리즘이 컴퓨터가 직접 처리할 수 있는 형태로 표현된 것

실직적인 문제도 신경 써야 함(메모리 부족, 제한된 프로세서 속도, 유효하지 않거나 악의적으로 잘못된 입력 데이터, 하드웨어 결함, 네트워크 연결 불량, 인간적인 약점)

실제 컴퓨터가 과제를 완료하기 위해 수행해야 하는 모든 단계를 구체적으로 서술한다. 불충분한 메모리, 제한된 프로세서 속도, 유효하지 않거나 악의적으로 잘못된 입력 데이터, 하드웨어 결함, 네트워크 연결 불량, 인간적인 약점 등의 문제가 포함된다.

알고리즘과 프로그램 사이에는 명확한 차이점이 있다.

알고리즘이란 문제를 해결하기 위한 일련의 정해진 절차를 의미한다. 개념적이고 추상적인 형태로 표현되며, 어떤 언어로도 표현될 수 있다. 알고리즘은 문제를 해결하는 방법을 구체적으로 정의하며, 주어진 입력에 대해 예상 가능한 출력을 제공해야 한다.

프로그램은 이 알고리즘을 특정 프로그래밍 언어로 구현한 것이다. 컴퓨터에 의해 실행될 수 있는 구체적인 코드입니다. 프로그램은 알고리즘을 실제로 동작하게 하는 방법에 초점을 맞추며, 이 과정에서 여러 현실적인 제약 사항을 고려해야 한다. 메모리 용량, 프로세서 속도, 입출력 데이터의 유효성, 하드웨어의 기능, 네트워크 상태 등이 포함된다.

따라서 알고리즘과 프로그램을 비교하면, 알고리즘은 이상적인 요리 레시피라고 볼 수 있다. 이 레시피는 어떤 요리사에게도 전달될 수 있으며, 재료와 조리 방법을 제공합니다. 반면, 프로그램은 이 레시피를 구체적으로 실행하는 요리사라고 할 수 있다. 요리사는 주방의 환경, 재료의 상태, 조리 도구 등의 실제 사항을 고려해야 한다.

완전 탐색은 가능한 모든 경로를 탐색하여 최적의 경로를 찾는 방식이다. 이 방식은 경로의 수가 적을 때는 유용하지만, 경로의 수가 많아질수록 연산 비용이 증가하는 단점이 있다. 그리디 알고리즘은 항상 현재 상황에서 가장 좋은 선택을 하는 방식으로 최적의 해를 찾는 방법이다. 이를 위해 각 도시 간의 거리 정보가 필요하며, 이를 이용하여 현재 위치에서 가장 가까운 도시를 선택해 나가면 된다.

1.알고리즘 '복잡도(complexity)'

복잡도란

• 알고리즘의 성능을 나타내는 척도
• 크게 시간 복잡도, 공간 복잡도로 나눌 수 있다.

1.시간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다.
• 알고리즘을 위해 필요한 연산의 횟수
• 복잡도를 표현하기 위해 빅오 표기법을 사용한다.
• 최악의 경우에 대한 연산 횟수가 가장 중요하다.
• N의 범위에 따라 시간 복잡도를 계산하고 사용할 수 있는 알고리즘을 선택하는 방법도 있다.

※ 빅오 표기법 (O, big-O)

빅오란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.

• 빅오는 점근적 실행 시간을 표기할 때 가장 널리 쓰이는 수학적 표기 방법이여, 여기서 점근적 실행 시간이란 간단하게 N이라는 입력값이 무한대로 커질때의 실행 시간의 추이를 의미한다.
• 따라서 충분히 큰 입력값에서의 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.

빅오 표기법 표현 설명

2.공간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
• 알고리즘을 위해 필요한 메모리의 양

2. P vs NP

1.다항 시간 알고리즘(Polynomial-Time Algorithms)

• 다항 시간(합리적인 시간)안에 풀 수 있는 문제.
• 모든 문제가 다항 시간안에 해결되지 않는다.
  • Ex) 튜링의 "Halting Problem(정지 문제)" : 정지 문제란
  프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라.
  • 1936년 앨런 튜링이 모든 가능한 입력값에 대해 정지 문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다.

2.클래스 P

• 다항 시간내에 해결되는 알고리즘을 가지고 있는 결정(decision) 문제의 클래스
  • 어떤 상수 k에 대해 O(N^K) 시간에 풀 수 있는 문제
• O(P(N)) - 이때 P(N)은 N상의 다항시간
• 항상 올바른 답을 계산하는 방법
• 다항시간내에 해결되지 않으면 비효율적

3.클래스 NP

• '비결정적인 다항시간' 상에 존재(stand)
• 주로 "추측" or "평행선화(parallelize)"방식으로 계산
• 다항 시간에 "확인할 수 있는" 문제로 구성
  • 해의 "후보"가 주어지면 문제 입력 크기에 대한 다항 시간에 그 후보가 올바른 해인지 확인할 수 있음을 의미
• 이 방식의 문제점은 "속도(quickly)"

4.P ⊆ NP (아직 증명X)NP-complete(완비) 문제는 NP에서 가장 어려운 문제이다.대부분의 전문적인 문제는 P or NP-complete 문제이다.NP-complete 문제 : P로 해결 가능하지만 NP로 해결되지 않는 문제(미제문제)

3.여행하는 외판원 문제(Traveling-Salesman-Problem)

1.여행하는 외판원 문제(TSP)

외판원 문제 또는 순회 외판원 문제는 초합 최적화 문제의 일종이다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

• 외판원은 자신이 사는 도시에서 출발해서 어떤 순서로든 다른 도시를 모두 방문하고 나서 다시 출발점으로 돌아와야 한다.
  • 여기서 목표는 각 도시를 정확히 한 번씩(반복 없이) 방문하고,
  • 전체 여행한 거리를 최소로 만드는 것이다.⇒ 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순회를 구하라" 라고 표현할 수 있고, 반드시 시작점으로 돌아와야 한다는 제약 조건을 없애도 계산 복잡도는 변하지 않는다.
• 외판원 순회 알고리즘은 무식하게 풀 수 있다. 무조건 0번 도시에서 출발한다고 가정해도 경로의 길이는 다르지 않다.
• 그러면 남은 도시들을 어떤 순서로 방문할지를 정하기만 하면 된다.
• 남은 n-1개의 도시를 나열하는 방법으로는 (n-1)!가지가 있다.
• 그래서 재귀 호출을 통해 쉽게 외판원 순회 알고리즘을 설계할 수 있다.
• 그러나 보통 n!의 풀이는 사용하지 않는다. 12!만 해도 479,001,600라는 엄청난 수를 지니기 때문이다.

2.외판원 순회 알고리즘을 더 빠르고 효율적으로 구하는 방법은?

• 모든 정점을 한 번씩 방문하는(출발 정점 제외) 최단 순환 경로를 탐색하는데 최적의 효율로 탐색하기 위해서 사용한다.

DP 메모제이션

• (n-1)!의 모든 경로를 조사하지 않고 중복된 경로를 제거하는 dp 메모제이션 기법을 사용하면 된다.
  • 동일한 하위 문제의 반복을 막아줌으로써 더 높은 효율로 연산이 이루어지게 해준다. 중복되는 경로의 조사를 제거해주는 것이다.
• 예를 들어, 피보나치 함수는 dp 메모제이션 기법을 통해 O(2^n)의 복잡도를 O(N)까지 줄여준다. **그렇다고 무조건 dp 메모제이션을 적용하면 각 문제의 성질이 다르기 때문에 O(n)으로 줄어든다는 뜻은 아니다.

비트마스킹

• 비트마스킹을 사용하면 bit연산이기 때문에 다른 자료구조(boolean배열)을 사용하는 것보다 훨씬 빠르게 동작되고 코드도 간결해진다.
• 가장 큰 장점은 N이 16개인 경우 2^16가지의 경우를 16bit로 표현이 가능하다.

⇒ 정리하면 TSP(외판원 순회)는 최단 순환 경로를 탐색해야하는데 1) N! 의 중복 경로를 제거해주는 DP 메모제이션 기법을 사용한다. 그래도 2^N의 모든 경우의 수를 표현해야 하기 때문에 그만큼의 공간복잡도가 필요하다. 2) 메모리 사용량도 줄이고 성능 향상을 위해서 2^N의 경우의 수를 Nbit로 표현할 수 있는 비트마스킹으로 사용한다.

⇒ 올라가야 할 계단의 수를 100 개에서 1개로 줄여주는 설계 방법 이라고 보면 된다.

그렇다면 왜 한 정점만 탐색해도 될까?

• DP 메모제이션 기법으로 엄청나게 시간을 단축 할 수 있는 것은 그만큼 중복되는 경로가 많기 때문이다.
• 이 순회 경로는 싸이클로 n개의 정점 중 어느 정점에서 탐색을 시작해도 결과는 똑같다는 것을 알아야 한다.

• 어차피 최적 경로 싸이클은 어디서 시작해도 똑같이 나오기 때문에 한 정점에서만 탐색해줘도 된다.
• 1번에서 출발 : 1 → 2 → 5 → 3 → 4 → 12번에서 출발 : 2 → 5 → 3 → 4 → 1 → 23번에서 출발 : 3 → 4 → 1 → 2 → 5 → 3

알고리즘 참고 영상 :

[youtube] hungarian dance - sorting algorithms

참고 링크 :

[알고리즘] 복잡도란 무엇인가

빅오 표기법 (O, big-O)

정지 문제

P와 NP

여행하는 외판원 문제(TSP)

선택 정렬

1. 배열에서 최솟값을 찾는다.
2. 최솟값과 정렬되지 않은 맨 앞의 수와 위치를 바꾼다.
3. 최솟값이 이동한 부분은 고정된다.
4. 고정된 부분 이 후부터 배열을 돌면서 1번부터 반복한다.

선택 정렬 구현(Java) 오름차순

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  
            if (arr[j] < arr[indexMin]) {           
                indexMin = j;  // 최솟 값 찾기
            }
        }
        // 최솟값과 제일 앞의 수를 바꿔 주기
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

선택 정렬 시간 복잡도

이중 for문에서 알 수 있듯이 O(N^2) 이다.

첫 번째 값을 찾기 위해 N번 확인 해야 하고, 두 번째 값을 찾기 위해 N+1번 확인하고.. 반복하면

N+ (N-1) + … + 2 + 1 = N(N+1) 이므로 O(N^2)이 된다.

퀵 정렬

배열을 두 부분으로 나누고, 나뉜 부분을 다시 퀵 정렬 하는 대표적인 *분할 정복 방법을 사용한다.

*분할 정복 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

1. 배열에서 하나의 원소를 골라 이 원소를 피벗(pivot)이라고 한다.
2. 피벗 앞에는 피벗보다 작은 원소가, 피벗 뒤에는 피벗보다 큰 원소가 오도록 이동 시킨다.(divide)
3. 피벗 기준으로 좌우 부분에서 재귀적(recursion)으로 1번부터 반복한다.

(책에서는 정렬해야 할 원소들이 알파벳으로 이루어진 이름이라는 것이 명확하여 알파벳 순서대로 반을 나누어 정렬했지만, 숫자를 정렬한다고 생각하면 범위를 알 수 없으니 고정된 기준으로 나눌 순 없고 배열의 원소를 기준으로 잡고 나눠야 한다)

퀵 정렬 구현(Java) 오름차순

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private static void quickSort(int[] arr, int start, int end) {
    // start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
    if (start >= end)
      return;
    
    // 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
    int pivot = start;
    int lo = start + 1;
    int hi = end;
    
    // lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
    // 서로 엇갈리게 될 경우 while문 종료
    while (lo <= hi) {
      while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
        lo++;
      while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
        hi--;
      if (lo > hi)				 // 엇갈리면 피벗과 교체
        swap(arr, hi, pivot);
      else
        swap(arr, lo, hi);			 // 엇갈리지 않으면 lo, hi 값 교체 
      }
	
    // 엇갈렸을 경우, 
    // 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
    quickSort(arr, start, hi - 1);
    quickSort(arr, hi + 1, end);

  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

퀵 정렬 시간 복잡도

O(NlogN) - N이 1이 될 때까지 2로 나누는 횟수.

최악의 경우는 O(N^2)이 된다.

1 2 3 4 5 6

(리스트가 불균형하게 나누어 지는 경우 - 정렬하고자 하는 배열이 정렬이 되어 있는 경우)

정렬이 되어 있으면 가운데 수를 선택하면 좋다! 그니까 무조건 가운데를 피벗으로 선택하는게 이득!

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview (gyoogle.dev)