[2023 정보처리기사] 2과목 – 16. 알고리즘, Mccabe 순환 복잡도

1. 알고리즘

: 주어진 과제를 해결하기 위한 방법과 절차. 자연어, 의사코드, 순서도, 프로그래밍 언어를 이용하여 표현.

  1. 1. 알고리즘 설계 기법 ★

• 분할 정복법(Divide & Conquer): 제시된 문제를 분할이 불가할 때까지 나누고, 각 과제를 풀면서 다시 병합.
• 동적 계획법(Dynamic Programming): 부분 문제로 분리 후 가장 낮은 단계의 부분문제의 답을 계산. 이후 답을 계속적으로 활용.
• 탐욕법(Greedy Method): 국소적인 관점에서 최적의 해결 방법을 구하는 기법.
• 퇴각 검색법(Back Tracking): 어떤 문제의 최적해를 구하기 위해 모든 가능성을 찾음.
• 분기 한정법(Branch & Bound): 정해진 범위(Bound)를 벗어나는 값을은 가지치기(Branch)해가며 결과값을 추적.
• 근사 해법(Approxximation): 복잡도가 매우 높은 문제에 대해 가장 근사치의 값을 구하는 기법.

2. Mccabe 순환 복잡도(Cyclomatic)

  2. 1. 순환 복잡도

: 프로그램의 이해 난이도는 제어 흐름 난이도의 복잡도에 따라 결정되며 복잡도를 Cyclomatic개수에 의해서 산정하는 방법.

  2. 2. 복잡도 계산 방식 ★

– 복잡도 = 화살표 수 – 노드 수 + 2(제어 흐름 그래프를 통해 파악)

Ex)

– 복잡도: 화살표 수(6) – 노드 수(4) +2 = 6-4+2 = 4