[알고리즘] 4주차 내용 초압축

# Brute-force 전략

 

Brute-force

- 문제 정의에 따라, 가능한 모든 경우를 시도하는 방법 == 문제정의에 기반한 가장 직접적인 접근 방식, Naive Method

 

중요성

1. 해결보장: 반드시 해를 찾아낸다

2. 작은 입력에 유용: 오버헤드가 적기 때문에, 빠르다.

3. 최적화의 기준: 최적 알고리즘 비교의 참고대상이 됨.

4. 이론적 토대: 최적화 적용 전, 복잡도 이해에 도움을 준다.

-> sorting, searching, geometric problems, exhaustive search, and graph traversal 에 사용됨

 

# Exhaustive Search

 

- 기존 문제점: input size가 커지면서, 일부 알고리즘은 복잡도가 폭발적으로 증가한다. <- 보통 순열/조합/부분집합을 생성함

- 최적화 문제점: 이런 큰 복잡도 속에서도, 가장 비용이 적은 것을 찾아야함.

- 이런 문제에 Brute-force 전략을 적용한 것을 Exhaustive Search 라고 부른다.

- Exhaustive Search 는 정확성을 보장하지만, 효율적이지는 않다. -> 합리적인 전략은 아님.

 

# Graph Search

 

구조

1. 선형구조

- 순차적 레이아웃덕분에 순회가 쉬움

- ex) list,stack

2. 비선형구조

- 탐색과정이 1보다 훨씬 복잡하다

- ex) tree,graph

 

그래프 순회

- 시작정점에서부터 중복없이 모든 정점을 한번씩만 방문하는 것

 

그래프 탐색 전략 2 <- Exhaustive Search 를 구현하는 방법 중 일부

1. DFS

- 깊이 우선 탐색: 한 경로를 따라 최대한 깊게 탐색한다.

- stack 사용(LIFO)

2. BFS

- 너비 우선 탐색: 시작정점 기준 가까운 정점에 차례대로 방문한다.

- queue 사용 (FIFO)

 

그래프 구조 2

1. 인접행렬

2. 인접 리스트

 

그래프 탐색 전략의 시간복잡도

1. 인접행렬 O(n+e): 정점개수+간선개수 -> 간선의 수가 적은 희소 그래프에서 효율적이다.

2. 인접 리스트 O(n^2): 모든 정점에서 n번씩 계산 -> 희소그래프에서는 오히려 공간 낭비이다.