Chapter1 알고리즘 개요

알고리즘

문제의 해답을 구하기 위한 절차를 순서대로 명확하게 나타낸 것, 주어진 문제 해결을 위한 단계적인 절차

9세기경 페르시아의 수학자 알-콰리즈미(Al-Khwarizmi)의 이름에서 유래되었다.

컴퓨터를 통한 문제의 해결은 한가지 방법만 있는것이 아니라 서로 다른 여러가지의 방법들이 존재한다.

→ 방법들 사이의 효율성 차이가 매우 크다. ⇒ 가장 최적화된 효율적인 방법론을 찾는것이 중요!!

알고리즘의 조건

컴퓨터를 통한 문제 해결은 절차를 표현하기 위해 명령어들을 사용한다. 하지만 모든 명령어의 집합이 알고리즘이 되는것은 아니다.

→  알고리즘이라는 명령어가 되기 위해서는 조건이 필요하다.

• 입력 : 0개 이상의 입력을 갖는다.
• 출력 : 반드시 1개 이상의 출력을 갖는다.
• 명확성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다,
• 유한성 : 알고리즘의 단계는 한정되어야 하며 수행 후 반드시 종료되어야 한다.
               → 무한루프에 빠져서는 안된다.
• 유효성 : 현재 실행 가능한 연산이어야 한다.
                → 미래에 개발될 기술 등을 포함해서는 안된다.

알고리즘의 표현 방법

자연어(Natural Language)

find_max(A)
1. 리스트 A의 첫 번째 항목을 변수 max에 대입한다.
2. 리스트 A의 다음 항목들을 차례대로 max와 비교하여, max보다 더 크면 그 값을 max로 복사한다.
3. 배열 A의 모든 요소를 비교했으면 max를 반환한다.

장점 : 표현이 자유롭고 편리하다

단점 : 문장의 의미가 애매해질 가능성이 존재한다.

흐름도(FlowChart)

find_max(A) FlowChart

장점 : 알고리즘의 절차가 한눈에 보이므로 가장 정확하게 표현할 수 있다.

단점 : 절차가 많아지면 그림이 복잡해져 오히려 이해하는것을 방해하고 혼란을 야기한다.

유사코드(Pseudo-code)

자연어보다는 체계적이지만 프로그래밍 언어보다는 덜 엄격하게 쓰여진 알고리즘 표현법

find_max(A)
	max ← A[0]
    for i ← 1 to size(A)
    	if A[i] > max then
        max ← A[i]
    return max

장점 : 불필요한 표현들을 생략할 수 있다.

프로그래밍 언어(Programming Language)

//C언어 알고리즘 코드
inf find_max(int A[], int n) {
    int i, max = A[0];
    for (i = 1; i < n; i++){
    	if (A[i] > max) {
            max = A[i];
        }
    }
    return max;
}

#파이썬 알고리즘 코드
def find_max(A):
    max = A[0]
    for i in range(len(A))
    	if A[i] > max:
            max = A[i]
    return max

장점 : 알고리즘을 실행해 볼 수 있어 매우 편리하다.

단점 : 특정 프로그래밍 언어에 대해 알고 있어야 하며 문법상의 불필요한 표현들이 알고리즘의 이해를 방해할 수 있다.

※ 파이썬은 유사 코드와 표현법이 매우 비슷하기 때문에 알고리즘의 사용과 확인이 매우 편리하다.

예시 1) 최대 공약수를 구하는 알고리즘

1. 정의를 사용
   1) a의 약수를 모두 찾아 Alist에 저장
   2) b의 약수를 모두 찾아 Blist에 저장
   3) Alist와 Blist를 서로 비교하며 공통으로 들어있는 수 중 가장 큰 수를 반환한다,
   

   a = 60
   b = 28
   Alist = (1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30)
   Blist = (1, 2, 4, 7, 14)
   CommonDivisor = (1, 2, 4)
   GreatestCommonDivisor = 4
   print(GreatestCommonDivisor)

2. 한 수의 약수만 구함
   1) a와 b 둘중 하나의 수에서 약수를 모두 구한 뒤 List에 저장
   2) 저장 된 List의 가장 큰 수 부터 차례로 남은 수의 약수인지 검사하고 약수이면 해당 수를 반환한다.
   3) List의 모든 숫자에 대해 반복한다.
   

   a = 60
   b = 28
   list = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30]
   list.reverse()
   def CommonDivisor(list, b): 
       result = 0
       for i in range(len(list)):	## 28%30, 28%20, 28%15 ...... 28%4 = 0
           if b%list[i] == 0: 
               result = list[i]
               break
       return result				## GreateCommonDivisor = 4
   print(CommonDivisor(list, b))

3. 유클리드 알고리즘
   1) a와 b중 큰 수를 작은수로 나눠 나머지를 구한다.
   2) a와 b중 작은 수를 1)에서 나온 나머지로 나눠 나머지를 다시 구한다.
   3) 이 방법을 나머지가 0이 될 떄 까지 반복하며 이때 나온 수가 최대 공약수이다.
   

   a = 60
   b = 28
   def gcd(a, b):
       while b != 0:
           tmp = a % b
           a = b
           b = tmp
       return a
   GreateCommonDivisor = gcd(a, b)
   print(GreateCommonDivisor)

문제 해결 과정

알고리즘의 개발 과정

1. 문제의 이해 : 문제를 정확하게 이해하고 애매한 부분을 모두 없애 모든 유효 입력에 대해 정확한 해답을 구할 수 있어야 한다.
2. 설계 방향 결정 : 사용할 계산 장치의 특성에 따라 순차 알고리즘과 병렬처리, 최적해와 근사해 등 알고리즘을 선택한다.
3. 설계 : 억지 기법과 완전 탐색, 축소와 분할 정복법, 동적 계획, 탐욕적 기법, 백트래킹과 분기 한정기법 등 다양한 설계
            기법중 선택하여 알고리즘을 설계한다.
4. 정확성 검증 : 모든 유효 입력에 대해 유한한 시간 안에 정확한 결과를 구한다는 것을 검증한다. 실험적 분석과 증명적
                        분석이 있다.
5. 분석 : 검증이 완료된 알고리즘을 시간과 공간, 코드 효율성의 측면에서 분석하여 개선점을 찾아낸다.
6. 구현 : 분석까지 마친 알고리즘을 프로그래밍 언어를 통해 구현한다.

중요한 문제의 유형들

정렬(Sorting)

데이터를 순서대로 재배열하는 것

정렬을 위해서는 사물들을 서로 비교할 수 있어야 하며, 비교할 수 있는 모든 속성은 정렬의 기준이 된다

• 레코드 : 정렬할 대상, 여러개의 필드를 통해 이루어진다.
• 정렬 키 : 정렬의 기준이 되는 필드
• 안정성 : 입력에 동일한 키 값을 갖는 레코드가 존재할 때 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것
                ex)  (30, 20, 30, 40, 10) → (10, 20, 30, 30, 40)
• 비교기반 정렬 : 키 값을 서로 비교하여 정렬하는 방법, nlogn에 비례하는 연산 필요
• 분배기반 정렬 : 기수 정렬과 같이 키 값의 분배를 이용하는 방법, 비교기반 정렬보다 빠른 정렬이 가능하다.
• 제자리 정렬(In-place) : 입력 배열 외 추가적인 메모리를 사용하지 않는 정렬방법

탐색(Searching)

주어진 레코드의 집합에서 "탐색키"라 불리는 원하는 값을 가진 레코드를 찾는 것

순차탐색, 이진탐색, 해싱 등의 방법들이 있으며 모든 상황에 가장 적합한 알고리즘이 없기 때문에 메모리나 정렬과 같이 추가적인 사전 작업을 반드시 요구한다.

문자열 처리

주어진 문자열에서 특정 단어를 찾는 것

이 외에도 그래프, 조합, 기하학적 문제를 해결하는데 알고리즘이 사용될 수 있다.

자료구조와 파이썬

컴퓨터가 자료들을 정리하고 조직화 하는 여러 가지 자료의 구성형태

단순 자료구조

정수, 실수, 문자와 같이 프로그래밍 언어에서 기본적으로 제공되는 자료구조

복합 자료구조

단순 자료구조를 기반으로 여러가지 복잡한 형태의 자료 구조를 형성한 것

배열, 연결된 구조, 선형 자료구조, 원형 자료구조, 그래프, 트리, 집합, 맵 등이 있다.

자세한 내용은 자료구조, 파이썬 카테고리에서 기술하겠습니다.

'컴퓨터공학/자료구조' 카테고리의 글 목록 (tistory.com)

'프로그래밍/Python' 카테고리의 글 목록 (tistory.com)