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. 비트 마스크 문제 부울 배열들을 비트 마스크 로 풀어내는 문제이다. 과목 => 선수과목 학기 => 과목 학기마다 선수과목이 포함되어 있는지 확인하고. 강의를 들을 수 있는 과목을 선택하여 조합 탐색하면 쉽게 답을 구할 수 있다. tmpSelect = semester[j] & (~select); => 이번 학기에 들을 수 있는 수업중 이미 수강한것은 제외시킨다. => 최상위 비트또한 반전되어 없어진다. => 모든학생이 이번 학기에 들을 수 있는 강의들 if((tmpSelect&(1

1. 선형 자료 구조 일렬로 늘어선 같은 자료 여러개를 저장하기 위한 가장 기초적인 자료구조는 배열이다. 배열과 같이 일렬로 늘어선 자료들을 저장하기 위한 자료 구조인 동적 배열과 연결 리스트를 선형 자료 구조라고 한다. 2. 동적 배열(dynamic array) 배열의 큰 문제 중 하나는 배열의 크기를 지정해야하며, 그 이상의 자료를 집어 넣을 수 없다는 것이다. 이와 같은 문제를 해결하기 위해 만들어진 자료구조가 동적 배열이다. 동적 배열은 자료의 개수가 변함에 따라 크기가 변경된다. 동적 배열은 일반 배열처럼 언어 차원에서 지원되는 기능이 아니라 배열을 이용해 만들어 낸 별도의 자료 구조이고, 언어의 표준 라이브러리에 대개 포함되어있다. 3. 동적 배열의 특성 - 원소들은 메모리의 연속된 위치에 저..

1. 부분 합 부분 합이란 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 합을 구해둔 배열이다. psum[i] = Σscores[j] (0

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

계산 기하 점, 선, 다각형, 원 등 각종 기하학적 도형을 다루는 알고리즘을 계산 기하 알고리즘이라고 한다. 알고리즘 문제들에서는 대부분 기초적인 수학 이론을 구현할 수 있는 능력을 평가한다. 2차원 기하학 벡터의 구현(vector) 방향과 거리를 모두 알고 있으면 두 점 사아의 상대적인 위치를 정확히 표시할 수 있다. 이런 방향과 거리의 쌍을 벡터라고 한다. 벡터는 수학, 물리학, 공학 전반에 걸쳐 널리 쓰이는 개념으로 가장 기초적인 도구이다. 벡터의 시작점을 바꿔도 벡터는 변하지 않기 때문에 항상 원점으로 정해두면 벡터를 끝점의 위치(x, y)로만 표현할 수 있다. 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 2..