분할정복4 [leetcode] 108. Convert Sorted Array to Binary Search Tree 문제 : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ 오름차순 정렬된 nums 배열이 주어질 때, height-balanced BST로 변형하라. height-balanced BST는 모든 노드들의 두 하위 트리깊이가 1이상 차이가 나지 않는 이진 트리이다. height-balanced BST가 뭔가 했더니 이런식으로 불균형적인 트리를 만들지말란 의미였다. [그림 1]에서 왼쪽 하위트리의 높이는 1, 오른쪽 하위트리의 높이는 3 이므로 1 이상 차이가 나서 높이 균형 BST가 아니다. 결국 노드들을 왼쪽 오른쪽 균등하게 분배하면서 bst를 만들라는 뜻이다. 정렬된 nums 배열의 중간 값을 현재 노드로 만들고 중간 값.. 2021. 7. 27. [programmers][월간 코드 챌린지 시즌1] 쿼드압축 후 개수 세기 문제 : programmers.co.kr/learn/courses/30/lessons/68936 크기가 2인 answer 배열을 하나 만들고 각각 0, 1일 때 크기를 저장한다. arr[sx~ex][sy~ey] 를 탐색하면서 모든 수가 같은지 확인하고 같다면 answer 배열을 갱신하고 같지 않다면 배열을 4분할로 나눠서 다시 판단한다. 이 때 n은 확인하고 있는 배열의 크기로 ex - sx값이라 한다. 1. arr[sx ~ ex - n/2][sy ~ ey - n/2] 2. arr[sx + n/2 ~ ex][sy ~ ey - n/2] 3. arr[sx ~ ex - n/2][sy + n/2 ~ ey] 4. arr[sx + n/2 ~ ex][sy + n/2 ~ ey] 이를 매열 크기가 1일때까지 반복하고 배.. 2020. 10. 17. [algospot][QUADTREE] 쿼드 트리 뒤집기 문제 : https://www.algospot.com/judge/problem/read/QUADTREE 분할정복 문제. 만약 입력으로 받은 문자열의 길이가 1이라면 이는 압축이 되는 경우가 없을 때이다. (x가 입력에 없음) 이 때는 해당 문자열을 그대로 반환한다. 문자열 길이가 1이 아닌 경우는 첫 번째 문자가 반드시 x가 된다. 입력으로 받은 문자열을 앞에서부터 탐색하면서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 부분을 배열에 각각 저장한다. 탐색 하면서 나올 수 있는 경우는 총 3가지이다. 탐색 중인 문자(now)가 1. 'w'인 경우 : 배열에 "w" 저장 2. 'b'인 경우 : 배열에 "b" 저장 3. 'x'인 경우 : 탐색 중인 인덱스부터 시작하는 문자열로 다시 왼쪽 위, 오른쪽 위, .. 2019. 5. 24. [CodeJam][2017] Bathroom Stalls - Qualification Round C 문제 : https://code.google.com/codejam/contest/3264486/dashboard#s=p2 N이 9라고 할 때를 예로 들어보자.파란색이 연속된 빈 자리(탐색 중인 자리들). 빨간 색이 이때 선택되는 최적의 자리이다.연속된 빈 자리가 많을 수록 우선으로 선택된다. (최대, 최소가 크므로)그리고 연속된 빈 자리수가 같다면 구하고자 하는 다른 상점 or 화장실과의 최대, 최소 거리는 같다. -> 한꺼번에 계산할 수 있다. map을 하나 만든다. key 값은 연속된 빈 자리이고 value는 연속된 빈 자리 수의 개수가 된다.key 값이 큰 것부터 탐색한다. (거리의 최대, 최소는 연속된 빈 자리 수에 비례하므로)탐색중인 map의 key값을 n, value를 cnt라 하자.cnt만큼.. 2019. 1. 27. 이전 1 다음
