Algorithm Problem (93) 썸네일형 리스트형 Lesson 8. Leader - Dominator #2 Dominator #1에서는 map을 이용해서 풀었다.이번에는 정렬을 이용해서 풀어본다.1. 아이디어대표값이 되려면 등장 횟수가 배열 크기의 절반을 초과해야 한다.그렇다면 배열이 정렬되어 있다면? 대표값은 항상 배열의 중간에 위치하고 있지 않을까? 예시) 정렬 전A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]34323-133 정렬 후A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]-12333334 배열 전체의 절반을 넘게(초과) 차지하려면, 배열 중간값을 항상 대표값이 가지게 되어있다. 2. 문제풀이 전략배열을 정렬한다배열 중간 값을 대표값으로 정한다대표값이 배열에 몇 번 등장하는지 확인한다. (배열 전체탐색) 3. 코드 (C++)int solution(vector &A) { i.. 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.. 이전 1 ··· 5 6 7 8 9 10 11 12 다음
