[컴퓨터공학개론] 5. 알고리즘 (Algorithms)

본 게시물은 컴퓨터공학개론 과목의 강의영상과 강의자료를 바탕으로 작성한 학습용 게시물입니다.

---

알고리즘의 개념 

# 알고리즘 

: 모호하지 않고 실행 가능한 단계들의 집합이며, 단계들에는 순서가 정해져있고 종료되는 프로세스를 정의

- 프로그램 : 알고리즘에 대한 표현 

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

---

알고리즘의 표현 (Algorithm Representation)

# 프리미티브 

: 알고리즘 표현에 사용될 잘 정의된 기초 요소 
- 자체의 semantics와 syntax을 갖음 
- 프리미티브 조합 규칙의 집합이 프로그래밍 언어를 구성

 

# 의사코드 

: 알고리즘 개발 과정에서 생각들을 보다 자유로운 형식으로 표현할 수 있는 표기 체계 
- 배정문, 조건, 반복문, 함수정의
- 들여쓰기 

---

알고리즘의 발견 (Alogorithm Discovery)

 

- 알고리즘의 발견 :  프로그램으로 표현 

- Polya's Problem Solving Steps 

- 단계적개선법

- 넓은 시각의 유지 필요

---

반복구조 

# 반복구조 

: 순환 방식으로 반복되는 일단의 명령 

- ex) 순차 검색 (선형 검색) 알고리즘, 삽입 정렬 알고리즘 

- 초기화 : 종료 조건으로 이행되어갈 초기 상태 확립

- 테스트 : 현재 상태와 종료 조건을 비교하고 이들이 같으면 반복을 종료

- 변경 : 종료 조건을 향해 이행되도록 상태 변화시킴 

- 사전 테스트 루프 : while 루프 구조, 본체 실행 전에 종료 조건을 테스트 

- 사후 테스트 루프 : repeat 루프 구조, 본체 실행 후에 종료 조건을 테스트 

---

재귀구조 

# 재귀구조

: 명령 집합을 원래 작업의 부분 작업으로서 반복하는 형태 

- ex) 이진 검색 알고리즘 

- 초기화, 변경, 종료 테스트의 세 가지 요소가 필요하다. (기본 케이스)

- 재귀 함수를 실행하면 그 함수의 여러 복사본이 생기는데, 이들은 여러 개의 원통으로 만들어진 망원경의 원통들처럼 생겨났다가 알고리즘이 진행되면서 사라진다.

- 특정 시점에는 한 개의 복사본만이 실제로 진행되며, 나머지 복사본들은 기다린다. 

---

효율성과 정확성 

# 알고리즘 분석 

- 최선 / 최악 / 평균 경우의 분석 

- ex) 최선 : n-1 회 , 최악 : n(n-1)/2 회, 평균 : n(n-1)/4 회 

 

# 소프트웨어 검정 

- 명제 ㅣ 사전조건, 사후조건, 루프 불변 명제