Algorithms/Division and Conquest 검색 결과

해당 글 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

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

분할 정복을 활용한 Merge Sort 구현 접근법 Merge Sort는 분할 정복을 활용한 대표적인 알고리즘 중 하나입니다. 분할 정복을 연습하기 위해서 Merge Sort를 구현해 보았습니다. Merge Sort의 원리는 다음과 같습니다. 하나의 배열을 원소가 하나가 남을 때까지 양분(분할)합니다. 재귀적으로 분할된 원소를 정렬하며 다시 병합하여 온전히 정렬된 배열을 만듭니다. Merge Sort의 가장 큰 특징은 안정 정렬이라는 것입니다. 안정 정렬이란 똑같은 원소라면 그 상대 위치가 변하지 않는다는 뜻입니다. 예를 들어 아래와 같은 데이터 타입이 있다고 가정해 봅시다. struct data{ int key; char name; } 위 데이터 타입을 가진 데이터들이 아래와 같이 정렬되지 않은 상태로..
Algorithms/Division and Conquest 2021. 9. 16. 11:14

[프로그래머스] 쿼드압축 후 개수 세기 (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