반응형
풀이일시 : 2020-08-31
분할정복 :
divide and conquer 로 성질이 똑같은 여러개의 부분문제로 문제를 나누어 해결하는 방법이다.
1. 문제 사례를 하나 이상의 작은 사례로 분할한다.
2. 작은 사례들을 각각 정복(conquer)한다. 재귀를 이용
3. 작은 사례에 대한 해답을 통합하여 원래 사례의 답을 구한다.
장점 - 문제를 나눠 풀어 어려운 문제를 해결할 수 있다. 병렬적으로 문제를 해결.
단점 - 함수를 재귀적으로 호출하여 오버헤드가 발생, 스택 오버플루우가 발생하거나 과도한 메모리사용 가능성
쓰임 - 이분검색, 최대값찾기 및 여러 알고리즘문제풀이에 쓰인다.
아래는 분할&정복 알고리즘의 대략적인 묘사도이다.
문제와 풀이 :
[백준문제풀이] 1074 Z
풀이일시 : 2020-09-24 문제 : 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z
dbstndi6316.tistory.com
[백준문제풀이] 1992 쿼드트리
풀이일시 : 2020-09-29 문제 : 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서
dbstndi6316.tistory.com
반응형
'알고리즘 문제풀이 > 기본문제풀이' 카테고리의 다른 글
| [기본문제풀이] DFS 깊이우선탐색 (0) | 2020.12.29 |
|---|---|
| [기본문제풀이] BFS 너비우선탐색 (0) | 2020.12.29 |
| [기본문제풀이] greedy 알고리즘 (0) | 2020.12.29 |
| [기본문제풀이] rabin karp 알고리즘 (0) | 2020.12.28 |
| [기본문제풀이] KMP알고리즘 (0) | 2020.12.28 |
댓글