부분합 특정 구간 상의 합을 구할 때 필요한 구간의 합을 구하게 되는 경우 일일이 for문을 계산하기 때문에 10만이 넘는 경우 계산을 하는 시간이 많아져 많은 연산으로 인한 timeover가 발생할 수 있다. 이를 해결하기 위해 사용하는 방법으로는 input 값이 들어올때 바로바로 계산을 해서 저장을 하게 되면 이 문제는 해결이 된다. input 12 3 2 4 2 1 5 1 sum 12 15 17 21 23 24 29 30 이때 2~5번까지 의 sum을 구하기 위해서는 단 1번의 연산만 시행을 하면 된다. 5번 합 - 1번 합 = 11 단 1번의 계산으로 성립이 되기 때문에 0(1)로 성립이 가능하다. 구간의 합이 0에 가까운 구간을 찾기 위해서는 구간 합의 변화가 0에 가까운 것을 찾으면 된다. 세..
Algorithms/Definition
도입완전 탐색 알고리즘은 대개 답을 만드는 과정을 여러 개의 선택으로 나눈 뒤, 재귀 호출을 이용해 각각의 선택지를 채워가는 형태로 구현됨기존 완전 탐색은 모든 답을 다 만들어 보면서 문제를 해결하므로, 완전 탐색의 수행 시간은 탐색 공간의 크기에 직접적으로 비례이는 문제의 규모에 따라 기하급수적으로 크기가 증가조합 탐색: 완전 탐색을 포함해, 이렇게 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘모든 조합 탐색은 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어야 하는 답의 수를 줄이는 것을 목표조합 탐색 최적화 기법가지치기 기법탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라냄지금까지 찾아낸 최적해보다 부분해가 이미 더 나빠졋다면 상태 마저 탐색하지 않고 ..
다각형다각형(Polygon): 현실 세계를 계산 기하로 표현하는 데 필수적인 요소다각형의 종류볼록 다각형(Convex Polygon): 모든 내각이 180도 미만인 다각형오목 다각형(concave polygon): 180도가 넘는 내각을 가진 다각형단순 다각형(simple polygon): 다각형의 경계가 스스로를 교차하지 않는 다각형면적 구하기벡터의 외적을 이용시 삼각형 세 점이 주어지면 그 면적을 구하는 것이 가능볼록 다각형의 경우P0, P1, Pn-1의 점을 가질 때다각형 내부에 한점 q를 잡고 그 q를 중심으로 하는 삼각형을 여러개를 만들어 각각의 삼각형의 넓이들을 더하면 가능세 점 좌표 (x1,y1), (x2,y2), (x3,y3)가 있을 때 세 점을 꼭지점으로 하는 삼각형의 넓이벡터의 외적은 ..
도입계산 기하(computational geometry) 알고리즘: 점, 선, 다각형과 원 등 각종 기하학적 도형을 다루는 알고리즘 계산 기하는 3d 그래픽이나 캐드, 로보틱스 등 다양한 분야에서 사용을 하기 때문에 전산학에서는 중요한 역할많은 주제를 포함하고 있지만 학부 선형 대수나 고등학교 수준의 기하학을 요구2차원 평면 도형과 3차원 입체 도형을 모두 다룸.(주로 2차원을 많이 사용) 계산 기하의 도구들벡터정의 및 특징방향 + 크기 = 단위 벡터 + 스칼라(스칼라: 크기만 가지는 양)크기와 방향이 같으면 동일한 벡터계산기하의 기본적인 도구2차원 평면 위에 있는 서로 다른 두 점의 상대적 위치벡터의 종류위치 벡터(Position Vector)원점에서 임의의 점까지 향하는 벡터그 점은 위치 좌표들에 의..
도입탐욕법(greedy method): 각 단계마다 지금 당장 가장 좋은 방법만을 선택탐욕적 알고리즘이 사용되는 경우탐욕법을 사용해도 항상 최적회를 구할 수 있는 문제의 경우, 탐욕법은 동적 계획법보다 수행 시간이 항상 빠르기 때문에 유용시간이나 공간의 제약으로 최적회를 찾기 어려운 경우 최적회 대신 근사값을 찾는 것으로 해결 가능(임의의 답보다는 좋은 답을 구하기 좋음) 예제: 회의실 예약문제회의실이 하나 밖에 없음n T; //testcase입력 for (int test_case = 1; test_case > N; for (int i = 0; i> value; russia.push_back(value); } for (int i = 0; i> value; korea.push_back(value); } s..
