변수의 기록

Divide and Conquer (분할 정복) 전략개념 정리**Divide and Conquer(분할 정복)**는 컴퓨터 과학에서 널리 사용되는 문제 해결 전략 중 하나로, 다음 세 단계로 이루어져 있습니다:Divide (분할)주어진 문제를 **더 작고 유사한 하위 문제들(sub-problems)**로 나눈다.각 서브 문제는 원래 문제와 구조적으로 유사하며, 전체 문제를 분해하여 해결 가능하도록 만든다.Conquer (정복)나눠진 서브 문제들을 재귀적으로 해결한다.더 이상 나눌 수 없을 정도로 작은 문제(기저 조건 base case)는 직접 해결한다.Combine (통합)해결된 서브 문제들의 결과를 합쳐서 전체 문제의 해답을 구성한다.주요 특징재귀 호출을 기반으로 하며, 하향식(top-down) 방식의..

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자..

문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를..

레드-블랙 트리의 삭제 동작 방식과 시간복잡도레드-블랙 트리(Red-Black Tree)는 삽입보다 삭제가 더 복잡한 구조적 조정을 필요로 한다.이는 트리의 속성(#2~#5)이 깨질 가능성이 높기 때문이며,특히 Black 노드가 삭제되는 경우 트리의 균형이 크게 영향을 받는다. 참고 (레드-블랙 트리의 5가지 주요 속성)모든 노드는 Red 또는 Black이다.루트 노드는 항상 Black이다.모든 leaf 노드(NIL 노드)는 Black이다.실제 값이 없는 NIL 노드는 트리의 균형 계산에 사용됨.Red 노드의 자식은 모두 Black이다.즉, Red 노드가 연속적으로 나타날 수 없다.임의의 노드에서 그 자손인 모든 NIL 노드로 가는 경로에는 같은 수의 Black 노드가 있다.이를 Black Height라..

레드-블랙 트리(Red-Black Tree) 개념과 속성 정리레드-블랙 트리는 자기 균형 이진 탐색 트리(Self-balancing BST) 의 일종이다. 일반 이진 탐색 트리(BST)는 삽입 순서에 따라 한쪽으로 편향될 수 있는데, 레드-블랙 트리는 특정 규칙을 통해 항상 트리의 높이를 O(log N) 수준으로 유지함으로써 검색, 삽입, 삭제 연산을 효율적으로 만든다.✅ 기본 개념이진 탐색 트리(BST)의 변형으로, 추가적인 색상 속성을 가지는 트리.모든 노드는 Red 또는 Black 색을 가짐.자체적으로 균형을 유지하여, 최악의 경우에도 탐색 시간이 O(log N)을 보장함.✅ 레드-블랙 트리의 5가지 주요 속성모든 노드는 Red 또는 Black이다.루트 노드는 항상 Black이다.모든 leaf 노드..

문제 설명명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다. 명함 번호 가로 길이 세로 길이16050230703603048040가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=..

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..

문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 이하입니다. a..