1강. 알고리즘 소개 ( 1 )

1. 컴퓨터 과학에서 알고리즘이란?

• 컴퓨터과학 = 컴퓨터 + 데이터 + 프로그램 + 알고리즘
• 컴퓨터의 한계는 해당 문제와 관련된 알고리즘의 존재 여부와 관련이 있다.
• 컴퓨터 과학은 알고리즘의 과학이라고도 부른다.

2. 알고리즘 강의의 학습 목표

• 잘 알려진 특정 문제를 위한 알고리즘의 설계 및 분석 방법의 습득 →
• 컴퓨터를 이용한 문제 해결 방법에 대해 체계적으로 생각하는 훈련 →
• 주어진 문제에 대한 지적 추상화 능력 및 통찰력 향상

3. 컴퓨터 과학이란?

• 컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문
• 이때 문제 풀이를 위한 절차나 방법을 알고리즘이라고 한다.

4. 알고리즘이란?

• 문제 해결을 위한 레시피
  • 레시피의 단계적인 조리 절차를 따르면 음식을 만들 수 있듯이
  • 알고리즘의 단계적인 처리 절차를 따르면 주어진 답을 구할 수 있음
• 알고리즘의 목표
  • 효율적인 알고리즘

5. 오일러 경로

• 각 정점의 차수가 홀수인 정점이 0개 혹은 2개이어야 한다.
  • 차수는 한 점에서 이어진 선의 개수이다.
• 홀수점이 2개일 경우에는 홀수점에서 시작해야 한다.

6. 알고리즘의 정의

• 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것
• 알고리즘의 조건
  • 입출력 : 0개 이상의 외부 입력과 1개 이상의 출력을 생성
  • 명확성 : 각 명령은 모호하지 않고 단순 명확해야 함
  • 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료함
  • 유효성 : 모든 명령은 컴퓨터에서 수행할 수 있어야 함
  • 즉, 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호하지 않고 단순 명확하며 컴퓨터가 수행할 수 있는 유한 개의 일련의 명령어들을 순서에 따라 구성한 것을 알고리즘이라 함
  • 실용적인 관점에서 알고리즘은 이에 더하여 효율적이어야 한다.

7. 알고리즘 생성 단계

• 설계 → 표현 / 기술 → 정확성 검증 → 효율성 분석
• 단계별 에시
  • 설계 : 상향식 설계, 하향식 설계, 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법
  • 표현 / 기술 : 일성 언어, 순서도, 의사코드, 프로그래밍 언어
  • 정확성 검증 : 수학적 증명
  • 효율성 분석 : 공간 복잡도, 시간 복잡도

8. 알고리즘 설계

• 주어진 문제와 조건 등이 매우 다양
  • 일반적/범용적인 설계 기법은 존재 X
• 대표적인 알고리즘 설계 기법
  • 욕심쟁이 방법 ( Greedy )
  • 분할정복 방법 ( divide-and-conquer )
  • 동적 프로그래밍 방법 ( dynamic programing )

9. 욕심쟁이 방법 ( Greedy )

• 탐욕적 방법, 탐욕 알고리즘, 그리디 알고리즘
• 해를 구하는 일련의 선택 과정에서 전후 단계의 선택과는 상관없이 각 단계마다 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할수 있을 것이라는 희망적인 전략을 취하는 방법
  • 희망적이라는 의미는 각 단계마다 선택한 국부적인 최적해가 항상 전체적인 최적해를 만들지 못할 수도 있다는 의미
• 간단하면서 효율적인 알고리즘을 만들 수 있는 강력한 기법
• 최솟값 / 최댓값을 구하는 최적화 문제에 주로 사용
• 한계
  • 국부적인 최적해들이 전체 최적해를 구성하지 못하는 경우도 있다.
• 대표적인 응용 문제
  • 거스름돈 문제, 배낭 문제
  • 최소 신장 트리 → 크루스칼 알고리즘, 프림 알고리즘
  • 단일 출발점 최단 경로 → 데이크스트라 알고리즘

10. 욕심쟁이 방법 - 거스름돈 문제

• 동전 문제, 거스름돈 문제
• ex ) 가게에서 고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
• 기본적인 해결 방법
  • 거스름돈의 액수를 초과하지 않으면서 동전의 액면가가 단순히 큰 것부터 ’욕심을 부려서’ 최대한 뽑아서 거스름돈을 만듦
    • 가정 → 동전의 종류 : 500원, 100원, 50원, 10원
    • 500원을 될 수 있는한 준다 → 100월 될 수 있는한 준다 → 50원을 될 수 있는한 준다 → 나머지를 10원으로 준다.
  • 그러나 동전의 액면가가 일반적인 경우에는 욕심쟁이 방법으로 해결 불가
    • 일반적인 경우는 120원이나 170원짜리가 생길 경우이다.
    • 500원, 100원, 50원, 10원만 있을 경우 적용 가능

11. 욕심쟁이 방법 - 배낭 문제

• 최대 용량 𝑀인 하나의 배낭, 𝑛개의 물체가 있다고 가정
  • 각 물체 𝑖에는 물체의 무게 𝑤𝑖와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 𝑝𝑖가 부여됨
• 배낭 문제
  • 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체들의 이익의 합이 최대가 되도록 물체를 넣는 방법( 또는 최대 이익 )을 찾는 문제
  • 가정 : 물체를 쪼개서 넣을 수 있음
• 기본 해결 방안
  • 물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 ’욕심을 내어’ 최대한 넣는 과정을 반복
  • 단위 무게당 이익이 가장 큰 물체부터 최대한 넣는 과정을 반복
    • 물체를 통째로 넣을 수 없으면 배낭의 남은 용량에 맞게 물체를 쪼개서 넣음
• 0/1 배낭 문제
  • 가정 : 물체를 쪼갤 수 없는 형태의 배낭 문제
  • 0/1 배낭 문제는 욕심쟁이 방법으로 해결 불가

12. 분할정복 방법

• 순환적으로 문제를 푸는 하향식 접근 방법 ( top-down )
• 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후, 이들의 해를 결합하여 원래 문제의 해를 구하는 방식
• 특징
  • 분할된 작은 문제는 원래 문제와 동일
    • 입력의 크기만 작아짐
  • 분할된 문제는 서로 독립적
    • 순환적인 분할 및 결과의 결합이 가능
• 분할정복 방법은 각 순환 호출마다 세 단계의 작업을 수행
  • 분할
    • 주어진 문제의 입력을 여러 개의 작은 문제로 분할
  • 정복
    • 작은 문제들을 순환적으로 분할
    • 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 충분히 작으면 순환 호출 없이 작은 문제에 대한 해를 구함
  • 결합
    • 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함
• 대표적인 적용 문제
  • 퀵 정렬, 합병 정렬, 이진 탐색

13. 분할정복 방법 - 이진 탐색

• 이진 탐색 알고리즘과 분할정복 방법의 관계
  • 분할
    • 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 절반씩 분할
    • 탐색 키와 가운데 원소가 같으면, 해당 원소의 배열 인덱스를 반환 / 종료
  • 정복
    • 탐색 키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출
  • 결함
    • 부분배열에 대한 탐색 결과가 직접 반환되기에 결합이 불필요

14. 동적 프로그래밍 방법

• 입력의 크기가 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고, 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법 ( bottom-up )
• 각각의 작은 문제는 원래 문제와 동일하고, 입력의 크기만 작음 ( 분할정복 방법과 동일 )
• 작은 문제들은 서로 독립일 필요가 없음 ( 분할정복 방법과 다름 )
• 대표적인 적응 문제
  • 모든 정점 쌍 간의 최단 경로 → 플로이드 알고리즘
  • 행렬의 연쇄적 곱셈 문제, 최장 공통 부분 수열 문제

15. 요약

• 기본 개념
  • 알고리즘
    • 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 순차적으로 나열한 것
  • 조건
    • 입출력, 명확성, 유한성, 유효성 + ( 실용적 조건 ) 효율성
• 알고리즘 설계
  • 대표적인 설계 기법
    • 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법
    • 욕심쟁이 방법
      • 거스름돈 문제, 배낭 문제, 최소 신장 트리 문제( 크루스칼 알고리즘, 프림 알고리즘 ), 단일 출발점 최단 경로 문제( 데이크스트라 알고리즘 )
    • 분할정복 방법
      • 이진 탐색, 퀵 정렬, 합병 정렬
    • 동적 프로그래밍 방법
      • 모든 쌍 간의 최단 경로 문제(플로이드 알고리즘), 연쇄적 행렬 곱셈 문제, 최장 공통 부분 수열 문제