Post

소프트웨어 개발 - 알고리즘

Posted Updated
By hyemin 10 min read

#애플리케이션 성능 - 알고리즘

문제를 해결하기 위한 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 기법

■ 알고리즘 특성

  • 입력
  • 출력
  • 명확성
  • 유한성
  • 유효성

알고리즘 기법

  • 분할과 정복 (Divide and Conquer)
  • 동적계획법 (Dynamic Programming)
  • 탐욕법 (Greedy)
  • 백트래킹 (backtracking)

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

O(1)

  • 자료 크기와 무관하게 항상 같은 속도로 작동
  • 해시함수

O(log₂n)

  • 문제를 해결하기 위한 단계 수가 log₂n번만큼의 수행 시간을 가짐
  • 이진 탐색

O(n)

  • 선형 복잡도
  • 차례대로 하나씩 모두 처리
  • 수행 시간이 자료 크기와 정비례
  • 순차 탐색

O(nlog₂n)

  • 문제를 해결하기 위한 단계의 수가 nlog₂n번만큼의 수행 시간을 가짐
  • 퀵 / 합병 / 힙 정렬

O(n²)

  • 주요 처리 루프 구조가 2중인 경우의 복잡도
  • 거품 / 삽입 / 선택 정렬

해싱함수

데이터를 키로 변환하는 함수

해싱 함수 선택 시 고려해야할 점

  • 계산과정의 단순화
  • 충돌의 최소화
  • 기억장소 낭비의 최소화
  • 오버플로우의 최소화 (더 이상 저장할 곳이 없는 상태)

해싱 함수 종류

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

검색 알고리즘

■ 순차검색 (Sequential Search)

배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘

장점:

  • 가장 단순하여 구현이 쉬움
  • 정렬되지 않은 리스트에서도 사용 가능

단점:

  • 검색할 리스트의 길이가 길면 비효율적임

■ 이진 검색 (Binary Search)

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘

가운데 레코드 번호 찾는 식
(첫번째 레코드 번호 + 마지막 레코드 번호) / 2

장점:

  • 탐색 효율이 좋고 탐색 시간이 적게 소요됨

정렬 알고리즘

■ 퀵 정렬 (Quick Sort)

피벗을 두고 피벗 왼쪽에는 피벗보다 작은 값을 오른쪽에는 큰 값을 두는 과정을 반복하는 알고리즘
(많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬)

■ 합병 정렬 (Merge Sort)

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 합병하여 정렬하는 알고리즘

■ 힙 정렬 (Heap Sort)

힙을 구성하고 가장 큰 키 값을 갖는 루트 로드를 제거하는 과정을 반복하여 정렬하는 알고리즘
완전이진 트리로 입력 자료의 레코드를 구성

■ 거품 정렬 (Bubble Sort)

인접한 2개의 레코드 키값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 알고리즘
PASS를 요소의 개수 -1번 수행하게 되면 모든 숫자가 정렬됨

■ 삽입 정렬 (Insertion Sort)

n번째 키를 앞의 (n-1)개 키와 비교하여 알맞은 순서에 삽입하는 알고리즘

■ 선택 정렬 (Selection Sort)

정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 정렬되지 않은 부분의 가장 앞의 데이터와 교환해나가는 알고리즘

소스 코드 품질 분석

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

■ 소스 코드 품질 분석

정적 분석 도구:
작성된 코드를 실행시키지 않고 코드 자체만으로 코딩 표준 준수 여부, 코딩 스타일 적정 여부, 잔존 결함 발견 여부를 확인하는 코드 분석 도구

  • pmd
  • cppcheck
  • sonarQube
  • checkstyle
  • ccm
  • cobertura

동적 분석 도구:
애플리케이션을 실행하여 코드에 존재하는 메모리 누수 현황을 발견하고, 발생한 스레드의 결함 등을 분석하기 위한 도구

  • Avalanche
  • Valgrind

■ 소스 코드 복잡도 분석 - 맥케이브 회전 복잡도

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

특징:

  • 정향적 지표
  • 구조적 평가
  • 간접 방식

복잡도측정 방식:

  • V = E - N + 2: 노드(N)와 간선(E) 수로 계산
  • V = P + 1: 조건 분기문(P)의 수로 계산

코드 최적화

읽기 쉽고 변경 및 추가가 쉬운 클린 코드를 작성하는 것

클린 코드

  • 중복 코드 제거로 애플리케이션 설계가 개선됨
  • 가독성이 높기때문에 애플리케이션의 기능에 대해 쉽게 이해할 수 있음
  • 버그를 찾기 쉬워짐
  • 프로그래밍 속도가 빨라짐

클린 코드 작성 원칙

  • 가독성
  • 단순성
  • 의존성 최소
  • 중복성 제거
  • 추상화

나쁜 코드

다른 개발자가 로직을 이해하기 어렵게 작성된 코드

  • 오염
    • 비즈니스 기능 을 수행하지 못하는 많은 컴포넌트들이 존재
  • 문서부족
    • 현재 코드와 문서가 일치하지 않고 수정과 변경을 위한 도메인 지식은 크게 증가하지만 개발자의 지식 부족
  • 의미 없는 이름
    • 명확한 의미를 갖지 못하거나 실제 작동과 불일치
  • 높은 결합도
    • 클래스와 컴포넌트 간에 데이터와 컨트롤 흐름이 네트워크로 복잡하게 연결
  • 아키텍처 침식
    • 구별되지 않고 여러 솔루션으로 이루어져 아키텍처 상 변형들로 인해 시스템 품질이 떨어짐
  • 외계인 코드
    • 매우 오래되거나 참고 문서 또는 개발자가 없어 유지보수가 어려운 코드
  • 스파게티 코드
    • 작동은 정상적으로 하지만 사람이 코드를 읽으면서 그 코드의 작동을 파악하기는 어려운 코드
  • 알 수 없는 변수명
    • 변수나 메서드에 대한 이름 정의를 알 수 없는 코드
  • 로직 중복
    • 동일한 처리 로직이 중복되게 작성된 코드
정보처리기사, 소프트웨어개발
정보처리기사
This post is licensed under CC BY 4.0 by the author.