알고리즘(Algorithm)

(1) 알고리즘

1. 알고리즘이란

- 알고리즘은 어떠한 문제를 해결하기 위한 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 기법

 

2. 알고리즘 기법

▼  알고리즘 기법

기법	설명
분할과 정복	문제를 나눌 수 없을 때까지 나누고 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘
동적계획법	어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘
탐욕법	결정을 해야할 때마다 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방식의 알고리즘
백트래킹	어떤 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손노드를 검색하는 알고리즘

 

▼ 시간 복잡도에 따른 알고리즘 분류

• O(1) -> 상수형 복잡도, 자료 크기 무관하게 항상 같은 속도로 작동, 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정함 -> 해시 함수
• O(log2n) -> 로그형 복잡도, 문제를 해결하기 위한 단계의 수가 log2n번만큼의 수행 시간을 가짐 -> 이진 탐색
• O(n) -> 선형 복잡도, 입력 자료를 차례로 하나씩 모두 처리, 수행 시간이 자료 크기와 직접적 관계로 변함(정비례) -> 순차 탐색
• O(nlog2n) -> 선형 로그형 복잡도, 문제를 해결하기 위한 단계이 수가 nlog2n번만큼의 수행 시간을 가짐 -> 퀵 정렬, 합병 정렬, 힙 정렬
• O(n2) -> 제곱형 주요 처리 루프 구조가 2중인 경우, n크기 작을 때는 n2이 nlog2n보다 빠를 수 있음 -> 거품 정렬, 삽입 정렬 ,선택 정렬

3. 알고리즘 설명

[1] 해싱함수 

- 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

 

• 제산법 : 나머지 연산자를 사용하여 테이블 주소를 계산하는 방식
• 제곱법 : 레코드 키값을 제곱한 후에 결과값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용하는 방식
• 숫자 분석법 : 레코드 키를 구성하는 수들이 자리별로 어떤 분포인지를 조사한 후에 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법
• 폴딩법 : 레코드 키를 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR 한 값을 홈 주소로 사용하는 방식
• 기수변환법 : 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방식
• 무작위방법 : 난수를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방식

[2] 검색 알고리즘

1. 순차 검색 : 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘
2. 이진 검색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘

[3] 정렬 알고리즘

• 퀵 정렬 : 피벗을 두고 피벗의 왼쪽에는 피벗보다 작은 값을 오른쪽에는 큰 값을 두는 과정을 반복
• 합병 정렬 : 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 합병해서 정렬하는 알고리즘
• 힙 정렬 : 정렬할 입력 레코드들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬
• 거품 정렬 : 인접한 2개의 레코드 키값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 알고리즘
• 삽입 정렬 : 2번째 키와 첫번째 키를 비교하여 순서대로 나열하고, 이어서 3번째 키를 1,2번째 키와 비교해 순서대로 나열하고, 계속해서 n번째 키를 앞의 (n-1)개 키와 비교하여 알맞은 순서에 삽입하는 알고리즘
• 선택 정렬 : 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 정렬되지 않은 부분의 가장 앞의 데이터와 교환해나가는 알고리즘

 

(2) 소스 코드 품질 분석

1. 소스 코드 품질 분석이란

- 소스 코드에 대한 코딩 스타일, 설정된 코딩 표준, 코드의 복잡도, 코드 내에 존재하는 메모리 누수 현황, 스레드의 결함 등을 발견하기 위한 활동이다. 

 

▼  소스 코드 품질 분석 도구 유형

• 정적 분석 도구 : 작성된 소스 코드를 실행시키지 않고 코드 자체만으로 분석하는 도구(pmd, cppcheck, SonarQube, checkstyle, ccm, cobertura 
• 동적 분석 도구 : 애플리케이션을 실행하여 코드에 존재하는 메모리 누수 현황을 발견하고 스레드의 결함 등을 분석(Avalanche, Valgrind)

2. 소스 코드 복잡도 분석

① 맥케이브 회전 복잡도 : 소프트웨어의 제어 흐름을 그래프로 표현하고 소스코드의 복잡도를 정량적으로 나타내는 지표

- 특징은 정량적 지표가 가능하고 구조적으로 평가하여 효율, 가능성, 품질 등을 간접적으로 측정하는 데 유용하다. 

 

▼  맥케이브 회적 복잡도 측정 방식

• V(G) = E - N +2 -> 복잡도V(G)는 노드(N) 수와 간선(E) 수로 계산
• V(G) = P + 1 -> 복잡도V(G)는 조건 분기문(P)의 수로 계산

 

(3) 코드 최적화

- 읽기 쉽고 변경 및 추가가 쉬운 클린 코드를 작성하는 것으로, 소스 코드 품질을 위한 가장 기본이다. 

- 그 중에서도 클린 코드는 가독성이 높고, 단순하며, 의존성을 줄이고, 중복을 최소화하여 깔끔하게 잘 정리된 코드다. 

 

▼ 클린 코드의 작성 원칙

- 가독성 : 이해하기 쉬운 용어를 사용, 들여쓰기도 해야 함

- 단순성 : 한 번에 한 가지 처리만 수행 

- 의존성 최소 : 영향도를 최소화

- 중복성 제거 : 중복된 코드를 제거, 공통된 코드를 사용

- 추상화 : 클래스/메소드/함수에 대해 동일한 수준의 추상화 구현