Algorithm Problem/Codility (91) 썸네일형 리스트형 Lesson 9. Maximum slice problem - MaxProfit #3 (속도 개선-2) 1. 속도 개선 아이디어+1이든, +100이든 흑자만 발생한다면, 가능한 오래 가져가는게 이득이기 때문에, 우리에게 필요한 값은 총 이익값이다.따라서 이익을 매일 매일 발생하는 이익의 누적으로 바라볼 필요가 있다. 우리가 구하고자 하는 이익이, 매일 발생하는 이익의 누적이라면, 최저값과 최대값의 위치도 신경쓸 필요가 없다. 왜냐하면 중간에 최저값이 있고, 맨 끝에 최대값이 있다고 할 때, 최저값에 사서, 최대값에 파는게 최대 이익인가? 하면 그렇지 않기 때문이다.최저값 이전에도 계속 흑자가 발생했다면, 그냥 흑자가 발생한 시점부터 쭈욱 가지고 오는게 최대이익이 된다. Vector A가 아래와 같다고 하자.A[0]A[1]A[2]A[3]A[4]A[5]A[6]5796134매수: A[0] / 매도: A[1] .. Lesson 9. Maximum slice problem - MaxProfit #2 (속도 개선-1) 1. 속도 개선 아이디어정렬을 사용한 코드는 개선의 여지가 있다.매번 정렬하지 말고, 필요할 때만 정렬하도록 수정할 수 있다. 알고리즘 수정정렬 후, 최대값 구하기매수가격(A[i])이 최대값(max_value)과 같지 않으면, 최대값 재활용매수가격(A[i])이 최대값(max_value)과 같으면, 최대값 다시 구하기 2. 코드 (C++)#include int getMaxPrice(vector prices, int Q){ sort(prices.begin() + Q, prices.end()); return prices.back();}int solution(vector &A) { if(A.empty()) return 0; int max_profit = 0; int max_value.. Lesson 9. Maximum slice problem - MaxProfit #1 1. 문제An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q For example, consider the following array A consisting of six elements such that:A[0] = 23171A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367If a share was bought on day 0 and sold.. Lesson 8. Leader - EquiLeader #2 (속도 개선) 1. 속도 개선 아이디어'Leader는 배열의 절반 이상을 차지해야 한다' 라는 조건에 대한 고찰이 필요하다.결론부터 얘기하자면, Equi Leader는 배열 전체 Leader와 항상 값이 같다. 전체 배열에 대한 리더(A)가 있다고 하자.전체 배열을 왼쪽 배열(LEFT)과 오른쪽 배열(RIGHT)로 나누었다.왼쪽 배열(LEFT)의 리더(B)는 리더(A)와 다른 값이 나올 수 있을까?오른쪽 배열(RIGHT)의 리더(C)는 리더(A)와 다른 값이 나올 수 있을까? 이 질문에 대한 답이, 속도 개선의 열쇠이다.리더(B)와 리더(C)가 값이 다를 수는 있지만, 둘 중 하나는 반드시 전체 배열 리더(A)와 값이 같다.즉, Equi Leader가 성립할 때는, 항상 전체 배열 리더(A)와 값이 같다. 증명결론:.. Lesson 8. Leader - EquiLeader #1 1. 문제A non-empty array A consisting of N integers is given.The leader of this array is the value that occurs in more than half of the elements of A.An equi leader is an index S such that 0 ≤ S For example, given array A such that:A[0] = 4A[1] = 3A[2] = 4A[3] = 4 A[4] = 4A[5] = 2we can find two equi leaders: - 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4. .. Lesson 8. Leader - Dominator #3-2 (코드 개선) 1. 아이디어stack을 생성해서 모든 값을 가지고 있을 필요가 없다.왜냐하면, stack에는 최종적으로 대표값만 있기 때문이다. 즉, 중복된 값만 stack에 남게된다. 2. 코드 (C++)int solution(vector &A) { if(A.empty()) return -1; //대표값 찾기 int dominator = 0; int cnt = 0; for(size_t i = 0; i 3. 결과 Lesson 8. Leader - Dominator #3-1 Dominator #1에서는 map을 이용해서 풀었다. Dominator #2에서는 정렬을 이용해서 풀었다.이번에는 stack을 이용해서 풀어본다. 1. 아이디어대표값이 가장 많이 등장하는 값이므로, 서로 다른 값들을 지우면, 결국 대표값만 남게 될 것이다.stack을 이용하면, 서로 다른 값들을 간단하게 지울 수 있다. 예시)A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]34323-133 stack으로 담으면 다음과 같이 된다.stack에는 대표값 최종적으로 남게 된다. 4 2 -1 333333333pushremovepushremovepushremovepushpush 2. 문제풀이 전략stack이 비어 있으면, 값을 넣는다stack에 값이 있으면, 현재 값과 같은지 비교한다같.. 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.. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음
