알고리즘.

어떻게 표현해야하고 얼마나 자세히 기술해야할까?

프로그램은 알고리즘에 대한 표현이다. 즉, 알고리즘을 표현한게 프로그램이다.

의사코드 (Pseudocode)

- 자연어(Natural language)와 프로그래밍 언어 사이.

- 알고리즘을 비정형적(Informal) 표현

- FlowChart, UML

의사코드(Pseudocode)의 설계

- 널리 사용되는 프로그래밍 언어 아무거나 선택. (C, JAVA, Python ...)

- 구문 규칙 니 맘대로(라기보단.. 다소 완화)

- 일부 자연어 표현 허용

- 일관성 있고 간결하게...

의사코드 프리미티브 (Python Style)

- 배정문 (Assignment Statement)

이름 = 식

- 조건부 선택 (Conditional Selection)

if(조건):
	활동
    
ex) if(판매액이 감소):
		가격을 5%만큼 낮추거라.

if(조건):
	활동
else:
	활동
    
ex) if(해당 연도가 윤년):
		1일 합계 = 합 / 366
    else:
    	1일 합계 = 합 / 365

- 반복 실행 (Repeated Execution)

while (조건):
	본체
    
ex)	while (판매할 티켓 남음):
		한 장의 티켓 판다.

- 함수 정의 (Function Definition) & 함수 실행 (Function Call)

# 함수 정의
def 이름():
ex) def ProcessLoan():

# 함수 실행
if(...):
	ProcessLoan()
else:
	RejectApplication()
    
ex)
	def Greetings():
    	count = 3
        while(count>0):
        	print('Hello')
            count = count - 1

알고리즘의 발견

- 프로그램 개발의 첫 단계

- 예술에 가까움... 그리고 어려움

Polya의 문제 해결 단계

1. 문제 이해.

2. 알고리즘적 절차.. 어떻게 해결해야할까? 정리

3. 알고리즘 기술 -> 프로그램으로 표현

4. 정확도 검토, 일반화 등 평가.

반복 구조 (Iteration Structure)

1. Iteration

- for, while, repeat 등.. loop구조 사용

- 순차 검색(Linear or Sequential search) 알고리즘 : 정렬되어 있는 상태에서 리스트 안의 특정 값 찾기.

- 삽입 정렬(Insertion Sort) 알고리즘.

- Loop Control

초기화 : 초기값 (int i=0;)

테스트: 반복 조건 (종료 조건) (i < 10;)

변경 : 종료 조건에 만족하도록.. (i++)

- 사전 테스트 루프 : 조건에 만족할 때 까지 돌림.

- 사후 테스트 루프 : 닥치고 돌고 조건에 만족하면 나감.

2. Recursive Structure

- 명령 집합을 원래 작업의 부분 작업으로서 반복.

- 동일 함수에 대한 여러 개의 호출 중첩(자기를 호출), 한 개의 호출본에 대한 진행. 나머지는 다른 호출본들이 완료되기 까지 기다림.

ex) binary search(이진 검색) 알고리즘 : 이미 정렬 되어 있다는 가정.

저작자표시 비영리