Algorithm Problem (93) 썸네일형 리스트형 Lesson 4. Counting Elements - MaxCounters #1 1. 문제You are given N counters, initially set to 0, and you have two possible operations on them: - increase(X) − counter X is increased by 1, - max counter − all counters are set to the maximum value of any counter.A non-empty array A of M integers is given. This array represents consecutive operations: - if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X), - if A[K] = N + 1 th.. Lesson 4. Counting Elements - PermCheck 1. 문제A non-empty array A consisting of N integers is given.A permutation is a sequence containing each element from 1 to N once, and only once.For example, array A such that:A[0] = 4A[1] = 1A[2] = 3A[3] = 2is a permutation, but array A such that:A[0] = 4A[1] = 1A[2] = 3is not a permutation, because value 2 is missing.The goal is to check whether array A is a permutation.Write a function:int solu.. Lesson 4. Counting Elements - FrogRiverOne #3 (속도 개선-2) 1. 속도 개선 아이디어이 문제를 조금 다르게 해석하면, 다른 해법이 보인다.문제에서는 '찾는다'라고 표현했지만, 다르게 생각하면 1부터 X까지의 합을 구하는 것과 같다.즉, vector A의 요소들을 더했을 때, (1 + .. + X)가 되는 시점을 구하면 된다. 2. 코드 (C++)int solution(int X, vector &A) { vector found_leaves(X, false); //이미 계산한 값인지 확인하기 위한 vector int sum = X * (X + 1) / 2; //1부터 X까지의 합 for(size_t i = 0; i 3. 결과 Lesson 4. Counting Elements - FrogRiverOne #2 (속도 개선-1) 1. 이전 코드 분석#include int solution(int X, vector &A) { int max_pos = 0; for(int leaf = 1; leaf max_pos) max_pos = idx; } return max_pos;}std::find 함수를 통해서 vector A에서 값을 찾고 있다. std::find 함수의 실행 속도는 O(N)이다.코드에서 반복문이 하나지만, 사실상 이중반복문을 쓰고 있는 것이다. 2. 속도 개선 아이디어vector A에서 1부터 X까지 값을 매번 찾지 않고, 연관 배열(map)을 이용한다.map에서 insert 함수와 find 함수의 실행 속도는 \( O(log{N}) \) 이다. 2. 코드 (C++)#include int sol.. Lesson 4. Counting Elements - FrogRiverOne #1 1. 문제A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in secon.. Lesson 3. Time Complexity - TapeEquilibrium 1. 문제A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.Any integer P, such that 0 The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|In other words, it is the absolute difference between the sum of the first part and the sum of the second part.For example, consider array A such that:.. Lesson 3. Time Complexity - PermMissingElem 1. 문제An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.Your goal is to find that missing element.Write a function:int solution(vector &A);that, given an array A, returns the value of the missing element.For example, given array A such that:A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5the function s.. Lesson 3. Time Complexity - FrogJmp 1. 문제A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.Count the minimal number of jumps that the small frog must perform to reach its target.Write a function:int solution(int X, int Y, int D);that, given three integers X, Y and D, returns .. 이전 1 ··· 8 9 10 11 12 다음
