본문 바로가기

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 < .. 더보기
면접 준비 * 직무의 이해s직군에 대하여 삼성홈페이지 접속하여 조사하기 * Researcher & Developer 연구 개발자- 혁신적인 기술을 바탕으로 한 제품 개발(면접에서는 그 기술력을 잘 합쳐서 같이 협동할 수 있는 지를 본다.)(혁신적인 기술을 얼마나 잘 하는 지 보다 같이 오래 할 수 있는 사람)(시장과 고객의 needs를 파악한 합리적 가격의 제품 개발 * 요구되는 자질- 소통 능력, 태도 ( 가장 주로 요구되는 것 소통능력)- 책임감, 열정, 인내, 끈기=> 이 두가지는 본인의 episode 로 이루어 지는것=> 듣고 싶어 하는 대답을 잘 듣고, 잘 하는 것.=> 성실함, 인상적인 부분은 보면 충분히 알 수 있다.=> 이러한 episode 5개정도는 만들어 두는게 도움이 된다. - 전문적인 지식과 .. 더보기
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 더보기