목록자료구조, 알고리즘 정리 (5)

codedoc

plane sweeping - 직사각형 넓이합 구하기

plane sweeping 사각형 넓이 구하기 알고리즘문제링크 : https://www.acmicpc.net/problem/3392 작성중... 아래 처럼 직사각형이 겹쳐졌을 때 색칠된 부분의 넓이 합을 구하는 것이 목표입니다. 먼저 각 직사각형의 가로선을 포함하는 x축과 평행한 선으로 잘라 줍니다. 필요없는 좌표들을 버리고 나면 다음과 같이 트리를 구성할 수 있습니다.각 트리는 (y축 합, 카운트)데이터 묶음을 가지고 있고 앞으로 (sum, cnt)라고 부르겠습니다. 각 직사각형의 세로성분 데이터를 얻어오고 각 선들을 x축 기준으로 정렬시킵니다.이렇게 하면 왼쪽에서부터 sweep을 차례대로 할 수 있을 것입니다. sweep을 x축이 작은 세로선 부터 시작합니다.넓이을 어떻게 구하냐면, 각 과정마다 (직..
자료구조, 알고리즘 정리 2016. 7. 24. 23:47
최장증가수열 LIS (Longest Increasing Subsequence)

인터넷에 널려있는 n^2 해법은 생략하고 이분탐색을 이용한 nlogn 해법을 소개합니다.LIS는 부분수열이 되는 것 중 가장 긴 수열을 찾는 알고리즘 입니다.무슨 말이냐 하면,8 12 15 9 13 1 14 5이렇게 있으면 8 -> 9 -> 13 -> 14 가 가장 긴 수열이 되고 이를 찾는 알고리즘이라는 소리죠. n^2 해법에서 dp의 정의가 마지막 수가 x번째인 가장 긴 최장증가수열을 의미한다면다음에서 소개할 nlogn 해법에서 dp의 정의는 길이가 x인 최장증가수열의 마지막 수의 최소값를 의미합니다.두 알고리즘이 같은 역할을 할 것이라는 점은 뭔가 직관적으로 와닿는다고 생각합니다.익숙치 않다면 아래 그림을 보며 이해 해보시기 바랍니다. 앞서 말했지만 이분탐색을 이용하기 때문에 이분탐색을 모르시는 분..
자료구조, 알고리즘 정리 2016. 7. 24. 23:04
knapsack 문제

knapsack problem 즉, 배낭 채우기 문제인데 동적 계획법 공부를 하다보면 한 번쯤은 보았을 유명한 문제이기도 하다. 배낭 채우기 문제는 여러 버전이 있다만, 내가 이 문제를 처음 공부할 때는 좀처럼 자세한 설명이나 최적화된 코드를 찾기 어려웠다. 많은 이들의 삽질을 줄여 보려고 knapsack problem에 대해 내가 아는 지식 총동원해서 정리해보았다. 글을 읽고 오류나 수정/추가할 부분이 있다면 알려주길 바란다.
자료구조, 알고리즘 정리 2015. 8. 23. 15:52
Convex Hull Trick / c++ 코드

아직은 정리가 잘 안된거 같은데 이해하기 어려운 부분은 덧글로 남겨 주세요.
자료구조, 알고리즘 정리 2015. 8. 3. 19:45
Binary Indexed Tree / c++코드

아직 수정중입니다.
자료구조, 알고리즘 정리 2015. 8. 3. 01:14
Prev 1 Next