변수의 기록

백트래킹(Backtracking) vs 시뮬레이션(Simulation) 문제 정리1. 백트래킹 (Backtracking)✅ 개념백트래킹은 해를 찾기 위해 가능한 모든 경우의 수를 탐색하되,불필요한 경로(조건 위반)가 감지되면 탐색을 중단하고 이전 단계로 돌아가는 방식이다.즉, "완전 탐색 + 가지치기" 전략.✅ 언제 사용하는가?모든 경우의 수를 탐색해야 하는 문제조합, 순열, 부분 집합, 경로 찾기 등의 문제에서 유용for문으로는 해결이 불가능한, 깊이가 달라지는 문제 구조✅ 전형적인 예시 문제N과 M (순열, 조합)모든 연산자 끼워넣기퀸 문제(N-Queen)최소 비용 경로 탐색스도쿠✅ 시간 복잡도 기준 경우의 수 조건 시간 복잡도현실적으로 가능한 N중복 허용N ≤ 7~8 수준중복 불허N ≤ 10 수준..

DFS vs BFS (그래프 탐색 기법 정리)1. 그래프 탐색이란?그래프 탐색(Graph Traversal)이란, 어떤 노드(정점, Vertex)에서 시작해서 연결된 모든 노드를 빠짐없이 방문하는 과정이다.그래프는 다음 두 요소로 구성된다:Vertex (정점): 탐색의 대상이 되는 지점 (예: 사람, 도시, 방 등)Edge (간선): 정점 간의 연결 (예: 친구 관계, 도로, 벽 없는 통로 등)그래프는 연결되어 있는 방식에 따라 다양한 문제(미로 탐색, 단지 번호 붙이기, 친구 관계 등)에 응용될 수 있다.2. 탐색 기법 종류✅ DFS (Depth-First Search, 깊이 우선 탐색)한 방향으로 쭉 들어가며 끝까지 탐색한 뒤, 다시 돌아와서 다른 방향 탐색자식의 자식까지 내려감, 더 이상 갈 곳이 ..

Dynamic Programming (DP) 개념 정리1. Optimization Problem이란?Optimization Problem은 가능한 해답 중에서 **가장 최적의 해(solution)**를 찾는 문제입니다.“최적”이란 일반적으로 최대값(Maximum) 또는 **최소값(Minimum)**을 의미합니다.예시:가장 적은 비용으로 목적지에 도달하는 경로최대 수익을 내는 주식 거래 시점최소 동전 개수로 거스름돈 만들기✅ 하나의 문제에 대해 하나 이상의 최적 해가 존재할 수도 있음.2. Dynamic Programming(DP)이란?Dynamic Programming은 최적화 문제를 효율적으로 해결하는 알고리즘 설계 기법입니다.핵심 아이디어큰 문제를 작은 하위 문제들로 나누고작은 문제들의 정답을 이용해..

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 노드..