알고리즘과 순서도

컴퓨터를 이용한 문제 해결 4단계

1 단계: 주어진 문제를 정확하게 이해, 분석하기

2 단계: 분석한 문제를 해결하기 위한 가장 좋은 방안 (=알고리즘) 구상

3 단계: 알고리즘을 컴퓨터가 알아들을 수 있는 방법으로 표현하여 수행하도록 지시

4 단계: 실행하여 출력, 잘못 작성된 경우 3단계 프로그래밍을 반복 ... 검증(=디버깅)

*디버깅: 원래는 프로그램을 대상으로 실시하지만, 2단계 알고리즘의 오류를 검증할 때도 같은 용어를 사용한다. 디버깅 작업을 할 때 표(Table)를 사용하는데 이를 디버깅 표(Debugging Table)라고 부른다

 

순서도 : 알고리즘을 표현하는 여러 방식 중에 순서도(Flowchart)를 가장 많이 사용한다. 

- 장점: 구조를 한눈에 파악하기 쉽다.

- 좋은 알고리즘: 정확도, 시간과 공간의 활용(빠르고 저장공간이 작아야됨) CPU, memory storage 등 적게 쓰는 알고리즘

 

- 순서도의 기본 개념

- 순서도 작성법

● 순서도는 시작 기호에서 출발하여 완료 기호로 마친다

○ 시작 기호 안에는 알고리즘 이름을 기록하기도 한다

● 기호와 기호 사이의 흐름선으로 연결하여 작업의 흐름을 명시한다

● 흐름선의 방향은 가급적 위에서 아래로, 왼쪽에서 오른쪽으로 향하도록 한다

○ 반복 구조 등 특별한 경우 예외

● 흐름선은 가급적 교차되지 않도록 하여 혼동을 피한다

○ 둘 이상의 흐름선이 합류되어야 하는 경우에는 결합 기호를 사용한다

● 값을 보관하고 처리하기 위하여 적절한 변수를 사용한다

● 같은 종류의 여러 값들을 한꺼번에 보관하고 처리하기 위해서는 배열 변수를 사용한다

 

- 순서도를 구성하는 3대 기본 구조

● 직선 구조 : 흐름선을 따라 위에서 아래로 차례대로 작업을 진행하는 구조

● 분기 구조 : 조건 기호에 대한 검사 결과에 따라 진행할 다음 작업이 달라지는 구조

● 반복 구조 

  ○  선처리 후검사

  ○  선검사 후처리 

 

변수와 배열

-변수

● 변수는 순서도에서 값을 보관하여 처리하기 위한 장소이다. 

● 모든 변수는 컴퓨터상에서 메모리 공간이 할당된다. 

- 변수와 배정문

● 순서도의 처리 기호를 통하여 변수에 값을 배정하거나 변경할 수 있다. 

-배열 변수와 준비 기호

배열 변수는 같은 종류의 값들을 메모리 공간 안에 연속적으로 보관하여 처리하기 위한 장소를 말한다. 

*배열 변수의 선언 : ENG(100) → ENG: 1차원 배열 변수의 이름, 100: 배열 변수의 원소 개수

                               SCORE(2,100) → SCORE: 2차원 배열 변수의 이름, 2: 세트 수, 100: 세트당 원소 수 ; SCORE 배열 변수의 총 원소 개수는 200개

 > 배열 변수는 순서도의 준비 기호 안에 배열 변수의 1) 차원과 2) 원소 개수 정보를 미리 선언한 후 사용

1차원 배열 변수

A(1)

A(2)

A(3)

A(4)

2차원 배열 변수

	1열	2열	3열
1행	B(1,1)	B(1,2)	B(1,3)
2행	B(2,1)	B(2,2)	B(2,3)

- 순서도 안에 등장하는 변수

● 입력 변수

● 출력 변수

● 반복 변수

● 스위치 변수

● 임시 변수

 

연산과 함수

-순서도에서 나올 수 있는 연산

1) 처리 기호 안에 나올 수 있는 산술 연산

산술 연산자	의미	사례
+	더하기	A+B
-	빼기	A-B
*	곱하기	A*B
/	나누기	A/B
%	나머지 구하기	A % B ex) 12%5=2
^	거듭제곱하기	A^2

2) 조건 기호 안에 나올 수 있는 관계 연산

관계 연산자	의미	사례
<	작다/미만	A < 10
>	크다/초과	A  > 10
=	같음	A = B
같지 않음	같지 않음	A <> B, A ≠ B
<= 또는 ≤	작거나 같음/이하	A <= 10, A ≤ 10
>= 또는 ≥	크거나 같음/이상	A >= 10, A ≥ 10

3) 조건 기호나 처리 기호에서 나올 수 있는 논리 연산(BOOL 연산)

논리 연산자	의미	사례
AND	- 둘다 TRUE이면 TRUE  - 나머지 경우는 False	(A > B) AND (A > C)
OR	- 둘 중 하나가  True이거나,     둘 중 모두가 True이면 True  - 나머지 경우는 False	(A > B) OR (A > C)
NOT	- True는 False로 바꿈  - False는 True로 바꿈	NOT (A > B)

순서도에서 나올 수 있는 함수

함수 이름	의미
ABS(X)	부호를 뺀 절대값을 계산해줌
INT(X)	X 이하인 정수 중에서 최댓값을 찾아줌
SQRT(X)	제곱근 값을 계산해줌
MOD(X,Y)	- X를 Y로 나눈 나머지를 계산해줌  - 앞의 산술 연산 %와 동일함

**나머지 함수 MOD()의 활용

 1) 어떤 자연수를 A로 나누면, 나머지는 0,1,2,....,(A-1) 중의 하나가 된다.

     ex) 어떤 자연수를 5로 나누면 나머지는 0,1,2,3,4중 하나가 된다.

  2) A를 B로 나눈 나머지를 구하는 연산을 영어로 Modulo라고 하며, MOD(A,B)로 표현한다.

     ex) 10을 4로 나눈 나머지 = MOD(10,4) = 2

  3) A를 B로 나누어 나머지가 0이 되면, A는 B의 배수, B는 A의 약수가 된다.

     ex) MOD(16,4) = 0이므로 16은 4의 배수, 4는 16의 약수이다.

  4) 어떤 수 A가 짝수이려면, MOD(A,2) = 0이어야 한다.

  5) 어떤 수 A가 홀수이려면, MOD(A,2) = 1이어야 한다.

  6) 따라서 어떤 수 A가 B의 배수이면서 동시에 C의 배수이려면, MOD(A,B)=0이면서 동시에 MOD(A,C)=0이어야한다.

     ex) 어떤 수 A가 3의 배수이면서 동시에 5의 배수이려면, MOD(A,3) + MOD(A,5) = 0

 

알고리즘 검증

https://youtu.be/G8lTntUQVxQ

-디버깅 표의 용도

● 디버깅 표는 알고리즘(순서도)이 정확하게 작성되었는지 최정적으로 검증

●  미리 컴퓨터의 반응을 예견하기 위해 사용

●  순서도의 시간에 따라 작업 수행

● 순서도에 나타난 변수들을 중심으로 검증 작업 수행