탑싯_1_소프트웨어 개발_4_알고리즘

알고리즘 조건

1. 명확성: 수행할 작업의 내용과 순서를 나타내는 알고리즘의 단계가 명시되어 있어야 한다.

2. 유한성: 유한 시간 안에 수행 후 반드시 종료되어야 한다. 

3. 효과성: 실행이 가능해야 한다.

 

알고리즘 분석 기준

1. 정확성: 유한 시간 내에 올바른 결과를 산출해야 한다.

2. 작업량: 알고리즘을 수행하는데 필요한 수행 횟수가 적어야 한다

3. 기억 장소 사용량: 메모리 사용량

4. 최적성: 문제를 가장 잘 해결할 수 있는 알고리즘이어야 한다.

5. 단순성: 설명하거나 사용하기에 편해야 한다.

 

 

알고리즘 성능 분석

공간 복잡도, 시간 복잡도가 적어야 더 효과적인 알고리즘이다.

 

정렬 알고리즘

분류

내부 정렬: 주기억장치에서 정렬한다. 정렬 속도가 빠르나 양이 적다 

외부 정렬: 보조 기억 장치에서 정렬한다. 속도가 느리나 양이 많다.

 

내부 정렬

선택 정렬

1~N까지 중에 가장 큰 값을 찾아 A[N]과 바꾼다

1~N-1까지 중에 가장 큰값을 찾아 A[N-1]과 바꾼다

(반복)

 

시간 복잡도: 무조건 O(N^2)

 

버블 정렬

인접한 두 원소를 비교해 순서가 역전돼 있으면 swap한다

 

시간 복잡도: 무조건 O(N^2)

 

검색 알고리즘

 

그래프 탐색 알고리즘

1. 깊이 우선 탐색(DFS)

시작으로 부터 리프 노드까지 하나씩 찾고 없으면 부모 노드로 돌아간다. 후입선출의 Stack 형태이다. 시작 노드에서 목표노드까지의 가장 짧은 거리를 구할 수 있다. 저장 공간의 수요가 적고 목표노드가 깊은 단계에 있는 경우 빨리 찾을 수 있다.

2. 너비 우선 탐색(BFS)

하나의 시작 노드를 방문하고 인접한 노드를 먼저 탐색하는 방법이다. Queue 형태!

 

최소 신장 트리

가중치가 있는 그래프에서 모든 정점을 지나는 사이클이 없는 하나의 경로를 구하는 방식이다.

 

크루스칼

 정점과 연결된 간선 가운데 가중치가 최소인 간선을 선택한다! 그 후 그래프에 사이클이 있으면 선택한 간선을 제거한다.

프림

 임의의 한 정점을 선택해 선택되지 않은 정점 중 가장 가중치가 적은 간선을 선택한다.