정용이의 놀이동산

개요 펜윅 트리(Fenwick Tree)라고도 한다. 누적 합 배열의 동적 자료구조이다. 이름은 트리이지만 배열로 표현한다. 모든 배열의 인덱스가 1부터 시작한다고 가정한다. 그래야 구현하기가 좀 더 쉽다. 시간복잡도가 O(log n)인 2가지 연산을 제공한다. update(int k, int diff) : 배열의 원소 갱신 sum(int k) : 1번 원소부터 k번 원소까지의 구간 합 계산 p(k) : k의 약수 중에서 가장 큰 2의 거듭제곱. p(k) = sum(k - p(k) + 1, k) 위치 k에서 끝나면서 그 길이가 p(k)인 구간의 합 BIT를 사용하면 어떤 sum(1, k)의 값도 O(log n)에 구할 수 있다. 배열의 원소를 갱신하면 BIT에서 해당 원소가 포함되어 있는 값도 갱신해야 ..

개요 집합의 묶음을 관리하는 자료구조이다. 집합은 서로소 집합(Disjoint Set)이고, 하나의 원소는 오직 하나의 집합에 속한다. 집합마다 하나의 원소가 해당 집합의 대푯값이 되고, 나머지 원소에서 대표 원소로 가는 경로가 존재한다. 유니온-파인드 자료구조는 O(Log n)의 시간복잡도를 가진 2가지 메서드를 제공한다. unite(a, b) : a와 b가 속한 각각의 집합을 하나로 합친다. find(x) : x원소가 속한 집합의 대푯값을 반환한다. 집합을 합칠 때, 원소가 더 적은 집합의 대푯값을 원소가 더 많은 집합의 대푯값으로 연결함으로써 효율적인 unite 연산을 수행할 수 있다. 구현 유니온-파인드는 배열을 사용해서 쉽게 구현할 수 있다. 배열은 각 원소에 대해서 경로상의 다음 원소를 저장하..

배열(Array) 같은 자료형의 데이터를 여러개 만들 때 사용 배열을 이용하면 연속적인 메모리 공간에 데이터들을 저장할 수 있음 각 데이터에는 인덱스를 이용하여 접근 ADT Array 객체 : 쌍의 집합 연산 : create(n) : n개의 요소를 저장할 수 있는 배열 get(A, i) : 배열 A의 i번째 요소 반환 set(A, i, v) : 배열 A의 i번째 위치에 v 저장 구조체(Structure) 배열 : 같은 타입의 데이터 모임 구조체 : 다른 타입의 데이터 묶음 struct를 이용하여 형성 예제 형식 struct 구조체이름 { int a; float b[10]; char name[20]; }; 구조체 변수 생성 struct 구조체이름 구조체변수; 구조체 타입 선언 typedef struct {..

2.1 순환 소개 순환 : 어떤 알고리즘이나 함수가 자기 자신을 호풀하여 문제를 해결하는 기법 순환 알고리즘 구조 순환을 멈추는 부분 + 순환 호출을 하는 부분 만약, 호출을 멈추는 부분이 없다면 int factorial(int n) { printf("factorial (%d)\n",n); //if(n 순환이 적절함 ex) 순환적인 문제들 보통 반복과 순환은 문제해결능력이 동등, 어떤 한 문제에 두 알고리즘을 모두 사용 가능 ex) 순환 -> 반복, 반복 -> 순환 순환은 반복에 비해 알고리즘을 명확하게 간결하게 표현 가능 순환은 매구간 함수 호출 --> 보통 반복에 비해 수행속도가 느릴 수 있음 순환 원리 순환은 분할정복(Divide & Conquer)을 구현 --> 문제의 일부분을 해결한 뒤, 문제의..

1.1 자료구조와 알고리즘 프로그램 = 자료구조 + 알고리즘 알고리즘 : 컴퓨터로 문제를 풀기 위한 단계적 절차 알고리즘의 조건 입력 : 0개 이상의 입력이 존재 출력 : 1개 이상의 출력이 존재 명백성 : 각 명령어의 의미는 모호하지 않고 명확 유한성 : 한정된 수의 단계 후에는 반드시 종료 유효성 : 각 명령어들은 실행 가능한 연산 알고리즘 기술방법 자연어 -> 순서도 -> 의사코드(Pseudo code) -> 프로그래밍 언어 자연어 인간이 이해하기 쉬움 자연어의 단어들을 정확히 정의하지 않으면 모호해질 우려가 있음 순서도 직관적, 이해하기 쉬움 복잡한 알고리즘의 경우, 굉장히 복잡해짐 의사코드 알고리즘 기술에 가장 많이 사용 알고리즘의 핵심적인 내용에만 집중 가능 프로그래밍 언어 알고리즘을 가장 정..