[Algorithm] 알고리즘의 기초 개념과 대표적인 설계 기법 정리

안녕하세요  .ᐟ 

알고리즘 기초 개념과 대표적인 설계 기법을 알아보겠습니다.

 

1. 알고리즘의 기본 개념

알고리즘이란 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것을 말합니다.

 

알고리즘의 성립 조건

• 입출력: 0개 이상의 외부 입력과 1개 이상의 출력이 있어야 함.
• 명확성: 각 명령은 모호하지 않고 단순 명확해야 함.
• 유한성: 한정된 단계를 거친 후에는 반드시 종료되어야 함.
• 유효성: 모든 명령은 컴퓨터에서 수행 가능해야 함.
• 효율성: 실용적인 관점에서 알고리즘은 효율적이어야 함.

주요 문제 예시

• 오일러 경로(Eulerian Path): 그래프의 모든 간선을 오직 한 번씩만 지나는 경로입니다.
  규칙 : 모든 정점의 차수가 홀수인 정점이 0개 또는 2개일 때 존재하며, 2개일 경우 반드시 홀수점에서 시작해야 합니다.
• 데이크스트라(Dijkstra): 최단 경로를 찾는 알고리즘입니다.

 

 

 

2. 탐색 알고리즘 (Search)

순차 탐색 vs 이진 탐색

• 순차 탐색: 데이터를 처음부터 끝까지 차례대로 확인합니다.
• 이진 탐색(Binary Search): 정렬된 데이터에서 중앙값을 기준으로 탐색 범위를 절반씩 줄여나가는 방식입니다.

 

[Java] 이진 탐색 구현 예시

public static int BinarySearch(int[] A, int key, int left, int right) {
    if (left > right) return -1; // 찾지 못함

    int mid = (left + right) / 2;
    if (A[mid] == key) {
        return mid; // 탐색 성공
    } else if (key < A[mid]) {
        return BinarySearch(A, key, left, mid - 1); // 왼쪽 부분 탐색
    } else {
        return BinarySearch(A, key, mid + 1, right); // 오른쪽 부분 탐색
    }
}

 

 

3. 알고리즘 설계 기법

1) 욕심쟁이 방법 (Greedy Method)

탐욕 알고리즘 / 그리디 알고리즘 이라고 부르기도 합니다.

각 단계에서 전후 상관없이 현재 상황에서 '가장 최선'이라고 여겨지는 해(국부적 최적해)를 선택해 나가는 전략입니다.

• 동전 거스름돈 문제: 액면가가 큰 동전부터 최대한 많이 선택합니다.
  다만, 동전의 종류가 일반적인 경우에는 최적해를 보장하지 못할 수도 있습니다.
• 배낭 문제 (Fractional Knapsack): 물체를 쪼갤 수 있는 경우, '단위 무게당 이익'이 큰 순서대로 넣으면 최적해를 구할 수 있습니다.
  • 주의: 물체를 쪼갤 수 없는 0/1 배낭 문제는 욕심쟁이 방법으로 해결이 불가능합니다.

 

2) 분할정복 방법 (Divide-and-Conquer)

큰 문제를 더 이상 나눌 수 없을 때까지 작은 문제로 순환적으로 분할한 뒤, 각각 해결하고 결합하는 하향식(Top-down) 접근 방식입니다.

• 특징: 분할된 작은 문제는 원래 문제와 동일하며 서로 독립적입니다.
• 단계: 분할 → 정복 → 결합
• 대표 적용: 퀵 정렬, 합병 정렬, 이진 탐색 등

 

3) 동적 프로그래밍 방법 (Dynamic Programming)

가장 작은 부분 문제부터 해를 구해 저장(Memoization)해두고, 이를 이용해 큰 문제의 해를 구하는 상향식(Bottom-up) 접근 방식입니다.

• 특징: 작은 문제들이 서로 독립적일 필요가 없으며, 이미 계산된 해를 재사용하여 효율성을 높입니다.

 

 

 

다음 글에서는 시간복잡도, 점근성능 표기법, 순환 알고리즘과 점화식에 대해 작성해보겠습니다.

감사합니다.