알고리즘
1. 알고리즘의 이해
정의
알고리즘은 "문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서"입니다.
프로그램과의 관계
프로그램은 자료구조(data structure) 와 알고리즘(algorithm) 으로 구성됩니다.
알고리즘의 조건
효과적인 알고리즘이 되기 위해서는 다음 5가지 조건을 충족해야 합니다.
| 조건 | 설명 |
|---|---|
| 입력(input) | 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공되어야 함 |
| 출력(output) | 알고리즘 수행 후 하나 이상의 결과를 출력해야 함 |
| 명확성(definiteness) | 수행할 작업의 내용과 순서가 명확하게 명세되어야 함 |
| 유한성(finiteness) | 알고리즘은 수행 뒤에 반드시 종료되어야 함 |
| 효과성(effectiveness) | 알고리즘의 모든 명령어는 기본적이며 실행 가능해야 함 |
올바른 알고리즘
"어떠한 경우에도 실행 결과가 똑같이 나오는 것"을 의미합니다. 만약 실행 결과가 경우에 따라 맞거나 틀리면 올바른 알고리즘이라고 할 수 없습니다.
학습 목표: 알고리즘의 개념을 이해하고, 알고리즘의 표현 방법을 설명할 수 있으며, 성능 분석 방법을 설명하고, 간단한 프로그램을 통해 알고리즘을 이해하고 정의 등을 설명할 수 있습니다.
2. 알고리즘의 표현 방법
알고리즘은 다양한 방법으로 표현될 수 있으며, 주요 방법은 다음과 같습니다.
2.1 자연어를 이용한 서술적 표현 방법
일상 언어로 알고리즘을 설명합니다.
예시: 딸기 시럽 치즈케이크 만들기
2.2 순서도(flow chart)를 이용한 도식화 표현 방법
문제에 대한 정의, 분석, 해법을 그림으로 표현합니다.
순서도에는 다음과 같은 다양한 기호가 사용됩니다:
- 데이터, 처리, 미리 정의한 처리, 판단, 선, 단말, 루프 범위 등
예시: 1부터 5까지의 합을 구하는 알고리즘 순서도
2.3 프로그래밍 언어를 이용한 구체화 방법
특정 프로그래밍 언어로 직접 코드를 작성합니다.
2.4 가상코드(pseudo-code)를 이용한 추상화 방법
프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘을 표현하지만, 특정 언어는 아니므로 직접 실행은 불가능합니다. 특정 프로그래밍 언어로의 변환이 용이합니다.
기본 요소
- 변수, 자료형(정수형, 실수형, 문자형 등), 연산자(산술, 관계, 논리) 등을 사용
지정문 형식
변수 <- 값; (예: a <- 5;)
제어 구조
알고리즘의 흐름을 제어하는 방식입니다.
조건문
조건에 따라 실행할 명령문이 결정되는 선택적 제어 구조입니다.
if-then-else형,if-then형- 다단계 조건문, 중첩 if문
- case문: 여러 조건식 중 해당 조건을 찾아 명령문을 수행하며, 중첩 if문으로 표현 가능
반복문(loop)
일정한 명령을 반복 수행하는 제어 구조입니다.
반복문의 종류:
for (초깃값; 조건식; 증감값) do 명령문;
while (조건식) do 명령문;
do 명령문; while (조건식);
반복문의 특징:
- 사전 판단 반복 (
while,for): 실행 전에 반복 여부를 판단하며, 제어식 결과가 0이면 루프 본문이 한 번도 실행되지 않을 수 있음 - 사후 판단 반복 (
do-while): 루프 본문을 한 번 실행한 다음에 반복 여부를 판단하며, 루프 본문이 적어도 한 번은 실행됨 - 다중 루프: 반복문 안에 다시 반복문이 중첩되는 구조 (이중 루프, 삼중 루프 등)
함수문
처리 작업을 별도 모듈화하여 만든 부프로그램입니다.
함수 이름(매개변수)
명령문;
...
return 결괏값;
end
3. 알고리즘의 성능 분석
알고리즘의 성능을 분석하는 기준과 방법은 다음과 같습니다.
3.1 성능 분석 기준
| 기준 | 설명 |
|---|---|
| 정확성 | 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부 |
| 명확성 | 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는지 여부 |
| 수행량 | 일반적인 연산을 제외하고, 알고리즘의 특성을 나타내는 중요 연산 모두 분석 |
| 메모리 사용량 | 알고리즘이 실행되는 동안 필요한 메모리 양 측정 |
| 최적성 | 시간 복잡도와 공간 복잡도 |
3.2 성능 분석 방법
공간 복잡도
"알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양"을 나타냅니다.
공간 복잡도 = 고정 공간 + 가변 공간
시간 복잡도
"알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간"을 나타냅니다.
시간 복잡도 = 컴파일 시간 + 실행 시간
참고: 컴파일 시간은 거의 고정적이므로, 실행 시간을 주로 분석합니다. 실행 시간은 컴퓨터 성능에 따라 달라질 수 있어, 실제 실행 시간보다는 명령문의 실행 빈도수에 따라 계산합니다.
기본 명령문: 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행 시간 차이가 거의 없으므로 하나의 단위 시간을 갖는 기본 명령문으로 취급합니다.
3.3 표기법 (점근적 표기법)
알고리즘의 성능을 나타내는 수학적 표기법입니다.
빅-오 표기법 (Big-O Notation)
O(f(n))으로 표기하며, 함수의 상한을 나타냅니다.
의미: "최악의 경우에도 g(n)의 수행 시간 안에는 알고리즘 수행 완료 보장"
표기 방법: 실행 시간 함수에서 가장 큰 영향을 주는 n에 대한 항을 하나 선택하고 계수를 생략하여 표기합니다.
예시: 피보나치 수열 실행 시간 함수
4n+2는O(n)으로 표기
빅-오메가 표기법 (Big-Omega Notation)
Ω(f(n))으로 표기하며, 함수의 하한을 나타냅니다.
의미: "어떤 알고리즘의 시간 복잡도가 Ω(g(n))으로 분석되었다면, 이 알고리즘 수행에는 적어도 g(n)의 수행 시간이 필요함"
빅-세타 표기법 (Big-Theta Notation)
θ(f(n))으로 표기하며, 상한과 하한이 같은 정확한 차수를 표현하기 위한 표기법입니다.
조건: f(n)= θ(g(n))이 되려면 f(n)= O(g(n))이면서 f(n)= Ω(g(n))이어야 합니다.
3.4 n값 변화에 따른 실행 빈도수 및 수행 시간 비교
각 실행 시간 함수에서 n값의 변화에 따른 실행 빈도수와 알고리즘 수행 시간을 비교하여 효율성을 분석할 수 있습니다.
4. 알고리즘 실습 예시
4.1 기본 구조 활용
세 정수의 최댓값 구하기
순차 구조와 선택 구조를 활용하여 세 정수 중 최댓값을 찾는 프로그램입니다.
조건 판단과 분기 학습
입력한 정숫값의 부호(양수/음수/0)를 판단하여 출력하는 프로그램으로, 프로그램 흐름이 여러 가지로 분기되는 것을 학습합니다.
4.2 반복 구조 학습
1부터 n까지 정수의 합 구하기
while문과 for문을 사용하여 반복 구조를 학습합니다.
양수만 입력받기
do-while문을 사용하여 사후 판단 반복을 학습합니다.
4.3 다중 루프
구구단 곱셈표 출력
이중 루프의 개념을 학습하는 프로그램입니다.
왼쪽 아래 직각 이등변 삼각형 출력
이중 루프를 활용한 도형 출력 프로그램을 통해 다중 반복문의 개념을 학습합니다.
💡 핵심 포인트: 알고리즘 학습에서는 다양한 제어 구조(순차, 선택, 반복)를 조합하여 복잡한 문제를 해결하는 능력을 기르는 것이 중요합니다.