최대 연속 부분합 최대 연속 부분합이란 어떤 수열 $a_1, a_2, ..., a_{N}$이 주어졌을 때 $1 \leq i \leq j \leq N$ 를 만족하는 $sum(a_i, a_{i+1}, ..., a_j)$ 중 최댓값을 뜻합니다. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제를 예로 들어봅시다. 쉽게 떠올릴 수 있는 풀이는 어떤 $(i, j)$에 대해 $sum(a_i, a_{i+1}, ..., a_j),(1 \leq i \leq j \..
혼자 그림 그려보면서 끙끙대다가 질문을 올렸는데 친절하신 분이 답변해주셨다. 앞쪽 부분의 개수를 정확히 구했으면 아래 싸이트에 수열을 넣고 검색해보라 하셨음. https://oeis.org/ The On-Line Encyclopedia of Integer Sequences® (OEIS®) oeis.org N = 2 $\longrightarrow$ 답 = 1 N = 4 $\longrightarrow$ 답 = 2 N = 6 $\longrightarrow$ 답 = 5 N = 8 $\longrightarrow$ 답 = 14 1, 2, 5, 14를 넣어보니 카탈란 수 라고 한다. $i$번째 카탈란수 $C_i = {2i\choose i} - {2i\choose i+1}$ 이다. 문제의 제한에서 N은 짝수이므로 $C..
0. 들어가기 전에 첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다. 원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 쓰게 되었습니다. 본 글의 내용은 고등학교 과정(2007 개정 교육과정 기준)인 '기하와 벡터' 수준의 지식만 있으면 얼추 알아들을 수 있지만, 혹시 그렇지 않다면 설명을 봐도 이해가 안가실 수 있습니다. 급하게 CCW를 사용해야 한다면 바로 아래의 한 줄 요약과 본문 하단의 코드(여기)만 보고 쓰시면 됩니다. 1. CCW 기하 알고리즘을 공부하기 전에 필수로 알아야 할 것이 있는데, 그게 바로 CCW입니다. 거의 사칙연산처럼 쓰게 될 거에요. CCW는 Counter Clockwise의 약자로써, 평면 위에 놓여진 세 점의 방향관계를 구할 수 ..