01. 기본 알고리즘

01-1 알고리즘이란?

 

순차적(concatenation) 구조 : 여러 문장(프로세스)이 순차적으로 실행되는 구조

선택(selection) 구조 : ( ) 안에 있는 식의 평가 결과에 따라 프로그램의 실행 흐름을 변경하는 구조

 

연산자(operation) : 프로그래밍 언어에서 연산을 수행하는 기호

피연산자(operand) : 연산의 대상이 되는 식 (변수)

연산자는 피연산자의 수에 따라 3종류로 분류된다.

1. 단항 연산자 : 피연산자 1개
2. 이항 연산자 : 피연산자 2개
3. 삼항 연산자 : 피연산자 3개

 

프로그램을 실행할 때 식이 평가된다.

식(expression) : 변수, 상수, 변수나 상수를 연산자로 결합한 것

예시	x = n + 135
변수 x, n	int 형
식	x
	n
	135
	n + 135
	x = n + 135

 

void형식의 식을 제외하고 원칙적으로 모든 수식에는 값이 있다. 값은 프로그램을 실행할 때 확인할 수 있다.

평가(evaluation) : 식의 값을 알아내는 것

      - 만약, n의 값이 52라면 각 식을 계산한 값은 52, 135, 187이 된다.  

 

여러 번 반복해서 처리해야 하는 프로그램인 경우 → 함수로 처리

함수를 정의할 때 함수에 전달되는 값을 저장하기 위해 변수(variable)를 선언하는데 이를 매개변수(parameter) 또는 형식매개변수(formal parameter)라고 한다. 

형식 매개변수를 가인수(임시 인수)라고 하고 함수를 호출할 때 사용하는 매개변수의 값을 실인수라고 한다. 

간단하게 함수를 정의할 때는 매개변수, 함수를 호출할 때는 실인수라고 생각하면 된다. 

int max3 (int a, int b, int c) { } //가인수 (매개변수)

int main() {
	max3(3, 2, 1); //실인수
}

 

→ 알고리즘 : 문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합

만약 변수의 값에 따라 결과가 맞기도 하고 틀리기도 한다면 올바른 알고리즘이라 할 수 없다. 

 

함수는 return문에서 처리한 결과값을 원래 호출한 곳으로 반환한다.

만약, 함수를 int 형으로 선언했다면 return 되는 변수는 int형으로 반환된다. 다만 반환값의 자료형이 void인 함수는 값을 반환하지 않는다. 

 

ex) 세 값의 대소 관계와 13종류 모든 조합에 대해 중앙값 구하기 > 퀵정렬 사용 

* 결정 트리 (Decision tree) : 왼쪽 끝에서 시작하여 오른쪽으로 이동하며 조건이 성립하면 윗가지로, 성립하지 않으면 아랫가지로 이동한다. 

 

중앙값을 구하는 다른 함수

→ b >= a 및 b <= a 의 조건문을 뒤집은 판단이 다음 else if ((a > b && c < b) || (a < b && c > b) 식이기 때문에 

첫번째 if 문이 성립되지 않을 경우 두 번째 if문에서도 같은 판단을 하게 되어 효율성이 떨어지게 된다. 

if ((b >= a && c <= a) || (b <= a && c >= a))
	return a;
else if ((a > b && c < b) || (a < b && c > b))
	return b;
return c;

 

조건 판단과 분기

if (n > 0)
	printf("이 수는 양수입니다.\n");
else if(n < 0)
	printf("이 수는 음수입니다.\n");
else
	printf("이 수는 0입니다.\n");

if (n > 0)
	printf("이 수는 양수입니다.\n");
else if(n < 0)
	printf("이 수는 음수입니다.\n");
else if(n == 0)
	printf("이 수는 0입니다.\n");

두 가지 분기는 비슷해보이지만 다르다. 

• 첫 번째 분기는 양수나 음수가 아닌 다른 수가 들어오면 모두 else문에서 처리하므로 3개의 분기로 나누어졌지만
• 두 번째 분기는 양수나 음수, 0 이외에 다른 수가 들어올 경우의 분기도 생각해야 하기 때문에 4개의 분기를 가진다.
  즉, 두 번째 분기는 밑에 else 문이 있는 것과 다름없다. 

 

조건 연산자 (Conditional operator)

• 3개의 피연산자(operand)를 갖는 3항 연산자 ? : 
• 식1 ? 식2 : 식3
• ex) min = a < b ? a : b;

 

순서도의 기호

• 프로그램 순서도(program flowchart)에서 사용하는 기호 

데이터 (data)	데이터(data)의 입력과 출력을 나타낸다.
처리 (process)	여러 종류의 처리 기능 수행
미리 정의한 처리 (predefined process)	서브 루틴 및 모듈 등 다른 곳에서 미리 정의한 하나 이상의 연산 또는 명령어들로 이루어진 처리
판단 (decision)	하나의 입구와 한 이상을 선택할 수 있는 출구가 있고 기호에서 정의한 조건을 평가하여 하나의 출구를 선택하는 판단 기능 → 주로 예상되는 평가 결과의 경로를 선 가까이에 쓴다.
루프 범위 (loop limit)	두 부분으로 구성되어 루프의 시작과 종료를 나타낸다. 기호의 두 부분에는 같은 이름(루프에 대한 임의 이름)을 사용한다.  루프의 시작 기호(반복 전에 판단하는 경우) 또는 종료 기호(반복 후에 판단하는 경우) 안에 초깃값(초기화), 증갓값, 종료값(종료 조건)을 표기한다.
선 (line)	제어의 흐름을 나타낸다. 흐름의 방향을 분명히 나타내고자 할 때 화살표를 붙인다.  순서도에 작성할 때는 보기 쉽게 화살표를 붙이기도 한다.
단말 (terminator)	외부 환경으로 나가거나 외부 환경에서 들어오는 것을 나타낸다. ex) 프로그램 흐름의 시작과 종료

 

01-2 반복

 

while문 반복

• 실행 전에 반복을 계속할지 판단하는데, 이런 구조를  '사전 판단 반복 구조'라고 부른다.
• 제어식의 평가값이 0이 아니면 프로그램 명령문은 반복된다. 
• 하나의 변수를 사용하는 반복문은 while문 보다 for문을 사용하는 것이 좋다. 

do문 while(제어식);

• do문은 일단 루프 본문을 한 번 실행한 다음 계속 반복할 것인지 판단하는 사후 판단 반복문이다. 
• while문과 마찬가지로 ( ) 안의 제어식을 평가한 값이 0이 아니라면 루프 본문의 명령문이 반복된다. 

→ 반복의 종료 조건을 아래쪽 루프 끝에 쓰는 순서도는 사전 판단 반복과 구별이 어렵기 때문에 do-while문 보다 while문을 더 많이 쓴다. 

 

사전 판단 반복과 사후 판단 반복의 차이점

• 사전 판단 반복문 (while, for문) : 처음에 제어식을 평가한 결과가 0이면 루프 본문은 한 번도 실행되지 않는다.
• 사후 판단 반복문 (do-while) : 루프 본문이 반드시 한 번 실행된다. 

 

구조적 프로그래밍(structured programming)

• 하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법
• 구조적 프로그래밍은 순차, 선택, 반복 3종류의 제어 흐름을 사용한다. 

 

단축평가(short circuit evaluation)

• 논리연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우, 오른쪽 피연산자의 평가는 수행하지 않는다.
• 논리합 (||)의 경우: 첫번째 연산의 결과가 1이라면 이미 T라는 결과가 나왔으므로 두번째 연산은 수행하지 않는다. 
• 논리곱(&&)의 경우 : 첫번째 연산의 결과가 0이라면 이미 F라는 결과가 나왔으므로 두번째 연산은 수행하지 않는다. 

 

드모르간 법칙(De Morgan's laws)

: 각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다는 법칙

x && y는 !(!x || !y)와 동일하다.

x || y는 !(!x && !y)와 동일하다.

no < 10 || no > 99 는 !(no >= 10 && no <= 99)와 동일하다.

계속 진행하는 조건을 종료 조건으로 바꾸는 것.

* 논리 부정 연산자와는 다르다. 논리부정연산자는 피연산자가 0이 아니면 0을, 0이면 1을 만드는 단항 연산자이다. 

 

다중루프 

• 반복 안에서 다시 반복한다. 
• 루프가 중첩되는 수준에 따라 이중 루프, 삼중 루프 라고 한다.