괴물 클럽

A번 문제: 최소 변경 횟수 이 문제는 비내림차순 수열로 만들기 위해 필요한 최소 변경 횟수를 구하는 문제입니다. 주어진 수열이 비내림차순이 아니므로, 가장 많은 원소를 그대로 유지할 수 있는 경우를 찾아야 합니다. 비내림차순 수열에서 가장 많이 유지할 수 있는 원소들은 동일한 값의 연속된 부분입니다. 따라서 가장 긴 동일한 값의 연속 부분의 길이를 찾으면 ...

정렬된 정수 배열 nums와 목표값 target이 주어졌을 때, 이 목표값이 처음 나타나는 위치와 마지막으로 나타나는 위치를 반환하는 문제입니다. 만약 목표값이 존재하지 않으면 [-1, -1]을 반환해야 하며, 알고리즘은 반드시 O(log n) 시간 복잡도를 가져야 합니다. 예시: 입력: nums = [5,7,7,8,8,10], target = 8 출력: [3,4] 초기 시도에서는 모든 일치하는 인덱스를 s ...

1. 교차 연결 리스트 문제 링크: 교차 연결 리스트 먼저 코드를 살펴보겠습니다. /** * 단일 연결 리스트에 대한 정의입니다. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* findIntersectionNode(struct ListNode* listA, struct ListNode* ...

서론: 재귀에 대한 솔직한 고백 재귀를 코딩할 때 종종 이런 경험이 있다. 코드는 작동하지만, "왜 이게 맞는지"는 설명하기 어렵다. 예를 들어: 왜 트리를 해제할 때 후위 순회를 써야 할까? 어떤 문제에서는 논리합(||)을 쓰고, 어떤 문제에서는 논리곱(&&)을 쓸까? 함수를 분리해서 작성해야 하는 경우는 언제일까? 이 글은 ...

1. 변경하지 않는 시퀀스 알고리즘 이러한 알고리즘들은 조작하는 컨테이너의 요소들을 변경하지 않습니다. 1.1 find와 find_if find(begin, end, value): value와 같은 첫 번째 요소를 찾아 반복자를 반환 (찾지 못하면 end 반환). find_if(begin, end, predicate): 조건자(predicate)를 만족하는 첫 번째 요소를 찾습니다. find_end(begin, end, sub_begin, sub_end): ...

문제 설명 수직선 위에 여러 개의 상품이 위치해 있으며, 각 상품의 좌표는 비내림차순으로 정렬된 배열 prizePositions로 주어집니다. 같은 위치에 여러 상품이 있을 수도 있습니다. 또한 정수 k가 주어지며, 이는 선택할 수 있는 두 개의 닫힌 구간 각각의 길이를 의미합니다 (즉, 구간의 길이는 정확히 k여야 함). 목표는 두 개의 길이 k인 구간을 선택하여 포함되는 ...

동적 계획법 핵심 개념 동적 계획법은 중복 하위 문제가 많은 최적화 문제에 효과적입니다. 문제를 하위 문제로 분해하고, 동일 계산을 반복하지 않도록 결과를 저장합니다. 최적 부분 구조가 존재해야 적용 가능하며, 이는 지역 최적해가 전역 최적해로 이어지는 구조를 의미합니다. 핵심은 상위 문제 해결에 하위 문제의 결과가 재사용되는 점입니다. 대표적인 예로 피 ...

이 문서는 세 가지 핵심 알고리즘 문제에 대한 다양한 해결 전략과 최적화 기법을 다룹니다. 소수 판별부터 배열 내 중복 원소 탐색, 그리고 '최대 물을 담을 수 있는 컨테이너' 문제까지, 각 문제에 대한 기본 접근 방식과 개선된 솔루션을 C++ 코드를 통해 설명합니다. 1. 소수 판별 알고리즘 소수(Prime Number)는 1과 자기 자신만으로 나누어떨어지는 1보다 큰 자연수 ...

T1 분배 문제 이 문제는 최대 나머지를 계산하는 간단한 알고리즘을 요구했습니다. 주어진 범위 내에서 최대값을 찾는 방식으로 접근했습니다. #include <iostream> using namespace std; int main() { int total, start, end; cin >> total >> start >> end; int maxRemain = 0; for(int i = start; i > queries; for(int i = 0; i < size; ...

다음 순열 정수 배열의 순열은 모든 요소를 일렬로 나열한 것을 의미합니다. 주어진 정수 배열에서 사전순으로 다음에 오는 더 큰 순열을 찾아야 합니다. 만약 더 큰 순열이 없다면, 배열을 가장 작은 순서로 재배치해야 합니다. #include <vector> #include <algorithm> class Solution { public: void nextPermutation(std::vector<int>& n ...