알고리즘.
어떻게 표현해야하고 얼마나 자세히 기술해야할까?
프로그램은 알고리즘에 대한 표현이다. 즉, 알고리즘을 표현한게 프로그램이다.
의사코드 (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(이진 검색) 알고리즘 : 이미 정렬 되어 있다는 가정.
