Algorithm Problem/Codility (91) 썸네일형 리스트형 Lesson 8. Leader - Dominator #1 1. 문제An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.For example, consider array A such thatA[0] = 3 A[1] = 4 A[2] = 3A[3] = 2 A[4] = 3 A[5] = -1A[6] = 3 A[7] = 3The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more th.. Lesson 7. Stacks and Queues - StoneWall 1. 문제You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by an array H of N positive integers. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall's left.. Lesson 7. Stacks and Queues - Nesting 1. 문제A string S consisting of N characters is called properly nested if:S is empty;S has the form "(U)" where U is a properly nested string;S has the form "VW" where V and W are properly nested strings.For example, string "(()(())())" is properly nested but string "())" isn't.Write a function: int solution(string &S);that, given a string S consisting of N characters, returns 1 if string S is pr.. Lesson 7. Stacks and Queues - Fish 1. 문제You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.The fish are numbered from 0 to N − 1. If P and Q are two fish and P Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the.. Lesson 7. Stacks and Queues - Brackets 1. 문제A string S consisting of N characters is considered to be properly nested if any of the following conditions is true: - S is empty; - S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string; - S has the form "VW" where V and W are properly nested strings.For example, the string "{[()()]}" is properly nested but "([)()]" is not.Write a function: int solution(string &S).. Lesson 6. Sorting - NumberOfDiscIntersections #2 (속도 개선) 1. 속도 개선 아이디어현재 모든 원을 하나씩 다 비교하고 있다. (전체탐색)정렬을 이용하면, 비교 횟수를 줄일 수 있다. 예제를 정렬해보자.정렬 기준은 왼쪽 값이다.원점(index)반지름(value)왼쪽 값오른쪽 값15-4601-112204440831245055 정렬된 데이터를 가지고 비교해자.왼쪽 값이 정렬되어 있으므로, 모든 원과 비교할 필요가 없다. A[1]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[0], A[2], A[4], A[3], A[5]A[0]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[2], A[4]A[2]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[4], A[3]A[4]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[3], A[5.. Lesson 6. Sorting - NumberOfDiscIntersections #1 1. 문제We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).The fig.. Lesson 6. Sorting - Triangle #2 (속도개선) 1. 속도개선 아이디어문제에서 삼각형을 만드는 조건을 다음과 같이 제시하고 있다.0 ≤ P A[P] + A[Q] > A[R]A[Q] + A[R] > A[P]A[R] + A[P] > A[Q]여기서 조건1은 삼각형을 만드는데 쓰이는 값(인덱스)이 중복 사용할 수 없다는 뜻이지,Vector A의 값 순서가 지켜져야 한다는 뜻은 아니다. 따라서 Vector A를 오름차순으로 정렬하면, 확인해야 하는 경우의 수가 줄어든다.왜냐하면 오름차순으로 정렬된 상태에서는 조건3과 조건4는 당연하기 때문이다. (A[R] > A[P], A[Q]) 즉, 우리가 확인해야 하는 경우는 오직 조건2 뿐이다.조건2는 나란히 붙어있는 3개의 값을 확인하면 된다. 2. 코드 (C++)#include #include int solution.. 이전 1 ··· 5 6 7 8 9 10 11 12 다음
