개발일지

문제 설명 제한 사항 및 입출력 예제 개념 주어진 배열에서 k개를 선택하는 방법 중 종류를 가장 적게 고르는 방법을 구하는 문제다. 배열을 내림차순으로 정렬하고, 가장 많은 개수를 가진 귤의 크기부터 선택하여 바구니에 담는 그리디 알고리즘을 채택하여 문제를 효율적으로 해결할 수 있다. 풀이 #include #include #include #include using namespace std; int solution(int k, vector tangerine) { int answer = 0, sum = 0; map m; for (const auto& val : tangerine) m[val]++; 주어진 벡터에 있는 원소들의 개수를 파악하기 위해 map 자료구조를 활용하였다. 이때 맵은 귤의 크기를 키로 하..

문제설명 입출력 예제 개념 배열 A와 B를 받아, 두 배열의 곱의 합 A[i] * B[i]의 합의 최솟값을 구하는 문제다. 이는 A 배열의 최솟값과 B 배열의 최댓값을 곱하면 쉽게 해결할 수 있다. 이를 엄밀히 증명하면 다음과 같다. a ≤ b 그리고 c ≤ d를 가정하면 (여기서 a, b, c, d는 임의의 실수입니다), 이때 다음 부등식이 성립한다 ac + bd ≤ ad + bc 이 부등식은 다음과 같이 변환된다. ac + bd - ad - bc ≤ 0 => ac - ad + bd - bc ≤ 0 => a(c - d) + b(d - c) ≤ 0 => (a - b)(c - d) ≤ 0 이제 우리가 얻은 부등식에 두 배열의 원소들을 대입해보자. 배열 A와 B가 주어지고, A의 원소 a, b (a ≤ b)..

문제설명 입출력 예제 개념 최소 비용을 통해 목표를 달성하는 그리드 알고리즘을 활용하는 문제다. 이 문제의 핵심 아이디어는 가장 낮은 기름값을 갖는 주유소를 찾아, 그곳에서 기름을 충전하는 것이다. 따라서 현재 위치에서 다음 도시로 이동하기 위해 필요한 기름을 충전하는데, 현재 주유소의 기름 가격과 다음 주유소의 기름 가격을 비교하여 최소 비용을 항상 유지하게 기름값을 갱신하면 된다. 풀이 #include #include using namespace std; int main() { long long N; cin >> N; vector station(N), road(N-1); for (int i = 0; i > road[i]; for (int i = 0; i < N; ++..

문제설명 입출력 예제 개념 각 사람이 돈을 인출하는 데 필요한 시간 합의 최솟값을 출력하는 문제다. 대표적인 그리디 알고리즘으로 효율적으로 해결할 수 있는 문제로서, 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리하는 최단 작업 우선 스케줄링 방식을 이용하면 된다. 여기서 돈을 인출하는데 걸리는 시간을 작업으로 보고, 이 작업들을 가장 짧은 것부터 처리하면 모든 사람이 돈을 인출하는데 필요한 최소 시간을 구할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N; cin >> N; vector v(N); int* sum = new int[N]; for (int i = 0; i > v[i]; s..

문제설명 입출력 예제 개념 이 문제는 회의 시간이 겹치지 않도록 하면서 동시에 가능한 한 많은 수의 회의를 배정하는 문제다. 이를 해결하는 방법 중 하나는 먼저 회의들을 종료 시간 기준으로 오름차순 정렬하는 것이다. 그리고, 가장 먼저 끝나는 회의를 선택한 후, 이전에 선택한 회의와 시간이 겹치지 않는 회의 중 가장 빨리 끝나는 회의를 다음으로 선택하는 것이다. 이러한 방식을 반복함으로써 가능한 많은 수의 회의를 배정할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N, n, k, count = 1; cin >> N; vector v(N); 회의의 수 N, 그리고 회의의 시작과 끝에 대한 입력을 초기화할 변수 n, k,..

문제설명 입출력 예제 개념 K원을 만드는데 필요한 최소한의 동전 개수를 구하는 문제다. 가장 가치가 큰 동전부터 사용하는 것이 최선의 서택이므로, 이러한 선택을 통해 가장 적은 동전을 사용하여 주어진 금액을 만들 수 있는 최적의 해답을 찾을 수 있다. 즉, 그리디 알고리즘을 사용하여 문제를 효율적으로 풀 수 있다. 풀이 #include #include using namespace std; int main() { int N, K, n, answer = 0; cin >> N >> K; vector v(N); for (int i = 0; i > v[i]; for (auto it = v.rbegin(); it != v.rend(); ++it) { if (*it < K) { answer..

문제 설명 제한 사항 및 입출력 예제 개념 이 문제는 최대 2명만 탑승 가능한 구명보트를 최소한으로 사용해 모든 사람을 구조하는 문제다. 이러한 상황에서 구명보트의 수를 최소화하려면, 남은 사람들 중 가장 가벼운 사람과 가장 무거운 사람을 동시에 태울 수 있는지 확인하면 된다. 따라서 투 포인터 알고리즘을 이용하여, 매 순간 보트에 최대한 많은 사람을 태우는 그리디 알고리즘을 구현하면 문제를 해결할 수 있다. 가장 가벼운 사람과 가장 무거운 사람이 보트의 무게 제한 내에 함께 탈 수 있다면, 두 사람을 동시에 태우는 것이 최선의 선택 그렇지 않다면, 가장 무거운 사람만 보트에 태우는 것이 최선의 선택 풀이 #include #include using namespace std; int solution(vec..

시간 복잡도　지난 포스팅에서 디스조인트-셋 자료구조를 사용하면 시간 복잡도가 O(Ea(V))로 줄어들며, 정점이 많은 그래프에서 큰 성능 차이가 발생한다고 하였다. 이는 디스조인트-셋 데이터 구조에 특정 휴리스틱을 적용했다는 것을 의미하는데, 여기서 휴리스틱(heuristics)이란 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 사용하는 어림짐작의 기술, 즉 항상 최적의 해를 보장하진 않지만 신속하게 답을 구할 수 있는 접근 방식이다. 이 휴리스틱은 Union by rank와 Path compression이다. 　Union by rank는 두 트리를 합칠 때 더 작은 랭크(rank)의 트리를 더 큰 랭크의 트리 아래에 두는 방법이고, Path compression은 find 연산을 수행할 ..

최소 신장 트리 문제그리디 알고리즘 요구 조건　앞 절에서 모든 문제에 그리디 방식을 적용할 수 있는 것은 아니라고 했다. 즉, 최적 부분 구조(optimal substructure)와 그리디 선택(greedy choice)이라는 두 가지 속성을 모두 갖는 문제만 그리디 접근 방식으로 최적의 솔루션을 구할 수 있다.  　최적 부분 구조는 큰 문제의 최적해가 부분 문제의 최적의 해답들로 구성될 수 있는 구조를 의미한다. 그리디 선택 속성은 현재의 선택이 미래의 선택에 영향을 미치지 않고, 각 단계에서 최적의 선택을 하면 전체적으로 최적의 해답을 얻을 수 있는 것을 의미한다. 　이러한 특성에 대해 이해하기 위해 크루스칼 최소 신장 트리 알고리즘에 대해 알아보도록 하자.개요　최소 신장 트리(Minimum Spa..

배낭 문제개요　배낭 문제(knapsack problem)는 조합 최적화의 한 부분으로, 최적화 이론 및 적용을 이해하는데 근본적인 문제다. 즉, 이 문제는 제한된 무게(또는 부피)의 배낭에 가장 가치 있는 물품들을 적절히 담는 방법을 찾는 것이다. 여기서 물건들은 각각 특정한 무게와 가치를 갖는다.본문 　배낭 문제는 주로 0-1 배낭 문제와 분할 가능 배낭 문제 두 가지 유형으로 분류된다. 일반 배낭 문제라고도 불리는 0-1 배낭 문제는 각각의 아이템이 배낭에 포함되거나 포함되지 않는 두 가지 상태만을 갖는다. 따라서, 아이템을 쪼개서 담는 것이 불가능하다. 이 문제는 NP-완전 문제로 분류되어, 이를 다항 시간 내에 결정적으로 풀 수 있는 알고리즘이 알려져 있지 않다.   　반면, 분할 가능 배낭 문제..