분류 전체보기 썸네일형 리스트형 <자료구조 알고리즘> 배열 ※ 이 글은 배열을 처음 배우시는 분들을 위한 글이 아닙니다. 배열이란? 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조 그냥 맨날 쓰는 그 배열 맞다. 근데 이 배열에도 종류가 있다. 그리고 그 종류에 따라 각 연산을 하는데 걸리는 시간복잡도가 달라진다. 배열의 종류에 따라 다음 연산에 걸리는 시간복잡도를 계산해 볼 것이다. - 인덱스가 i인 원소 접근 - i번째에 값 삽입(insertion), 삭제(deletion) - 마지막에 값 삽입,삭제 - 처음에 값 삽입, 삭제 종류 다음과 같이 분류해 볼 수 있겠다. 1. static array 2. dynamic array 1. Static Array 말 그대로 정적인 배열이다. 즉 한번 할당되고 나면 크기와 길이를 바꿀 수 없는 배열이다. c.. 더보기 <자료구조 알고리즘> FFT를 이용한 다항식 곱셈 알고리즘 다항식 곱셈은 수학에서 아주 기본적으로 하는 연산 중에 하나이다. $$A(x) = 5x+2$$ $$B(x) = x^2+2x+3$$ 이 두식을 곱한 C(x)를 구한다고 하면 $$C(x) = (5x+2)(x^2+2x+3) \\ = 5x \times x^2 + 5x \times 2x+2\times x^2 + 5x \times 3+2 \times 2x + 2 \times 3 = 5x^3 + 14x^2 + 19x + 6$$ 이렇게 쉽게 계산할 수 있다. 하지만 컴퓨터로 짜려면 어떻게 해야 할까? 다항식을 나타내는 방법에는 대표적으로 coefficient representation과 value representation 이 있다. coefficient representation으로 위의 A(x)와 B(x)를 나타내.. 더보기 이전 1 ··· 4 5 6 7 다음
