1. 알고리즘의 개요

안녕하세요 

공상 개발입니다.

 

이번 시간에는 알고리즘의 개요에 대해 알아보는 시간을 가지도록 하겠습니다.

---

 

1. 알고리즘이란? 2. 알고리즘의 표현 3. 알고리즘의 분석

 

---

 

# 알고리즘이란?

 

알고리즘(algorithm)은

주어진 문제에 대한 답을 찾는 단계적 절차 혹은 기법을 말합니다.

 

컴퓨터공학에서 알고리즘은 프로그램에서 어떤 특정한 일을 수행하는 개별적인 모듈과 유사합니다.

 

우리는 아래의 내용들을 중심으로 학습할 것입니다.

주어진 문제를 해결하는 알고리즘의 설계 기법 알고리즘의 효율성 분석 기법 중요한 문제에 대한 효율적 알고리즘의 이해 적절하고 효율적인 자료구조를 이용한 알고리즘의 구현

 

알고리즘 과목 자체가 어려운 것은 맞지만 사실 자료구조 과목에서 배웠던 내용과 겹치는 부분이 많이 있습니다.

 

알고리즘에서 다루는 중요한 문제들을 보자면,

고전적 문제 : 정렬 문제, 선택 문제, 검색 문제 등  최적화 문제 : 배낭문제, 스케줄링 문제, 행렬 연산 문제, 파일 압축 문제, LCS 문제 등  그래프 문제 : 그래프 탐색 문제, 최소 신장 트리 문제, 최단 경로 문제, 순회 외판원 문제 등

 

정렬 문제와 검색 문제의 경우 학부 1~2학년 때 많이 접하고,

그래프 문제의 위의 4가지 예시는 자료구조 시간 때 한 번씩 다루었던 개념들입니다.

최적화 문제의 경우에도 직접적으로 다룬 적은 없지만 한 번씩은 들어본 개념입니다.

 

---

 

# 알고리즘의 표현

 

주로 의사 코드(pseudocode)로 표현합니다.

 

이해를 돕기 위해 2가지 예시를 들며 한번 살펴봅시다.

 

예제1 : 최댓값의 인덱스 구하기.

 

구체적(concrete) 문제 : 알고리즘 중간고사 성적 1등은 몇 번째 학생인가?. 추상화(abstract) 문제 : n 개의 숫자들 중 최댓값의 인덱스 구하기. 문제 해결 방법 : 배열의 각 원소를 순서대로 스캔하면서 더 큰 값이 나올 때마다 최댓값의 인덱스를 업데이트한다.

 

의사 코드

자연어로 표현한 의사코드

배열의 최댓값 인덱스 구하기 max_index를 우선 0이라 한다. 배열의 인덱스를 하나씩 뒤로 옮겨가며,    만일 비교하는 원소가 현재 최대보다 크면, max_index를 바꾼다. max_index를 반환한다.

 

구현을 고려한 의사코드

get_max_index(a[0... n-1])  max_index = 0 for i=1, ..., n-1              if(a[i] > a[max_index])          max_index = i      max_index를 반환

 

코드

 

출력 값

 

T(n) = O(n)

 

---

 

예제2 : 정렬된 배열에 값 삽입하기.

 

구체적 문제 : 학생들의 중간고사 점수를 성적순(오름차순)으로 정렬하였지만, 마지막 원소를 빠뜨리고 정렬하지 못한 경우, 마지막 원소를 성적순이 되도록 끼워 넣는다. 추상화 문제 : 정렬된 리스트에 값을 삽입한다. 문제 해결 방법 : 정렬된 배열에서 마지막 원소의 삽입 위치를 찾아, 삽입 위치 이후의 원 소들은 모두 한 칸씩 뒤로 이동하고 해당 위치에 값을 삽입

 

의사 코드

자연어로 표현한 의사코드

정렬된 배열에 값 삽입하기                         정렬된 배열의 마지막 원소부터 시작하여 한 칸씩 앞으로 이동하며                                만일 삽입 값이 비교하는 원소보다 작으면                      해당 원소를 한 칸 뒤로 이동 아니면 루프 탈출 해당 위치(탈출 위치 바로 뒤)에 값을 삽입한다.

 

구현을 고려한 의사코드

insert(a[0,...,n]) x = a[n]         for j=n-1, ..., 0                           if(a[j] > x) a[j+1] = a[j]            else break    a[j+1] = x

 

프로그램 동작 추가 설명 10 35 45 20 이렇게 마지막 수만 정렬되지 않았다고 가정하고, 10 35 40 20 10 35 40 40 10 35 35 40 10 20 35 40 바로 아래의 코드를 통해 직관적으로 이해해봅시다.

 

코드

 

출력 값

 

B(n) = O(1)

W(n) = O(n)

A(n) = O(n)

 

---

 

# 알고리즘의 분석

 

알고리즘의 분석

알고리즘 분석은 효율성을 분석하는 것이다. 알고리즘이 자원(resource)을 얼마나 소모하는지 분석하는 것이다. -자원 : 소요 시간, 메모리(공간), 통신 대역 등이 있다.

 

시간 복잡도 분석(time complexity analysis)

알고리즘의 실행 시간(running time) 효율성 분석  알고리즘의 실제 실행 시간을 측정하는 방법 : 실행 환경의 영향을 많이 받는다.  시간 복잡도 분석은 물리적 시간 대신 명령문의 실행 횟수를 분석한다.  주어진 알고리즘의 실행 시간은 입력(input)에 따라 달라진다.

입력 크기(input size) 흔히 n으로 표시한다.   검색 혹은 정렬 문제 : 배열에 저장된 원소(element)의 수  팩토리얼, 피보나치 수열 : n의 크기(비트수)  그래프 문제 : 정점과 간선의 수

시간 복잡도 분석  입력 크기에 따른 중요 연산의 수행 횟수를 계산 모든 경우 시간 복잡도 T(n)  동일한 입력 크기라도 입력 사례에 따라 실행 횟수가 달라지는 경우   최악의 경우 시간 복잡도 W(n) : 최대 실행 횟수  평균의 경우 시간 복잡도 A(n) : 평균 실행 횟수  최선의 경우 시간 복잡도 B(n) : 최소 실행 횟수

 

빅오 표기법

정확한 실행 횟수보다 n이 커짐에 따라 어떤 비율로 시간이 증가하는지가 중요하다. n에 의존하는 항이 여러 개인 경우, 차수가 제일 높은 항이 전체 시간을 지배한다. 빅 오(O) 표기 : 시간 복잡도의 최고차항을 표시한 것 ex) T(n) = 3n^2nlogn+5n+3 = O(n^2) ex) T(n) = n^5+2^n+100n+5 = O(2^n)

 

---

 

피드백

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시면 감사하겠습니다.

 

좋은 하루 보내세요.