elbaro · June 5, 2016 07:51
diff --git a/ts b/ts
 # SDS Expert-to-be
 #### 강사. 강동구

 ## 1회
 - 2차원 벡터
 연속된 180도 범위의 모든 벡터를 쓰는 것이 정답이다.

 - 분수 찾기
 이분검색 + 특정 수 이하의 기약분수 개수 구하기 (에라토스테네스의 체)

 - Utopia Divided
 IOI 2002 보고서 참조
 http://olympiads.win.tue.nl/ioi/ioi2002/contest/report.pdf


 - 페리 수열의 합
 여러 N에 대해 답을 출력해보고 규칙을 찾는다. N번째 페리 수열의 길이와 비례한다.

 ## 2회

 - 히스토그램
 스택을 쓰면 선형 시간에 풀 수 있다.
 - 최소값 찾기
 유명한 Sliding Window 테크닉을 쓰면 된다.
 - CCW
 기하의 기본인 CCW 함수를 공부하는 문제
 - 다각형의 면적
 사선식으로 다각형의 면적을 구하는 공식을 연습한다.

 - 교차
 두 선분의 교차여부 판별법을 배우고 연습하였다. box_checking과 ccw_checking이 있다.

 - 볼록 껍질
 Convex Hull 알고리즘을 배우고 연습하였다.

 - 고속도로
 볼록 껍질을 이용하여 가장 먼 두 점을 찾는 법을 배우고 연습하였다.

 - 가장 가까운 두 점
 분할정복으로 가장 가까운 두 점을 찾는 법을 배우고 연습하였다.


 ## 3회

 - A+B: A+B를 출력한다.
 - 집합의 표현: union find 연습 문제이다.
 - 최소 스패닝 트리: kruscal 연습 문제이다.
 - 네트워크 연결: kruscal 연습 문제
 - 행성 터널: x, y, z 각각으로 정렬한 3개의 리스트를 가지고, 3n개의 이웃쌍 중 최소값을 골라 연결해 나가면 된다.
 - 두 번째로 작은 스패닝 트리: 우선 MST를 구한 뒤, 나머지 간선들을 추가해 본다. cycle이 생길텐데, 이 cycle 상에서 최대 가중치 간선을 제거해주면 second MST를 구할 수 있다. 이를 위해 LCA와 PQ를 익혀야 한다.
 - 스패닝 트리: kruscal을 제대로 이해했는지 보는 문제. 같은 가중치인 간선이 최대 4개이므로 많아야 2^4가지를 고려하면 된다.
 - 정상: 높은 지대부터 union find로 이웃한 4칸을 합쳐나가면 된다.

 ## 3.5회
 공통조상찾기와 우선순위 큐를 연습하는 세션이다. 모두 기본적인 알고리즘으로 풀 수 있다.

 - 소수의 곱
 1에서 출발하여 여기에 작은 소수부터 곱해나간다. 매 순간 다음 가장 작은 수가 될 후보들을 우선순위 큐에 가지고 있으면 된다.

 나머지 문제는 LCA와 PQ를 변형하지 않고 그대로 쓰면 되는 기본적인 문제들이다.


 ## 4회

 Range Tree들을 공부하는 세션이다.

 - A: 구간 트리를 배우고 연습한다.
 - B: 구간 트리 실습문제.
 - C: Lazy Propagation 테크닉 연습
 - D: 2차원 구간 트리 연습
 - E: 2차원 구간 트리를 선형 메모리로 구현하면 된다.
 - F: 현재 i번째 쿼리로 x번 DVD를 옮긴다면 마지막으로 x번을 옮겼던 쿼리의 번호 j를 찾는다. 정답은 [j+1,i-1] 구간의 쿼리에서 unique한 DVD들이 몇 가지가 등장했는지를 찾으면 된다. 각 DVD별로 마지막에 등장한 위치의 쿼리에만 +1을 해 두면 이들의 합이 정답이 된다.
	# SDS Expert-to-be
	#### 강사. 강동구

	## 1회
	- 2차원 벡터
	연속된 180도 범위의 모든 벡터를 쓰는 것이 정답이다.

	- 분수 찾기
	이분검색 + 특정 수 이하의 기약분수 개수 구하기 (에라토스테네스의 체)

	- Utopia Divided
	IOI 2002 보고서 참조
	http://olympiads.win.tue.nl/ioi/ioi2002/contest/report.pdf


	- 페리 수열의 합
	여러 N에 대해 답을 출력해보고 규칙을 찾는다. N번째 페리 수열의 길이와 비례한다.

	## 2회

	- 히스토그램
	스택을 쓰면 선형 시간에 풀 수 있다.
	- 최소값 찾기
	유명한 Sliding Window 테크닉을 쓰면 된다.
	- CCW
	기하의 기본인 CCW 함수를 공부하는 문제
	- 다각형의 면적
	사선식으로 다각형의 면적을 구하는 공식을 연습한다.

	- 교차
	두 선분의 교차여부 판별법을 배우고 연습하였다. box_checking과 ccw_checking이 있다.

	- 볼록 껍질
	Convex Hull 알고리즘을 배우고 연습하였다.

	- 고속도로
	볼록 껍질을 이용하여 가장 먼 두 점을 찾는 법을 배우고 연습하였다.

	- 가장 가까운 두 점
	분할정복으로 가장 가까운 두 점을 찾는 법을 배우고 연습하였다.


	## 3회

	- A+B: A+B를 출력한다.
	- 집합의 표현: union find 연습 문제이다.
	- 최소 스패닝 트리: kruscal 연습 문제이다.
	- 네트워크 연결: kruscal 연습 문제
	- 행성 터널: x, y, z 각각으로 정렬한 3개의 리스트를 가지고, 3n개의 이웃쌍 중 최소값을 골라 연결해 나가면 된다.
	- 두 번째로 작은 스패닝 트리: 우선 MST를 구한 뒤, 나머지 간선들을 추가해 본다. cycle이 생길텐데, 이 cycle 상에서 최대 가중치 간선을 제거해주면 second MST를 구할 수 있다. 이를 위해 LCA와 PQ를 익혀야 한다.
	- 스패닝 트리: kruscal을 제대로 이해했는지 보는 문제. 같은 가중치인 간선이 최대 4개이므로 많아야 2^4가지를 고려하면 된다.
	- 정상: 높은 지대부터 union find로 이웃한 4칸을 합쳐나가면 된다.

	## 3.5회
	공통조상찾기와 우선순위 큐를 연습하는 세션이다. 모두 기본적인 알고리즘으로 풀 수 있다.

	- 소수의 곱
	1에서 출발하여 여기에 작은 소수부터 곱해나간다. 매 순간 다음 가장 작은 수가 될 후보들을 우선순위 큐에 가지고 있으면 된다.

	나머지 문제는 LCA와 PQ를 변형하지 않고 그대로 쓰면 되는 기본적인 문제들이다.


	## 4회

	Range Tree들을 공부하는 세션이다.

	- A: 구간 트리를 배우고 연습한다.
	- B: 구간 트리 실습문제.
	- C: Lazy Propagation 테크닉 연습
	- D: 2차원 구간 트리 연습
	- E: 2차원 구간 트리를 선형 메모리로 구현하면 된다.
	- F: 현재 i번째 쿼리로 x번 DVD를 옮긴다면 마지막으로 x번을 옮겼던 쿼리의 번호 j를 찾는다. 정답은 [j+1,i-1] 구간의 쿼리에서 unique한 DVD들이 몇 가지가 등장했는지를 찾으면 된다. 각 DVD별로 마지막에 등장한 위치의 쿼리에만 +1을 해 두면 이들의 합이 정답이 된다.
No results found