분할정복3 [백준문제풀이] 1992 쿼드트리 풀이일시 : 2020-09-29 문제 : 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배.. 2020. 12. 31. [백준문제풀이] 1074 Z 풀이일시 : 2020-09-24 문제 : 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 : 첫째 줄에 정수 N, r, c가 주어진다. ex) 2 3 1 출력 : r행 c열을 몇 번째로 방문했는지 출력한다. ex) 11 제한 : 1 2020. 12. 31. [기본문제풀이] 분할정복 풀이일시 : 2020-08-31 분할정복 : divide and conquer 로 성질이 똑같은 여러개의 부분문제로 문제를 나누어 해결하는 방법이다. 1. 문제 사례를 하나 이상의 작은 사례로 분할한다. 2. 작은 사례들을 각각 정복(conquer)한다. 재귀를 이용 3. 작은 사례에 대한 해답을 통합하여 원래 사례의 답을 구한다. 장점 - 문제를 나눠 풀어 어려운 문제를 해결할 수 있다. 병렬적으로 문제를 해결. 단점 - 함수를 재귀적으로 호출하여 오버헤드가 발생, 스택 오버플루우가 발생하거나 과도한 메모리사용 가능성 쓰임 - 이분검색, 최대값찾기 및 여러 알고리즘문제풀이에 쓰인다. 아래는 분할&정복 알고리즘의 대략적인 묘사도이다. 문제와 풀이 : dbstndi6316.tistory.com/10.. 2020. 12. 29. 이전 1 다음 반응형
