정보처리기사 :알고리즘 과 소스코드 분석도구 완전 정복!!

알고리즘

문제를 해결하는 방법,제시된 문제를 논리적으로 해결하는 절차

표현방법 : 자연어,순서도,의사코드,프로그래밍 언어등

 

알고리즘의 조건

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

기법

	설명
분할과 정복(Divde & Conquer)	문제를 더 작은 문제로 나눠 해결
동적 계획법(Dynamic Program)	큰문제를 나누어 해결하며 중복계산 방지 작은 문제들에서 구한 해를 활용해 해결
탐욕법 (Greedy)	- 그때그때 가장 좋은 선택을 하는 방법
백트래킹 (Backtracking)	- 해가 없으면 이전 단계로 돌아가 다른 선택을 하는 방법

 

알고리즘 성능 분석

① 시간 복잡도

• 알고리즘 수행 시간의 분석 결과
• 표기법 : 빅오,빅오메가,빅세타
• 빅오 표기법 유형.

② 공간 복잡도

• 알고리즘 수행 종료까지 필요한 메모리 공간량
• 주로 변수저장을 위한 공간 관련

 

정렬 알고리즘( N제곱의 시간 복잡도 )

N제곱의 시간 복잡도를 가짐(검색시 최대  64번 찾음)

① 선택정렬(Selection Sort)

• 리스트중 최소값을 찾아 비교대상과 교체
• 비교횟수는 많지만 실제 교환 횟수는 적다

요약: 내순서에 가장 작은놈이랑 비교 

초기상태 9,6,3,75 일경우

1회전에서 최소값을 맨 앞으로 그러니 3,9,6,7,5

2회전에선 아까 옮기거 뺴고 최소값을 앞으로 3,5,9,6,7

3회전에선 아까 옮기것들 뺴고 최소값을 앞으로 3,5,6,9,7

② 삽입 정렬(Insertion Sort)

• 현재값이 삽입될 자리를 찾아 삽입하는 방식
• 자료가 부분적으로 정렬되어 있으면 빠르게 동작한다

요약: 내순서 +1 놈이랑 그앞에 놈이랑 비교

초기상태 5,1,2,3,-2,6 일경우

 

1회전 첫번쨰가 아니라 두번쨰값을 그 앞에놈이랑 비교해서 (1앞에는 5니까 5랑비교) 두번쨰 값이 더 적으면 앞으로 이동

 = 1,5,2,3,-2,6

2회전 세번쨰놈을 꺼내서 그전놈이랑 비교 (2랑 그전놈인 5랑 비교 2가 더 작으니 앞으로)

= 1,2,5,3,-2,6

3회전 네번쨰놈이랑 세번쨰놈을 비교 

= 1,2,3,5,-2,6

4회전 다섯번쨰놈이랑 네번쨰놈을 비교  근데 이경우 -2로 첫번쨰 두번쨰 세번쨰 네번쨰 놈보다 작으니 그앞으로 이동

= -2,1,2,3,5,6

 

③ 버블(Bubble Sort)

• 인접한값끼리 비교
• 모든 인접값 비교해야해서 비효율

요약: 인접한 놈들끼리 비교

초기상태 7 4 11 9 2

1회전

맨앞 7이랑 4를 비교  순서변경 4 7 11 9 2

그후 7이랑 11을 비교  7이 작네? 순서변경없음

그후 11이랑 9 를 비교 9가 더작네?  순서변경 4 7 9 11 2

그후 11이랑 2를 비교 순서변경 4 7 9 2 11

1회전 끝남 , 1회전 끝나면 맨뒤놈은 정렬 된거라 그냥 놔둠

 

2회전

4 7 9 2 11에서 시작

4랑7비교

7과9비교

9와 2 비교  순서변경 4 7 2 9 11

2회전이니 맨마지막은 끝났으므로 비교안함

고로 4 7 2 9 11 마무리

이제 9도 비교 안함

.....

 

⑦ 쉘 정렬(Shell Sort)

• 삽입 정렬의 단점을 개선하여 만든 알고리즘

정렬 알고리즘( N⋅logN  시간도)

N⋅logN 의 시간 복잡도 (검색시 최대  24번 찾음)

④ 퀵정렬(Quick Sort)

• 피벗을 사용해 분할하면서 정렬
• 일반적으로 O(n log n)의 시간 복잡도
• 최악의 경우 n제곱 시간도를 가질수도 있음

⑤ 힙정렬(Heap Sort)

• 추가 메모리를 사용하지않음
•  O(n log n)의 시간 복잡도

⑥ 병합정렬(Merge Sort)

• 배열을 반으로 분할하여 정렬
• 추가메모리 필요

--

⑧ 기수정렬(Radix Sort)

• 분배 방식의 정렬
• 키 값에 따른 버킷에 원소를 분배하고 순서대로 꺼내어 정렬
• 시간복잡도는 O(nw)

 

검색기법

	설명
① 선형 검색 (Linear Search)	배열의 좌측부터 시작하여 순차적으로 각 요소를 비교하여 검색 시간 복잡도: O(N)
② 이진 검색 (Binary Search)	검색 범위를 반으로 줄여가며 검색하는 방법 주어진 배열은 정렬되어 있어야 함 중간 값과 찾으려는 값을 비교하여 검색 범위를 좌측 또는 우측으로 좁혀나감 시간 복잡도: O(log N)
③ 보간 검색 (Interpolation Search)	이미 정렬된 리스트에서 검색 값이 있을 법한 위치를 예측하여 검색
④ 해시 검색 (Hashing)	해시 테이블을 사용하여 데이터의 저장 위치를 빠르게 찾아 검색하는 방식 시간 복잡도: 평균적으로 O(1), 최악의 경우 O(N)
⑤ 이진 트리 검색 (Binary Tree Search)	이진 트리 구조를 사용하여 검색 범위를 줄여 나가며 검색하는 방법 시간 복잡도: 평균 O(log N), 최악의 경우 O(N)
⑥ 블록 검색 (Block Search)	배열을 여러 블록으로 나눈 후, 각 블록의 최댓값을 추출하여 찾고자 하는 값의 위치 블록을 파악한 뒤, 해당 블록 내에서 선형 검색을 수행하는 방법

 

 

소스코드 품질분석 도구

코딩중 발생하는 다양한 문제를 탐지하고 해결하는 도구

스타일,표준,복잡도,메모리누수,스레드 결합등 검사

 

 

분류

① 정적 분석도구

• 프로그램 실행 없이 코드분석
• PMD,CheckStyle,SonarQube,CCM,Cppcheck,Cobertura

② 동적 분석도구

• 프로그램 실행 도중 메모리 누수나 스레드 결함 검사
• Avalanche,Valgrind

 

 

McCabe 회전복잡도 계산

① 면만 찾아서 계산해서 +1 해라

 

면이 보이는부분 빨간 부분 3개 +1 총 4

파란부분은 밖으로 나가서 체크 안함