알고리즘 구현

알고리즘

알고리즘의 개념

넓은 의미에서는 자료 구조와 함께 프로그램을 구성하는 요소를 의미하고, 좁은 의미에서는 어떤 문제에 대한 답을 찾는 해법을 의미한다.

프로그램 작성 과정 중 설계/계획 단계에 퐇마되며, 문제 해결을 위한 일련의 절차나 방법을 공식화한 형태 또는 계산을 실행하기 위한 단계적 절차를 말한다.

 

알고리즘의 5가지 특성

알고리즘은 기본적인 명령어를 통해서도 작성 가능하며, 아래와 같은 5가지 특성을 만족하여야 한다.

• 입력 : 외부로부터 입력되는 자료가 0개 이상이어야 한다.
• 출력 : 출력되는 결과가 1개 이상이어야 한다.
• 명확성 : 각 명령어의 의미가 명확하여야 한다.
• 유한성 : 정해진 단계를 지나면 종료되어야 한다.
• 유효성 : 모든 명령은 실행이 가능한 연산들이어야 한다.

 

순서도

순서도

알고리즘을 표현하는 여러 방식 중 하나이다.

미리 약속된 기호와 그림을 통해 논리적 절차, 흐름, 연산 등을 시각적으로 표현한 것을 말한다.

 

순서도 도형

 

순서도 연산

1) 순서도 산술 연산

+	더하기	/	나누기
-	빼기	%, mod	나머지
*	곱하기	^	거듭제곱

◎ 나머지는 순서도에서 % 와 mod 둘 다 사용가능하지만, 프로그래밍 에서는 %만 사용 가능하다.

 

2) 순서도 관계 연산

>	크다(초과)	<	작다(미만)
>=	크거나 같다(이상)	<=	작거나 같다(이하)
=	같다	<>, ≠, !=	같지 않다(다르다)

관계 연산은 의미 그대로를 식에 대입하는 것이 중요하다.

•  A > 10 : A 가 10 보다 크다.
• A <= 7 : A 가 7보다 작거나 같다.
• 7 > 3 : 7은 3보다 크다(True)
• 3 > 7 : 3은 7보다 크다(False)

 

순서도 기초 공식

1) 변수와 상수

변수 : 고정되어 있지 않은 값 또는 어떤 값을 주기억장치에 기억하기 위해서 사용하는 공간이다.

상수 : 고정되어 있는 값 또는 이미 지정되어 있는 변하지 않는 값이다.

예를 들어 a = 10 이란, 변수 a에 정수 10을 입력하라는 의미이다.

처리 기호 안에서 =(equals)은 같다는 의미가 아닌 대입 또는 입력으로 쓰인다.

 

2)수의 증감

① 수(i)의 초기값이 설정되어 있는 경우

i = i + 1 : 수에 1을 더하겠다는 의미이다.

i = i - 1 : 수에 1을 빼겠다는 의미이다.

i = 0;
i = i + 1; <- 가능

i;
i = i + 1; <- 불가능

i의 초기값이 없는 것은 0이 아닌 Null Value(값 없음)을 의미한다.

 

② 수(i)의 초기값이 설정되어 있지 않은 경우

i = 고정값 - 변수 : 수 i에 고정된 값에서 변수를 뺀 값을 저장하겠다는 의미이다.

i = 0;
k;
i = i + 1;
k = 10 - i;

# result
# i = 1, k = 9

 

③ 합의 공식

합계 = 합계 + 수

sum = 0;
sum = sum + 1;

합계의 초기값은 기본적으로 0으로 초기화하여 합계변수에 증감변수를 이용하여 누적한다.

 

④ 평균 공식

평균(avg) = 합계(sum) / 개수(count)

# 아래는 1 부터 10 까지의 합과 평균을 구하는 코드이다.
sum = 0;
avg = 0;
i = 0;

for(i = 1; i <= 10; i++){
	sum = sum + i;
}

avg = sum / 10;

# result
# sum = 55
# avg = 5.5
# i = 10

 

⑤ 부호 변경

부호의 변경은 판단 기호를 이용하여 계산하거나 '부호 = 부호 * (-1)' 을 이용해서 연산한다.

 

⑥ 몫과 나머지

1. 몫
   • '값 / 수' 로 표현한다.
   • 결과값을 정수형으로 표현한다. (int)
   • 예시 : 4 / 2 = 2, 5 / 2 = 2
2. 나머지
   • '값 % 수' 또는 '값 mod 수' 로 표현한다.
   • 예시 : 7 % 3 = 1, 5 mod 2 = 1

 

⑦ 배열

배열은 번호에 대응하는 데이터들로 이루어진 자료 구조를 말하는데, 변수를 연속적으로 저장하기 위해 확보한 메모리 공간을 의미한다.

a[5] = a[0], a[1], a[2], a[3], a[4] 의 주소로 이루어져 있다.

프로그래밍의 배열에서의 주소값은 0부터 시작이 고정이지만, 순서도에서는 0 또는 1로 시작이 가능하다.