본문 바로가기

분류 전체보기63

BOJ 6171) 땅따먹기 어떤 땅의 i 의 너비 Wi 와 Hi 가 주어진다.이 때 가격은 Wi * Hi 이다. - 한번에 여러개 된다면, (해당 땅 중 Wi의 최댓값 ) * (해당 땅 중 Hi의 최댓값) 으로 가격을 매긴다. 따라서 땅을 최소 비용으로 묶어서 살 경우 최소 비용은 ? 일단 무조건 wi를 기준으로 정렬을 시킨다.이 때 만약 Wi 와 Hi 가 Wj , Hj보다 더 크다면 무조건 묶는게 이득이다. 따라서 O(n) 시간으로 탐색하면서 더 큰 애들을 지워나간다. 그렇게 되면 현재 Wi 는 오름차순, Hi 는 내림차순으로 정렬된다. 그러고 DP를 생각해보자! DP[i] = min (DP[j-1] + b[j] * a[i]) 의 식이 성립한다. ( b 는 내림차순) 그러므로 Convex Hull Trick 을 사용하면 된다. .. 2018. 5. 13.
DP최적화 - Convex Hull Trick * 필요한 상황 dp[i] = min( dp[j] + b[j]*a[i] ) 를 찾는건데 여기서 b[i] > b[i+1] ( b는 내림차순) 을 반드시 만족한다. (j < i 인 정수) 만약 오름차순이라면 굳이 계산할 필요가 없고, 내림차순이라면 binary search 로 찾을 수 있다. 이런 식이 나온다면 바로 CHT 를 쓸 수 있다. 여기서 문제가 되는 것은 바로 조건에 맞지 않는 직선들을 제거해주는 것이다. * 업데이트현재 line1이 새로 추가될 것이라고 생각하자.그렇다면 line3 , line2 를 현재 저장된 라인들 중 가장 뒤에 있는 라인이라고 하자. intersect - x(line3,line1) = x1intersect - x(line3,line2) = x2 라고 해보자. 만약 x1 < .. 2018. 5. 6.
면접 준비 * 직무의 이해s직군에 대하여 삼성홈페이지 접속하여 조사하기 * Researcher & Developer 연구 개발자- 혁신적인 기술을 바탕으로 한 제품 개발(면접에서는 그 기술력을 잘 합쳐서 같이 협동할 수 있는 지를 본다.)(혁신적인 기술을 얼마나 잘 하는 지 보다 같이 오래 할 수 있는 사람)(시장과 고객의 needs를 파악한 합리적 가격의 제품 개발 * 요구되는 자질- 소통 능력, 태도 ( 가장 주로 요구되는 것 소통능력)- 책임감, 열정, 인내, 끈기=> 이 두가지는 본인의 episode 로 이루어 지는것=> 듣고 싶어 하는 대답을 잘 듣고, 잘 하는 것.=> 성실함, 인상적인 부분은 보면 충분히 알 수 있다.=> 이러한 episode 5개정도는 만들어 두는게 도움이 된다. - 전문적인 지식과 .. 2018. 4. 24.
4.9 알고리즘 수업 Array Doubling* 우리는 계산할때 배열이 얼마나 필요한지 모른다.* 새로운 원소를 삽입할때 room 이 필요하다면- 두배의 길이 배열을할당한다.- 새로운 배열로 값을 옮긴다 * t를 배열을 옮기는데 사용되는 cost 라고 하자.- (n+1)을 삽입할때 doubling 이 발생한다고 하자.-t*n의 시간이 걸린다 array-doubling 에- t*n/2 + t*n/4 + t*n/8 + ... for previous array doubling- 이것들은 t*n 보다 작다.- total cost < 2t*n 2018. 4. 9.