프로그램, 알고리즘에 대한 개념

프로그램의 흐름

- 순차적 흐름
- 반복
- 조건 분기

아무리 복잡한 프로그램이라도 이 세 가지를 조합하여 구현하고 있다.

프로그램이 흐르는길 (순서도)

몇 가지 예를 들어 살펴보자.

컴퓨터를 상대로 가위바위보 게임하기 (총 5번을 진행해서 내가 이긴 횟수를 표시한다).

 

가위바위보 게임 순서도

2차 방정식의 해를 근의 공식으로 해 구하기를 할때?

근의 공식으로 구하게 되면 b^2 - 4ac  요 부분이 경우에 따라 달라진다.

1부터 100까지 더하기를 생각해보면?

단순하게 1에서 100까지 모두 더하는 방법이 있는가 하면 가우스(Carl Friedrich Gauss) 공식을 이용하는 방법이 있다.

가우스 공식

알고리즘이란?

- 어떠한 문제를 해결하기 위한 여러 동작들의 모임

- 목적을 이루기 위해서는 일정한 순서와 단계를 따라야 함

- 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있음

일상생활에서 따뜻한 차 한잔을 만드는 것도 알고리즘이라고 생각한다면?

아래와 같은 목적을 위해 일련의 동작을 순차적으로 행하는 것도 알고리즘의 일종이다.

1. 티백을 컵에 넣는다
2. 주전자에 물을 붓는다
3. 물을 끓인다
4. 끓인 물을 컵에 따른다
5. 컵에 우유를 추가한다 (선택)
6. 컵에 설탕을 추가 한다 (선택)
7. 차를 휘젓는다 (선택)

알고리즘의 3가지 요소

• 알고리즘 작성
• 알고리즘 실행
• 알고리즘 사용

좋은 알고리즘이란?

아래 요소들을 고려하는 알고리즘이 좋은 알고리즘 일 것이다.

• 정확성: 적당한 입력에 대해서 유한 시간 내에 올바른 답을 산출하는가를 판단
• 작업량: 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정
• 기억 장소 사용량: 수행에 필요한 저장 공간
• 최적성: 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미