1. 문제 표지판번호가 0 ~ n-1 인 표지판이 있는 등산로가 있다고한다. 표지판에는 해발고도가 적혀있고 배열 h에 번호마다 해발고도가 저장되어있다. a번 표지판에서 b번 표지판까지의 등산로의 난이도를 a~b의 최대 해발고도와 최소 해발고도의 차이라고 한다. a, b가 주어졌을때 난이도를 구하는 함수를 만드라는게 이 문제의 의도이다. 2. 구간 트리 초기화 pair 객체를 가지는 구간 트리를 만들어서 각 구간마다 최대 최소인 원소를 저장해야한다. 이는 바텀업 방식으로 재귀를 이용하여 리프부터 루트까지 각 노드를 채워야한다. 기저조건으로 구간의 길이가 1 일때(리프) 구간은 최대와 최소가 같은 pair을 반환한다. 재귀를 이용하여 왼쪽, 오른쪽 서브트리를 루트로 합친다. 합칠때 최대는 최대끼리 최소는 최..

1. 트리의 순회 이 문제는 트리의 preorder와 inorder가 주어졌을 때 이 정보를 가지고 postorder을 생성하는 문제이다. preorder는 각 서브트리의 루트를 먼저 출력한다. 따라서 preord[0]은 이 트리의 루트가된다. inorder는 서브트리의 왼쪽끝쪽을 조사한다음 서브트리의 루트를 출력한다음 오른쪽을 조사한다. 즉, 트리의 루트가 출력될때 이미 이 루트의 왼쪽 부분은 탐색을 마친 상태이다. 트리의 루트의 오른쪽은 오른쪽 서브 트리이다. 위의 각 순회의 특성을 이용하여 재귀적으로 함수를 구현하면 답을 쉽게 얻을 수 있다. 이 코드의 시간복잡도는 r 과 for문에 지배된다 for문은 각 단계에서 대략 n번 수행되고 r = n이므로 O(N^2)의 시간 복잡도를 가진다. 1 2 3 ..

1. 문자열 이 문제는 KMP알고리즘을 사용하면 간단하게 풀 수 있다. 아래 코드는 좀 복잡하게 구현하였는데, 사실 첫 상태와 비교하는게 아니라 이전 상태랑 비교하면 더 깔끔한 코드가 될 것이다. 또한 A를 시계방향으로 i만큼 돌린 결과가 B일때 이는 B를 반시계방향으로 i만큼 돌린 결과가 A라는 것을 이용하면 더 직관적 일 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #include usi..

1. 크리스마스 인형 이 문제는 두가지의 문제를 풀어야한다. 선물상자의 인덱스 0~n 주문한번: a번 박스 부터 b번 박스까지 구매 1. 산타가 아이들에게 같은양의 선물을 주고 남은 나머지가 0인 상자의 구간의 개수 2. 산타가 아이들에게 띄엄 띄엄 주문해서(중복x) 주문한번당 아이들에게 나머지 없이 나누어주는 최대의 주문 수 2. 1번 문제 1번문제에서 이 문제는 부분 구간의 부분합을 구해야한다는 것을 알 수 있다. psum[a] = 0~a 까지의 합 order(a, b) = a 에서 b까지 주문하고 총 인형의 개수 라고 하자. 아이들한테 남는거 없이 선물하므로, order(a, b) % child == 0 이 되어야함을 알 수 있다. order(a, b) = psum[b] - psum[a-1] ord..

1. 벡터 이 문제는 장애물과의 충돌 유무와 충돌후 방향 벡터를 구하는 함수만 구현하면 쉽게 풀린다. 문제는 구현이다. 이 문제에서 사용한 벡터 클래스는 책에 구현되어 있는 것이다. 2. 핀볼과 장애물의 충돌 유무 판단 장애물의 중심 = c 장애물의 반지름 = r 핀볼의 방향 벡터 = dir 핀볼의 시작점 = a 장애물에서 a, a+dir 두점을 지나는 직선과의 거리 = h 라고 하자. 먼저 핀볼의 현재 상태에서 다음 충돌할 장애물을 찾아야한다. 핀볼이 충돌 할 수 있는 장애물은 h < r + 1 임을 알 수 있다. 그리고 이 조건을 만족하는 장애물들 중에서 핀볼과 가장 가까운 장애물을 선택하면된다 이것은 내분점 공식을 이용하여 구하였다. (예외 조건으로 a를 중심으로 dir과 c 가 예각을 이루어야 한..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include #include #include #include using namespace std; const int MAX_N = 10000001; int minfac[MAX_N]; int testCase, n, lo, hi; void era() { for(int i = 2; i testCase; for(int i = 0; i >n>>lo>>..