[컴퓨터과학개론] 5. 알고리즘

01. 알고리즘 개념

 

🔸컴퓨터과학: 컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문

문제를 풀기 위해선 알고리즘이 반드시 있어야 함

 

 

 

 

 

✅ 알고리즘

• 문제 해결을 위한 레시피
  • 단계적인 조리 절차를 따르면 음식을 만들 수 있듯이, 주어진 문제도 단계적인 풀이 절차("알고리즘")를 따르면 문제의 해를 구할 수 있음
  • 맛있고 좋은 음식 ↔ 효율적인 알고리즘

 

• 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것
  1. 입출력: 0개 이상의 외부 입력, 1개 이상의 출력
  2. 명확성: 각 명령은 모호하지 않고 단순 명확해야 함
  3. 유한성: 한정된 수의 단계를 거친 후에는 반드시 종료해야 함
  4. 유효성: 모든 명령은 컴퓨터에서 실행 가능해야 함
  5. (실용적 관점) 효율성

➡️ 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것

 

 

 

 

 

✅ 알고리즘 생성 단계

설계 표현/기술 기술 방법 일상언어 의사코드 순서도 정확성 검증 효율성 분석

 

 

 

 

 

✅ 자료구조와 알고리즘의 관계

• 자료구조
  • 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법
  • 배열, 연결 리스트, 스택, 큐, 트리, 그래프
• "효율적" 프로그램 ← 자료구조+알고리즘
  • 자료구조에 대한 고려 없는 효율적인 알고리즘의 선택 또는 알고리즘에 대한 고려 없는 효율적인 자료구조의 선택은 무의미

 

 

 

 

 

 

 

02. 알고리즘 설계

 

🔸최대값 찾기

두 알고리즘 모두 비교 횟수가 7번으로 효율성이 같음.

Q. 어떤 수의 최대/최소값을 찾기 위해 몇 번의 비교가 필요할까?
A. n→(n-1)
두 개의 데이터 중 최대값을 찾으려면 1번 비교, 세개의 데이터 중 최대값을 찾으려면 2번 비교...

 

 

 

 

🔸뒤섞인 카드에서 원하는 카드 찾기

 

 

 

🔸순서대로 나열된 카드에서 찾기

 

 

 

 

 

 

✅ 알고리즘 설계 기법

• 문제와 그에 따른 조건 등이 매우 다양 → 일반적이고 범용의 설계 기법은 없음
• 대표적인 설계 기법
  1. 분할정복(divide-and conquer)방법
  2. 동적 프로그래밍(dynamic programming)방법
  3. 욕심쟁이(greedy)방법

 

 

 

🔸분할정복 방법

• 순환적으로(recursively) 문제를 푸는 방법
  • 문제의 입력을 더이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 분할된 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법

• 특징
  • 분할된 작은 문제는 원래 문제와 동일, but 입력 크기만 작아짐
  • 분할된 작은 문제는 서로 독립적

• 각 순환 호출마다 세 단계의 처리 과정을 거침

분할	주어진 문제를 여러 개의 작은 문제로 분할한다.
정복	작은 문제를 순환적으로 분할. 만약 작은 문제가 더이상 분할되지 않을 정도로 크기가 충분히 작다면 순환호출 없이 작은 문제의 해를 구한다.
결합	작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다. ※결합 단계가 없는 문제도 존재

• 예) 퀵 정렬, 합병 정렬, 이진 탐색

 

 

 

🔸동적 프로그래밍 방법

• 최적화 문제의 해를 구하기 위한 상향식 접근 방법
  • 문제의 크기가 작은 소문제에 대한 해를 구해서 테이블에 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만듦
• 예) 모든 정점 간의 최단 경로를 구하는 플로이드 알고리즘

 

 

 

🔸욕심쟁이 방법

• 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 각 단계에서 '가장 최선'이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 얻을 수 있을 것이라고 희망하는 방법
  • 희망 → 각 단계의 최적해를 통해 전체적인 최적해를 만들어 내지 못할 수 있음
  • 적용 범위는 제한적, 간단하면서도 강렬한 설계 기법
  • 예) 거스름돈 문제, 배낭 문제

 

 

 

▪️ 거스름돈 문제

고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
동전의 종류 → 500원, 100원, 50원, 10원

 

 

 

▪️ 배낭 문제

• 최대 용량 M인 하나의 배낭, n개의 물체
  • 각 물체 i에는 물체의 무게 wᵢ와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 pᵢ
• 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾는 문제
  • 가정 → 물체를 쪼개서 넣을 수 있다

 

물체의 무게가 가벼운데 이익이 큰 놈부터 집어넣으면 됨. 단위 무게당 이익이 큰 놈부터!!

 

 

 

 

 

 

 

03. 알고리즘 분석

 

🔸정확성 분석

• 유효한 입력, 유한 시간 → 정확한 결과 생성
  • 다양한 수학적 기법을 사용한 이론적 증명이 필요 (교과 과목을 통해 배우는 알고리즘은 정확성 검증 완료!)

 

🔸효율성 분석

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
  • 메모리 양: 공간 복잡도(space complexity)
  • cpu 수행 시간: 시간 복잡도(time complexity)

 

 

 

 

 

✅ 시간 복잡도

 ▪️ 알고리즘의 수행 시간

1. 컴퓨터에서 실행시켜 완료될 때까지 걸리는 실제 시간을 측정
   • 컴퓨터의 종류와 속도, 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 종속적 → 일반성 결여!
2. "알고리즘에서 단위 연산의 수행 횟수를 모두 더한 값"
   • 입력 크기가 증가하면 수행 시간도 증가
     
     • 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현
     • 예) f(n) = 2n^2+5n+10
   • 입력 데이터의 상태에 종속적
     • 평균 수행 시간: 모든 데이터가 입력될 수 있는 경우를 고려
     • 최선 수행 시간: 어떤 데이터가 주어졌을 때 가장 빠른 수행 시간
     • 최악 수행 시간: 데이터의 상태가 알고리즘과 안 맞아서 가장 오래 걸리는 수행 시간 

 

 

 

 

 

✅ 점근성능

▪️ 입력 크기 n이 충분히 커짐에 따라 결정되는 성능

알고리즘을 수행하는데 수행되는 명령어들의 횟수 → 값이 작을 수록 좋은 알고리즘

▪️ 다항식의 수행 시간에서 가장 큰 영향을 미치는 것: 최고차항

• 계수 없이 '최고차항'만을 이용해서 표현
• 수행 시간의 어림값, 수행 시간의 증가 추세 → 알고리즘의 우열

 

 

 

🔸 점근성능의 표기법

• 알고리즘 수행시간 f(n)이 아무리 나빠도 cg(n)보다 나빠질 수 없음 → 최악의 수행 시간

 

 

• 최선의 수행 시간

 

 

 

• 최선과 최악의 시간을 동시에 표기

 

 

예)

 

 

 

 

 

▪️ 데이터 입력 크기가 증가해도 수행 시간 증가가 크지 않은 알고리즘이 BEST

 

 

 

 

 

 

 

04. 정렬 알고리즘

:선택 정렬, 버블 정렬, 삽입 정렬

 

📌 분포 기반 정렬이 성능이 더 좋은 이유
분포 기반 정렬은 내가 정렬하고 싶은 데이터가 어떤 분포적인 특성을 가지고 있는지에 대한 정보를 사전에 알고서 그걸 정렬에 활용→ 성능은 좋으나 일반성이 떨어짐(보통 정렬할 때 해당 데이터가 통계적으로 어떤 분포 특징을 가지고 있는지 잘 모름)

 

 

 

 

 

▪️ 정렬을 위한 기본 가정

 

 

 

 

 

✅ 선택 정렬

• 주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식(오름차순)

 

 

 

 

 

 

✅ 버블 정렬

• 왼쪽에서부터 모든 인접한 두 데이터를 차례대로 비교하여 왼쪽의 값이 더 큰 경우에는 오른쪽 값과 자리를 바꾸는 과정을 통해 정렬

예1

예2

입력 데이터가 8개니까 7번(8-1)의 단계를 수행하는데 4단계부터는 자리바꿈이 발생하지 않음!
== 6, 7단계는 확인하지 않아도 됨(이런 팁을 알고리즘에 적용할 수 있음)

 

 

 

 

🔸버블 정렬의 특징

• 선택 정렬에 비해 데이터 교환이 더 많이 발생 → 선택 정렬보다 비효율적
• 데이터의 입력 순서에 따라 성능이 달라짐

 

 

 

 

 

✅ 삽입 정렬

• 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은 데이터를 바른 위치에 '삽입'해서 나열하는 방식
• 입력 배열을 정렬 부분과 미정렬 부분으로 구분
  • 미정렬 부분의 가장 왼쪽에 있는 데이터("첫번째 데이터")를 꺼낸 후, 정렬된 부분에서 제자리를 찾아 삽입하는 과정을 반복

 

 

 

 

🔸삽입 정렬의 특징

• 버블 정렬과 동일