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

정보처리기사 필기 준비하며 정리한 내용입니다.

알고리즘

문제를 해결하기 위한 절차나 방법

자연어, 순서도, 의사 코드, 프로그래밍 언어 등을 이용하여 표현

조건

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

설계 기법

• 분할과 정복
  • 더는 쪼갤 수 없을 정도로 작은 문제로 나누기
• 동적 계획법
  • 더 작은 문제로 나누기
• 탐욕법
  • 가장 좋은 해결책을 그때그때 찾기
• 백트래킹
  • 더이상 해가 없으면 왔던 길 되돌아가기

 

성능 분석

• 알고리즘 효율성 높이기 위해 자원(시간과 공간)을 어떻게 소모하는가에 따른 분석

시간 복잡도

• 알고리즘의 수행시간 분석한 결과
• 빅오 표기법의 유형
  • O(1) : 오직 한단계만. 가장 빠르다
    • 스택, Hash 함수
  • O(log n)
    • 이진탐색
  • O(n)
    • 배열 순차 탐색
  • O(n log n)
    • 퀵, 힙, 병합 정렬
  • O(n^2)
    • 버블, 삽입, 선택정렬

공간복잡도

• 공간=메모리를 얼마나 효율적으로 사용하느냐

 

정렬 알고리즘

선택 정렬

• 왼쪽 첫번째 공간부터 하나씩 오른쪽과 비교해나간다

삽입정렬

• 자료가 어느정도 정렬이 되어 있으면 빠르다
• 두번째 공간부터 시작해서 왼쪽과 비교해나간다
  • 가까운 왼쪽부터!
    • step1일때는 2 - 1비교
    • step2일때는 3 - 2 → 3 - 1 비교

버블정렬

• 인접값 2개 비교
• 1회전 1-2, 2-3, 3-4, 4-5 이런 순서로 비교
  • 2회전부터 맨 끝은 이미 끝났기에 딱히 할 필요가 없어진다

퀵 정렬

최악의 경우 n^2의 값을 가지게 된다 (버블, 삽입, 선택과 동일하게)

힙 정렬

항상 O(n log n)

병합 정렬

n log n

쉘 정렬

삽입 정렬의 단점 보완

기수 정렬

분배. 버킷 → 버킷 순서대로.

 

검색 기법

• 선형 검색
  • 좌측부터 순차적으로
  • O(N)
• 이진 검색
  • 검색 반경을 반으로 나누어 반복
  • O(log N)
    • 빠르다! 정렬에서는 불가능한 속도.
• 보간 검색
  • 예측

 

 

소스코드 품질 분석 도구

정적 분석 도구

소스코드 - 내부

동적 분석 도구

실행하여 메모리 누수 등을 발견

• 종류
  • Avalanche
  • Valgrind

 

소스코드 복잡도 분석

McCabe 회전 복잡도 계산

면 + 1

 

코드 최적화

• 코드 스멜 : 좋지 않은 코드
  • 스파게티 코드
  • 외계인 코드

리팩토링

외부 동작 바꾸지 않으며 내부 개선

클린 코드

남들이 알아보기 쉬운 코드

코드의 복잡도를 낮춘다 (복잡도를 낮추려면 독립성을 높이고 응집도는 높이고 결합도는 낮추고!)

코드 중복 최소화

• 원칙 : 가독성 단순성 의존성배제 중복성최소화 추상화