[컴퓨터과학의이해🧮] 알고리즘 (5장)

교재 : 컴퓨터 과학 총론 (13th Edition)

(배운 내용을 책으로 복습하며 작성한 글입니다. )

1. 알고리즘의 개념

1) 알고리즘의 정형적 정의

알고리즘 : 모호하지 않고 실행 가능한 단계들의 집합이며, 단계들에는 순서가 정해져 있고, 종료되는 포르세르를 정의함.

2) 알고리즘의 추상적 특성

프로그램 : 알고리즘의 표현

프로세스 : 알고리즘의 실행 활동

 

2. 알고리즘의 표현

1) 프리미티브

- 프리미티브 (primitive) : 알고리즘 표현에 사용할 잘 정의된 기초 요소

- 프리미티브를 정확히 정의하게 되면 많은 모호성 문제가 해결되며, 프리미티브를 사용하여 알고리즘을 기술하도록 요구함으로써 세부사항 서술 정도의 일관성을 확립할 수 있다. 

- 프리미티브의 집합과 더 복잡한 개념을 표현하기 위한 프리미티브 조합 규칙의 집합이 프로그래밍 언어를 구성하는 요소이다. 

- 각 프리미티브는 자체의 구문(syntax)과 의미(semantics)을 갖는다. 

- 구문은 프리미티브의 기호 표현을 가리키며, 의미는 프리미티브가 나타내는 개념을 가리킨다. 

 

2) 의사코드

- 의사코드 (pseudocode) : 알고리즘 개발 과정에서 생각들을 보다 자유로운 형식으로 표현할 수 있는 표기 체계

- 프로그래밍 언어에 비해 사람이 이해하기 쉬우며 자연어보다 명확하다. 

- 알고리즘 표현에 적합해야 하며, 이는 자주 나타나는 의미구조를 일관성 있고 간결하게 표현할 수 있는 표기법을 갖추어야 한다. 

 

3. 알고리즘의 발견

1) 문제해결 기술

- 폴리야가 제시한 문제 해결 단계

① 문제를 이해한다. 

② 문제 해결을 위한 계획을 세운다.

③ 계획을 실행한다. 

④ 앞에서 구한 해결 방법이 정확한지 검토하고, 또 이 방법을 다른 문제의 해결에도 사용할 수 있도록 일반화할 수 있는지 평가한다. 

 

2) 알고리즘 발견의 기초

-문제 해결 방법

• 문제를 거꾸로 풀기
• 더 쉬운 문제나 이미 해결방법이 알려져 있는 비슷한 문제를 찾아보고 그 해결방법을 현재의 문제에 적용해본다. 
• 단계적 개선법 (stepwise refinement) : 주어진 문제를 몇 개의 작은 문제로 간주하고, 단계들을 모아 전체적인 해결방법을 얻는다. (하향식(top-down) 방법론)
• 상향식(bottom-up) 방법론 : 세부적인 것에서 일반적인 것으로 진행

- 알고리즘의 발견은 잘 정의된 방법론들을 다루는 것이 아니라 상당기간에 걸쳐 힘들게 노력하며 발전시켜 나가야 하는 창의적인 능력이다.

4. 반복 구조

1) 순차 검색 알고리즘

- 순차 검색 (sequntail search) 또는 선형 검색(linear search)

- 비교할 대상이 남아있고, 검색 대상이 현재 확인하는 대상보다 클 경우 리스트에 대한 검색을 계속한다. 

 

2) 루프 제어

- 반복 제어의 구성 요소

• 종료 조건으로 이행되어갈 초기 상태를 확립한다 ; 초기화
• 현재 상태와 종료 조건을 비교하고 이들이 같으면 반복을 종료한다 ; 테스트
• 종료 조건을 향해 나아가도록 상태를 변화시킨다 ; 변경

- 사전 테스트 루프 (pretest loop) : 본체 실행 전에 종료 조건을 테스트한다. 

- 사후 테스트 루프 (posttest loop) : 본체 실행 후헤 종료 조건을 테스트한다.

 

3) 삽입 정렬 알고리즘

삽입 정렬(insertion sort) : 한 항목을 꺼내 적절한 자리에 삽입하는 일을 반복해 리스트를 정렬한다. 

 

5. 재귀 구조

; 재귀법에서는 명령 집합을 원래 작업의 부분 작업으로서 반복한다. 

 

1) 2진 검색 알고리즘

- 2진 검색(binary search) : 리스트를 두 부분으로 분할하며 목표값을  검색한다.

- 정렬된 리스트에 사용한다.

- 리스트의 중앙 항목에서 검색을 시작한다. 

- 리스트의 중앙 항목이 목표값일 경우 검색의 성공을 선언한다. 

- 리스트의 중앙 항목이 목표값과 다를 경우, 목표값이 지금 비교한 항목보다 작은지 큰지에 따라 리스트의 전반부 또는 후반부로 검색 범위를 제한한다. 

- 목표 값을 찾거나 검색 범위가 비어있는 리스트 구간으로 좁혀질 때까지 문제의 리스트를 작은 구간으로 계속 분할한다. 

- 목표 값이 원래의 리스트에 들어 있지 않을 경우, 리스트를 분할한 구간이 빈 구간이 될 때까지 분할을 계속하고, 빈 구간이 나타나면 검색이 실패했음을 인지한다. 

 

2) 재귀 제어

- 재귀법 (recursion) : 각 반복 단계를 이전 단계의 부분 작업으로 실행시킨다.

• 재귀함수를 실행하면 그 함수의 여러 복사본이 생기고 각 복사본은 그 함수를 수행하는 것처럼 보인다. 
• 이러한 각 함수의 복사본을 함수 호출(activation)이라 부른다. 특정 시점에는 한 개의 복사본이 실제로 진행되며, 나머지 복사본들은 멈추고 있다가 다른 복사본이 끝나면 진행된다. 
• 재귀 시스템에서는 종료 조건에 대한 테스트와 종료 조건에 도달하도록 보장하는 설계가 중요하다. 
• 재귀 함수는 추가적인 호출 전에 기본케이스(base case)라 부르는 종료 조건을 테스트하도록 설계된다.
• 종료 조건이 만족될 경우, 추가적인 호출 없이 현재 호출된 복사본을 종료시키는 실행 경로를 취한다. 

* 검색 알고리즘에 대해 서술한 다른 글입니다.

https://0yeonjae2.tistory.com/entry/IT%EA%B0%9C%EB%A1%A0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?category=535579 

[IT개론] 알고리즘

 

6. 효율성과 정확성

1) 알고리즘 효율성

- 알고리즘 분석은 종종 최선의 경우, 최악의 경우, 평균적인 경우의 시나리오에 대해 이루어진다. 

• 순차 검색 알고리즘은 평균 n/2개의 항목을 검사한다. 
• 삽입 정렬 알고리즘은 최선의 경우 n-1개의 비교가 필요하다. 
• 삽입 정렬 알고리즘은 최악의 경우 (1/2)*(n^2-n)번의 비교가 필요하다. 
• 삽입 정렬 알고리즘은 평균적인 경우 (1/4)*(n^2-n)번의 비교가 필요하다.

- 알고리즘의 작업 수행에 필요한 시간을 입력 데이터 크기와 비교하여 얻은 그래프의 모양은 알고리즘의 효율성이라는 특성을 반영한다. 그래프 모양은 대개 최악 경우 분석에 기초한다.

- 빅 세타 표기법 : 알고리즘 분류 클래스를 나타내는 데 사용되는 표기법

 

2) 소프트웨어 검증

- 정형 논리 기법 (formal logic) 

• 프로그램이 표현하는 알고리즘이 의도된 작업을 수행하는지를 증명한다. 
• 프로그램의 정확성에 대한 엄밀한 증명은 프로그램 설계가 따르는 명세에 기초한다. 
• 정확성 증명은 사전 조건(precondition)이라 불리는 특정 조건이 프로그램 실행이 시작될 때 만족된다는 가정을 한다. 
• 사전조건들로 인한 결과가 프로그램 전체로 어떻게 파급되는지를 고려한다. 
• 정확성 증명은 프로그램의 여러 위치에 있을 수 있는 명제(assertion)라는 문장을 찾는 작업을 포함한다. 
• 각 명제는 프로그램의 사전 조건들에서 시작하여 그 명제를 세워둔 위치에 이르는 일련의 명령들을 수행한 결과에 부합되어야 한다. 
• 프로그램의 끝 부분에 세운 명제가 원하는 결과 명세(postcondition)에 부합될 경우 프로그램은 정확하다고 결론지을 수 있다.