문제 해결 알고리즘 기초/분할 정복 (8) 썸네일형 리스트형 [프로그래머스] 쿼드압축 후 개수 세기 - 분할 정복 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 쿼드압축 후 개수 세기 접근 방법 쿼드 압축은 2차원 배열을 4분할 했을 때 4면의 정보를 한 가지 표현으로 나타낸다. 문제에서 4면이 모두 같은 숫자인 경우 이를 해당 숫자 하나로 표현한다. 즉, 모두 같은 숫자를 가진 배열을 찾을 때 까지 주어진 배열을 4분할 한 뒤 각각에 대해 검사한다. C++ 코드 #include #include #include using namespace std; vector cutInQuarter(vector coord, vector arr) { vector row; vector ret; for (int i = coord[0]; i < coord[1]; ++i) { for (int j = coord[2] ; j <.. [프로그래머스] 괄호 변환 - 분할 정복 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 괄호 변환(링크) 접근 방법 문제에서 괄호를 재귀적으로 변환하는 방법에 대한 가이드 라인이 주어져 코드에서도 똑같이 이해되도록 구현했다. C++ 코드 iterator.end() 는 해당 컨테이너의 마지만 원소 바로 다음 위치를 가르킨다. string::append 함수를 이어붙여 호출하면 코드가 간결하고 더 직관적이다. #include #include using namespace std; bool isCorrect(string p) { int correct = 0; for (const auto& e: p) { e == '(' ? correct += 1 : correct -= 1; if (correct < 0) return false; } re.. [프로그래머스] 점프와 순간이동 - 분할 정복, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 점프와 순간 이동(링크) 접근 방법 주어진 그대로 시작 위치에서 출발하며 규칙을 찾으려고 했다. 순간 이동을 위해서 이동한 거리가 필요하니까 처음 한 칸을 점프하고 순간 이동으로 N까지 최대한 가깝게 이동한 후 점프로 마무리하는 가장 단순한 접근에서 부터 각 위치에서도 점프를 하느냐 마느냐에 따라 결과가 달라지므로 각 위치에서 재귀적으로 점프와 순간 이동을 하려고 생각했지만 너무 많은 경우의 수가 있고 입력이 10억 이하의 자연수인 만큼 모든 위치를 평가해 보기에는 힘들 것 같았다. 풀이 N에 도달하기 위해서 N / 2 위치에서 순간 이동하고 N / 2에 도달하기 위해 N / 4 위치에서 순간 이동 해야 한다. 재귀적으로 생각하면, 어떤 목적.. [알고스팟] 울타리 잘라내기 - 분할 정복, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 울타리 잘라내기(링크) 접근 방법 부분적으로 잘라낸 울타리의 최대 크기를 구하기 위해 분할 정복 기법을 사용했다. 주어진 울타리를 나무 판자 한개가 될 때까지 절반으로 분할하면 한개가 된 나무 판자 (한 조각의 부분 문제) 의 크기가 가장 작은 부분 문제의 답(기저 사례)이 된다. 울타리는 항상 절반으로 나누어져 왼쪽, 오른쪽 부분 울타리의 최대 크기를 가져오는데, 울타리를 합쳤을 때 왼쪽과 오른쪽 울타리에 걸쳐서 잘라낼 수 있는 것의 크기도 고려해 더 큰 울타리를 만들 수 있는지 확인해야 한다. 따라서 합치는 과정에서 중간 두개의 나무 판자로부터 양쪽으로 확장해 나가며 현재 왼쪽, 오른쪽 울타리 중 큰 울타리보다 더 큰 울타리를 만들 수 있.. [알고스팟] 쿼드트리 뒤집기 - 분할 정복, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 쿼드트리 뒤집기(링크) 접근 방법 문제에서는 원본의 흑백 그림에 대해 quad tree는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 순서로 알파벳 코드를 작성해 나간다. 윗줄과 아랫줄을 바꾼다고 할 때, 원본 그림에 대해 왼쪽 아래, 오른쪽 아래, 왼쪽 위, 오른쪽 위의 순서로 알파벳 코드를 작성하면 상하 반전이 된 quad tree를 얻을 수 있다. quad tree는 x를 만나면 4개의 알파벳 (4면의 그림) 을 만나게 되니까, 기본적으로 재귀 함수 형태로 작성했다. 재귀 함수의 인자로 문자열 자체를 넘겨 string.substr(1)을 통해 문자를 하나씩 줄여가는 방식을 취하려 했는데 재귀 내부에서의 변화를 함수 탈출 후에도 유지.. 빠른 정렬 - 분할 정복, 시간 복잡도 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 빠른 정렬 병합 정렬과 반대로 분할하는 과정에서 정렬된다. 배열의 원소 중 하나를 기준으로 하여 다른 원소들과 비교해 자리를 교환하며 정렬한다. 시간 복잡도 수행시간은 문제를 두 개의 부분 문제로 나누는 과정에 의해 지배된다. 병합 과정과 달리 분할된 부분 문제가 비슷한 크기로 나눠진다는 보장이 없다. 기준 원소가 최소값 혹은 최대값인 경우에 부분 문제의 크기가 하나씩만 줄어들 수도 있다. 이런 최악의 경우 O(n^2)의 시간 복잡도를 가진다. 평균적으로 부분 문제가 절반에 가깝게 나눠질 때 병합 정렬과 같은 O(nlgn)의 시간 복잡도를 가진다. 이런 경우는 단지 나눌 때 정렬하는지, 합칠 때 정렬하는지의 차이라고 볼 수 있다. C++ 코드.. 병합 정렬 - 분할 정복, 시간 복잡도 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 병합 정렬 주어진 배열을 크기가 1 이 될 때까지 절반씩 나눈다. 길이 1짜리 수열들을 서로 합치는 과정에서 크기를 비교해 정렬한다. 실제로 배열을 나누는 과정은 인덱스의 위치를 조정하는 것으로 O(1) 에 수행되고 나뉜 배열을 합치는 과정에서 각 원소 모두를 비교해 정렬한다. 즉, n 개 배열에 대해 O(n) 의 비교 과정을 거친다. 나눠진 배열을 합치는 과정을 원본 배열이 나눠진 횟수만큼 반복해야 한다. 길이가 n 인 원본 배열을 항상 거의 절반으로 나누므로 나눠진 횟수는 로그 n 이다. 따라서, 병합 정렬의 시간 복잡도는 O(n * lgn). 자세한 구현은 코드의 주석으로 확인해보자. vector v, tmp; void mergeSort.. 분할 정복 알고리즘에 대해서, 수열의 빠른 합 문제 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 분할 정복 문제를 거의 같은 크기인 둘 이상의 부분 문제로 나눈 뒤 각 문제의 답을 재귀적으로 계산하고, 각 문제의 답으로부터 전체 문제의 답을 계산한다. 문제를 더 이상 나눠지지 않는 매우 작은 단위 (기저 사례) 까지 나누고 (Divide), 나눠서 해결한 문제의 답을 원래 문제의 답으로 합친다. (Merge) 수열의 빠른 합을 구하는 과정을 분할 정복으로 생각해보자. fastSum(n) 은 1 부터 n (자연수) 까지의 합을 구하는 함수이다. 먼저, n 까지의 합을 구하는 과정을 거의 같은 크기의 부분 문제로 나눈다. n 까지의 합을 구하는 과정을 절반으로 나누었다. fastSum(n) = 1 + 2 + ... + n = (1 + 2 +.. 이전 1 다음