분할정복 검색 결과

해당 글 5건

[BOJ 1992] 쿼드트리(C++)

쿼드트리(Silver 1) 문제 전체 문제 보기 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 접근법 이번 문제는 분할정복으로 풀 수 있습니다. 우선 현재 입력받은 범위 내에서 모든 수가 같은지 확인하는 Check 함수를 만듭니다. 이 Check함수를 활용해서 모든 수가 같은지 확인 후 같다면 해당 수를 출력하고, 같지 않다 배열의 범위를 4곳으로 나누어 재귀적으로 호출합니다. 코드는 다음과 같습니다. 전체 풀이 #include #include #include #define endl '\n' u..
Algorithms/Division and Conquest 2021. 9. 23. 19:15

[프로그래머스] 쿼드압축 후 개수 세기 (C++)

쿼드 압축 후 개수 세기 (Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 접근법 이 문제는 다음과 같이 분할 정복으로 풀 수 있는 문제입니다. 2차원 배열에 모든 값을 탐색하여 압축 가능한지 확인한다. 압축이 불가능 하다면, 1 사분면, 2 사분면, 3 사분면, 4 사분면으로 나누고 ..
Algorithms/Division and Conquest 2021. 9. 15. 22:34

분할정복을 활용한 Quick Sort 구현 (C++)

분할 정복을 활용한 Quick Sort 구현 접근법 Quick Sort는 분할 정복을 활용한 대표적인 정렬 알고리즘입니다. 그래서 Quick Sort를 직접 구현해 보는 것은 분할 정복을 이해하는데 많은 도움이 될 수 있습니다. Quick Sort의 원리는 다음과 같습니다. Quick Sort를 구현하기 위해서는 left, right, pivot을 설정해야 합니다. left는 배열의 첫 원소를 가리키고, right는 배열의 마지막 원소를 가리킵니다. pivot은 Quick Sort를 구현하는 방법에 따라 다르긴 하지만, 여기서는 배열의 중앙값을 가리킵니다. 배열의 중앙값을 pivot으로 정한다. left가 right보다 작거나 같다면 아래의 행동을 반복한다. left는 가장 왼쪽에서 오른쪽 방향으로 pi..
Algorithms/Division and Conquest 2021. 9. 15. 16:34

[BOJ 2263] 트리의 순회(C++)

트리의 순회 (Gold 3) 문제 전체 문제 보기 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 접근법 이 문제는 트리의 중위 순회와 후위 순회 출력 값으로 트리의 전위 순회를 만드는 문제이다. 전위 순회는 루트 노드가 가장 먼저 출력되고, 중위 순회는 루트 노드가 중간에 출력되며, 후위 순회는 루트 노드가 가장 마지막에 출력된다는 특징을 가졌다. 아래의 그래프를 보자. 루트 노드 5가 후위 순회에서 가장 마지막에 출력됨을 알 수 있다. 우리는 이러한 특징을 활용하여 문제를 분할 정복으로 풀 수 있다. 후위 순회의 마지막 값을 루트 노드로 ..
Algorithms/Division and Conquest 2021. 9. 8. 10:47