아~ 알고리즘 너무 어려워~ 하지만 공부 하고 넘어가야겠지...?
BFS(Breadth-First Search) - 너비 우선 탐색
BFS는 가장 가까운 노드부터 차례대로 탐색하는 방식이다.
하나의 노드를 방문한 후, 그 노드와 인접한 모든 노드를 먼저 방문하고, 그 다음으로 인접한 노드를 방문하는 방식이다.
예시: 친구 관계 탐색
상황: 친구들 간의 관계를 나타낸 그래프가 있다고 가정해보자! 'A'라는 친구가 있고 'A'의 친구들은 'B', 'C', 'D'이다. 이제 'A'와 가장 가까운 친구들을 먼저 만나고, 그 다음으로 더 먼 친구들을 만날거다.
A - B - E
| |
C - D탐색 순서(BFS)
- 'A'를 시작으로 'B', 'C', 'D'를 차례대로 방문한다.
- 그다음 'B'의 친구인 'E'를 방문하게된다.
- BFS는 모든 노드를 하나씩 "레벨별로" 차례차례 탐색한다.
BFS 특징
- 큐(Queue)를 사용해 구현한다.
- 각 노드를 한번만 방문하며, 처음 만나는 노드부터 탐색한다.
- 가까운 노드부터 차례로 방문한다.
DFS(Depth-First Search) - 깊이 우선 탐색
DFS는 한 노드에서 시작하여 가능한 한 깊게 들어가면서 탐색하는 방식이다.
한방향으로 끝까지 진행한 후 , 더 이상 진행할 수 없으면 돌아가서 다른 경로를 탐색한다.
예시: 친구 관계 탐색
상황: 같은 친구 관계 그래프에서, 이번에는 'A'에서 시작하여 가능한 한 깊이 탐색하보자.
A - B - E
| |
C - D탐색 순서(DFS)
- 'A'에서 시작해, 'B'로 가고, 그 다음으로 'E'를 방문한다.
- 그다음 'B'를 거쳐 'D'로 가고, 'C'를 방문한다.
- 이 방법으로 가능한 한 방향으로 깊게 들어가며 탐색한다.
DFS 특징
- 스택(Stack)을 사용해 구현한다.
- 한 방향으로 최대한 깊게 탐색한 후, 다시 돌아가 다른 방향을 탐색한다.
- 깊이가 깊은 경로를 우선적으로 탐색한다.
비교
- BFS는 가까운 노드를 먼저 탐색하여 빠르게 가까운 탑을 찾는 데 유리하다.
- DFS는 깊이 있는 노드로 먼저 들어가며, 완전한 경로를 찾고 싶을 때 유리하다.
이진 탐색 (Binary Search)
- 개념: 데이터를 반으로 나누어가며 찾는 방법. 데이터를 오름차순 또는 내림차순으로 정렬한 상태에서만 사용할 수 있다.
- 언제 사용하나:
- 데이터가 정렬되어 있을때.
- 데이터의 개수가 많을 때.
- 예시: 책장에서 책을 찾는다고 생각해보자
- 책이 제목 순서대로 정렬되어 있다면, 중간 책을 펼쳐서 내가 찾는 책이 "앞쪽에 있는지", "뒤쪽에 있는지"를 확인할 수 있다.
- 내가 찾는 책이 뒤쪽에 있다면, 앞쪽의 책은 모두 무시하고 뒤쪽에서 다시 중간을 살펴보면된다.
- 이렇게 반씩 좁혀가며 책을 찾는다.
- 장점:
- 탐색 속도가 빠르다. 데이터의 개수가 많아져도 큰 영향을 받지 않는다.
- 시간 복잡도가 O(long N) 으로 효율적이다.
- 단점:
- 데이터가 반드시 정렬되어 있어야 한다.
- 구현이 순차 탐색보다 조금 더 복잡하다.
자바에 있는 대표적인 이진 탐색
static int binarySearch(int[] a, int fromIndex, int toIndex, int key)- 파라미터
- a: 탐색 대상 배열 (정령되어 있어야 함).
- fromIndex: 탐색 시작 위치 (포함).
- toIndex: 탐색 종료 위치 (포함되지 않음).
- key: 찾으려는 값.
- 리턴 값:
- 값을 찾은 경우: 해당 값의 인덱스를 반환한다.
- 값을 찾지 못한 경우: 음수 값 -(insertionPoint + 1)을 반환한다.
- insertionPoint 는 key가 삽입 되어야 할 위치이다.
int[] dp = new int[nums.length];
int length= 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, length, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == length) {
length++;
}
}
return length;
}순차 탐색 (Sequential Search)
- 개념: 데이터를 처음부터 끝까지 하나씩 차례대로 확인하면서 찾는 방법.
- 언제 사용하나:
- 데이터가 정렬되어 있지 않을 때.
- 데이터의 개수가 적을 때.
- 예시: 책장에서 책을 찾는다고 생각해보자
- 책장이 아무 순서 없이 섞여 있다면, 처음 책부터 하나씩 확인해야 한다.
- 찾는 책을 발견할 때까지 모든 책을 살펴볼 수 도 있다.
- 장점:
- 데이터가 정렬되어 있지 않아도 사용 가능.
- 간단한 구조로 구현 가능.
- 단점:
- 데이터가 많아질수록 시간이 오래 걸림.
- 평균적으로 데이터의 절반을 확인해야 찾을 수 있음.
차이점 정리
| 특징 | 이진 탐색 | 순차 탐색 |
| 필요 조건 | 정령되어 있어야함 | 정렬이 필요 없음 |
| 속도 | 빠름(O(long N)) | 느림(O(N)) |
| 데이터 크기 | 많은 데이터에 적합 | 적은 데이터에 적합 |
| 구현 난이도 | 약간 어려움 | 쉬움 |
동적 계획법(Dynamic Programming, DP)
DP(동대문 플라자가 아니다!)는 큰 문제를 작은 문제로 나누어 해결하고, 그 결과를 저장하여 다시 사용함으로써 연산을 줄이는 알고리즘 설계 기법이다!
중복 계산을 방지하고, 효율적으로 문제를 해결할 수 있다!
핵심 개념
- 분할 정복(Divide and Conquer) 과의 차이점
- 분할 정복(Divide and Conquer)은 문제를 독립적인 하위 문제로 나누어 해결하는 방식.
- 동적 계획법은 문제를 서로 중복되는 하위 문제로 나누고, 결과를 재사용하는 방식.
- 메모이제이션(Memoization)
- 이미 계산한 결과를 메모리에 저장하여 중복 계산을 방지하는 기술.
- 보통 재귀와 함께 사용.
- 탑다운과 보텀업
- 탑다운(Top-Down): 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출.
- 보텀업(Bottom-Up): 작은 문제부터 해결하며 점진적으로 큰 문제로 확장.
동적 계획법을 사용하는 조건
- 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해로 구성되는 경우.
- 중복되는 하위 문제(Overlapping Subproblems): 동일한 하위 문제가 반복적으로 계산되는 경우.
동적 계획법의 동작 과정
- 문제를 작은 하위 문제로 분할.
- 하위 문제를 해결하고 결과를 저장.
- 저장된 결과를 사용하여 큰 문제를 해결
활용 예
- 최적화 문제
- 배낭문제(Knapsack Problem)
- 동전 거스름돈(Coin Change Problem)
- 문자열 문제
- 문자열 유사도 계산(LCS, Longest Common Subsequence)
- 최소 편집 거리(Edit Distance)
- 그래프 문제
- 최단 경로(플로이드-위셜 알고리즘)
- 최대 독립 집합
- 게임 이론 및 기타
- 타일 채우리 문제
- 게임에서 최적의 전략 찾기
아 이걸 이제 알고리즘 풀때 잘 적용해야하는데 일단 뭐 해야지! 어케!
** 그냥 하루하루 개인 공부한 것을 끄적 거리는 공간입니다.
이곳 저곳에서 구글링한 것과 강의 들은 내용이 정리가 되었습니다.
그림들은 그림밑에 출처표시를 해놓았습니다.
문제가 될시 말씀해주시면 해당 부분은 삭제 하도록하겠습니다. **
'Study > Algorithm' 카테고리의 다른 글
| [Algorithm] 시간복잡도 (amortized time complexity) (1) | 2024.12.31 |
|---|
댓글