컴퓨터과학 개론 05 - 알고리즘 (1)

Wonil Jang·2024년 9월 23일

강의 컴퓨터과학개론 한국방송통신대학교

컴퓨터과학

목록 보기

10/12

해당 포스트는 강의를 수강 후 개인적으로 이해한 부분을 글로 기록하고 해석하기 위한 목적으로 이해한 부분이 틀릴수도 있습니다. 잘못 이해하고 있거나 틀린 부분에 대해서는 편하게 지적해 주시면 수정하겠습니다.

1. 알고리즘의 개념

1. 알고리즘이란?

주어진 문제를 효율적으로 해결하기 위한 명령어들을 단계적으로 나열

2. 알고리즘의 조건

입출력: 0개 이상의 입력, 1개 이상의 출력 생성
명확성: 각 명령은 단순 명확해야 한다.
유한성: 한정된 수의 단계를 거친 후 반드시 종료
유효성: 모든 명령은 컴퓨터에서 실행 가능해야 한다.

3. 알고리즘의 생성 단계

설계 -> 표현/기술 -> 정확성 검증 -> 효율성 분석

알고리즘 표현/기술 방법으로는 일상 언어로 단계 절차를 글로 작성하거나 의사코드 또는 순서도로 표현할 수 있다.

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

어떤 자료구조를 선택하느냐에 따라 작성된 프로그램의 효율성이 달라진다. 따라서 효율적인 프로그램을 작성하기 위해선 자료구조에 적합한 알고리즘 또는 알고리즘에 적합한 자료구조를 선정해야 한다.

2. 알고리즘의 설계

1. 순차 탐색, Sequential search

특정 데이터를 조회하기 위해 나열된 데이터를 첫 데이터부터 순차적으로 확인하는 탐색 방법

// 예시 코드
// [a, 4, 5, 7, 10, j, k]의 배열에서 k를 확인 
const cardList = ['a', '4', '5', '7', '10', 'j', 'k'];

const getTargetCard = ({cardList, targetCardIndex}) => {
	let targetCard; 
  	for(let i = 0; i < cardList.length; i++) {
      	if(cardList[i] === cardList[targetCardIndex]) {
        	targetCard = cardList[i]
          	break;
	  	}
    }
  	return targetCard;
};

getTargetCard({cardList, targetCardIndex: 6});

2. 이진 탐색, Binary search

순서대로 나열된 데이터 중 중간 지점의 데이터를 우선 확인하고 해당 중간 지점과 확인하고 싶은 특정 데이터가 있는 시작 지점 또는 끝 지점의 중간 지점을 다시 비교해가며 확인하는 탐색 방법

// 예시 코드
// [a, 4, 5, 7, 10, j, k]의 배열에서 10을 확인 
const cardList = ['a', '4', '5', '7', '10', 'j', 'k'];

const getTargetCard = ({cardList, targetCardIndex, startIndex, endIndex}) => {
	let targetCard
	
  	for(let i = startIndex; i <= endIndex; i++) {
      	// 원하는 특정 데이터가 확인되면 break
		// 중간 지점 찾기
    	const midIndex = Math.floor((endIndex + startIndex) / 2)
        // 중간 지점과 타겟 인덱스가 같으면 targetCard 값 할당하고 break
      	if(midIndex === targetCardIndex) {
        	targetCard = cardList[midIndex]
          	break;
	  	}
      	// 중간 지점과 타겟 인덱스 확인
      	// 1. 중간 지점보다 타겟 인덱스가 크면 시작 지점이 중간 지점의 오른쪽부터 시작	
      	if(midIndex < targetCardIndex) {
        	startIndex = midIndex + 1
        }
      	// 2. 중간 지점보다 타겟 인덱스가 작으면 끝 지점이 중간 지점의 왼쪽
      	if(midIndex > targetCardIndex) {
        	endIndex = midIndex - 1
        }
    }
  	return targetCard;
};

getTargetCard({cardList, targetCardIndex: 4, startIndex: 0, endIndex: cardList.length - 1});

3. 대표적인 설계 방법

1. 분할 정복, Divide-and-conquer

순환적으로 문제를 푸는 방법, recursive
문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제로 순환적으로 분할하여 분할된 문제들을 각각 해결한 후 결과 값을 결합하여 기존 문제를 해결하는 하향식 접근 방법
특징

분할된 작은 문제는 기존 문제와 동일, 입력 크기만 축소
분할된 작은 문제는 서로 독립적이다.

분할 정복 단계

분할: 주어진 문제를 여러 개의 작은 문제로 분할
정복: 작은 문제를 순환적으로 분할
결합: 정복에서 도출된 결과 값을 결합하여 기존 문제의 결과 값을 구한다.

대표적인 예시
1. 팩토리얼 함수

2. 동적 프로그래밍, Dynamic programming

최적화 문제의 값(최대값, 최소값)을 구하기 위한 상향식 접근 방법
문제의 크기가 작은 소문제에 대한 값을 구해 테이블에 저장하고 이를 이용하여 크기가 큰 문제의 값을 점진적으로 만들어 가는 방법
소문제들이 독립적일 필요 없다.
대표적인 예시

플로이드 알고리즘: 모든 정점 간 최단 경로를 구하는 알고리즘

3. 탐욕적 방법, Greedy

값을 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 각 단계에서 '가장 최선'이라고 여겨지는 국부적인 최적 값을 선택해 나가며 전체적인 최적 값을 결과적으로 얻을 수 있다고 희망하는 방법
대표적인 예시

배낭 문제

문제: 최대 용량 M(kg)인 배낭과 n개의 물체가 있을 때 배낭의 용량을 초과하지 않고 배낭에 들어 있는 물체의 이익의 합이 최대가 될 수 있는 방법을 찾는 문제

예시)
가방무게: $M= 10$ , 물체 개수: $n = 4$

이익: $(p_1, p_2, p_3, p_4) = (14, 15, 20, 9)$

단위: $(w_1, w_2, w_3, w_4) = (4, 3, 5, 3)$

단위 무게당 이익
$(\frac{p_1}{w_1}, \frac{p_2}{w_2}, \frac{p_3}{w_3}, \frac{p_4}{w_4}) = (3.5, 5, 4, 3)$

물체는 분할할 수 있다. 위 단위 무게당 이익으로 계산하여 최대 이익을 구할 수 있다.

4. 알고리즘의 분석

1. 알고리즘 분석

정확성 분석: 유효한 입력과 유한 시간 -> 정확한 결과 생성, 다양한 수학적 기법을 사용하여 이론적으로 증명
효율성 분석

알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정

공간 복잡도, Space complexity
- 메모리의 양 = 정적 공간 + 동적 공간
시간 복잡도, Time complexity
- 수행 시간

2. 시간 복잡도

알고리즘의 수행 시간

알고리즘에서 수행되는 단위 연산의 수행 횟수를 모두 더한 값
입력 데이터의 크기(입력 크기)가 증가하면 수행 시간 증가
단순히 수행되는 단위 연산 개수의 합이 아닌 입력 크기의 함수로 로 표현
입력 데이터의 상태에 따라 달라진다.
평균 수행 시간, 최선 수행 시간, 최악 수행 시간

코드 // 수행 횟수
i = 0; // 1
sum = 0; // 1
while (i<n) { // n + 1
sum = sum + a[i] // n
i = i + 1	// n
}
average = sum/n; // 1
print sum, average // 1

위 코드의 시간 복잡도는 입력 데이터 n에 대한 함수 $f(n) = 3n + 5$

점근성능

입력 크기 n이 충분히 커짐에 따라 결정되는 성능
계수 없이 최고차항만을 이용해서 간략히 표현하는 성능

최고차항: 수행 시간의 어림 값, 수행 시간의 증가 추세 -> 알고리즘의 우열 비교

점근성능의 표기법

정의 1
Big-oh, 점근적 상한
양의 정수를 갖는 f와 g라는 함수가 있고
$n \geq n_0$ 인 모든 $n$ 에 대해 $f(n) \leq c \times g(n)$ 을 만족하는 양의 상수 $c$ 와 $n_0$ 이 존재하면 $f(n) = O(g(n))$ 이다.

정의 2
Big-omega, 점근적 하한
양의 정수를 갖는 f와 g라는 함수가 있고
$n \geq n_0$ 인 모든 $n$ 에 대해 $f(n) \geq c \times g(n)$ 을 만족하는 양의 상수 $c$ 와 $n_0$ 이 존재하면 $f(n) = \Omega(g(n))$ 이다.

정의 3
Big-theta, 점근적 하한
양의 정수를 갖는 f와 g라는 함수가 있고
$n \geq n_0$ 인 모든 $n$ 에 대해 $c_1 \times g(n) \leq f(n) \leq c_2 \times g(n)$ 을 만족하는 양의 상수 $c_1$ , $c_2$ 와 $n_0$ 이 존재하면 $f(n) = \theta(g(n))$ 이다.

O-표기 간의 연산 시간 크기 관계

상수시간 < 로그 시간 < 선형 시간 < 로그 선형 시간 < 제곱 시간 < 세제곱 시간 < 지수 시간
$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2n^2)$

상수 시간으로 갈수록 효율적이고 지수 시간으로 갈수록 비효율적이다.

5. 정렬 알고리즘

1. 기본 개념

정렬은 수행 시점에 데이터의 저장 위치에 따라 내부 정렬, 외부 정렬로 나뉜다.

내부 정렬: 모든 데이터를 주기억장치에 적재한 후 정렬하는 방식
외부 정렬: 모든 데이터를 주기억장치에 저장할 수 없는 경우 전체 데이터를 보조기억장치에 저장하고 그 중 일부 데이터를 번갈아 가면서 주기억장치로 적재해서 정렬하는 방식

2. 내부 정렬

비교 기반
- 데이터를 정렬할 때 값을 직접적으로 비교하여 정렬하는 방식
- 일반적으로 사용하는 정렬 방식
분포 기반
- 데이터가 분포하고 있는 정보를 바탕으로 정렬하는 방식
- 비교 기반 정렬에 비해 더 성능이 좋다.
비교 기반
1. 선택 정렬
  - 주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식
  - 특징
    - 데이터 입력 상태에 영향을 받지 않아 수행 시간은 항상 동일하다.
2. 버블 정렬
  - 왼쪽부터 인접한 두 데이터를 차례대로 비교하여 왼쪽의 값이 큰 경우 오른쪽 값과 자리를 바꾸는 과정을 반복
  - 특징
    - 입력 데이터의 상태에 따라 성능에 영향을 받는다.
    - 선택 정렬에 비해 데이터 교환이 더 많이 발생하여 상대적으로 비효율적이다.
3. 삽입 정렬
  - 주어진 데이터를 하나씩 추출하여 항상 정렬된 형태를 가지도록 추출한 데이터를 바른 위치에 삽입해서 나열하는 방식
  - 특징
    - 입력 데이터의 상태에 영향을 받음

Wonil Jang

아 좀 신나고 싶네! XD

이전 포스트

컴퓨터과학 개론 04 - 자료구조(2)

다음 포스트

컴퓨터과학 개론 05 - 알고리즘 (1)